QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#396058#3082. Ascending MatrixGraphcityWA 60ms6700kbC++202.4kb2024-04-22 11:23:212024-04-22 11:23:21

Judging History

你现在查看的是最新测评结果

  • [2024-04-22 11:23:21]
  • 评测
  • 测评结果:WA
  • 用时:60ms
  • 内存:6700kb
  • [2024-04-22 11:23:21]
  • 提交

answer

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=350,Mod=998244353;

inline int Pow(int x,int y)
{
    int res=1;
    while(y)
    {
        if(y&1) res=1ll*res*x%Mod;
        x=1ll*x*x%Mod,y>>=1;
    }
    return res;
}

int n,m,K,X,Y,Z,f[Maxn+5][Maxn+5][2],val[Maxn+5];
int d[Maxn+5][Maxn+5],h[Maxn+5][Maxn+5];
int dx[Maxn+5][Maxn+5][2];
int fac[Maxn+5],inv[Maxn+5],g[Maxn+5],ans;

inline int sgn(int x) {return (x&1)?Mod-1:1;}
inline int Gauss()
{
    int ans=1; For(i,1,K)
    {
        int p=i; For(p,i,K) if(h[p][i]) {p=i; break;}
        if(!h[p][i]) return 0; if(p!=i) ans=Mod-ans,swap(h[p],h[i]);
        ans=1ll*ans*h[i][i]%Mod,p=Pow(h[i][i],Mod-2);
        For(j,i,K) h[i][j]=1ll*p*h[i][j]%Mod; For(j,i+1,K)
            {p=Mod-h[j][i]; For(k,i,K) h[j][k]=(h[j][k]+1ll*p*h[i][k])%Mod;}
    } return ans;
}
inline void Solve(int sx,int sy,int id)
{
    memset(f,0,sizeof(f)); f[sx][sy][0]=1;
    For(i,sx,Maxn) Rof(j,sy,0)
    {
        if(d[i][j]==-1) f[i][j][0]=f[i][j][1]=0;
        if(d[i][j]==1) f[i][j][1]=f[i][j][0],f[i][j][0]=0;
        For(op,0,1)
        {
            if(i<Maxn) (f[i+1][j][op]+=f[i][j][op])%=Mod;
            if(j) (f[i][j-1][op]+=f[i][j][op])%=Mod;
        }
    }
    For(i,1,K)
    {
        int tx=n+i-1,ty=i-1;
        For(op,0,1) dx[i][id][op]=f[tx][ty][op];
    }
}
inline int Work(int w)
{
    For(i,1,K) For(j,1,K) h[i][j]=(dx[i][j][0]+1ll*w*dx[i][j][1])%Mod;
    return Gauss();
}

signed main()
{
    // freopen("1.in","r",stdin);

    cin>>n>>m>>K>>X>>Y>>Z; fac[0]=inv[0]=1;
    if(K==1) {cout<<1<<endl; return 0;} K--;
    For(i,1,Maxn) fac[i]=1ll*fac[i-1]*i%Mod;
    inv[Maxn]=Pow(fac[Maxn],Mod-2)%Mod;
    Rof(i,Maxn-1,1) inv[i]=1ll*inv[i+1]*(i+1)%Mod;
    if(Z<=K) for(int i=Z-1;X+i<=Maxn && Y+i<=Maxn;++i) d[X+i][Y+i]=1;
    if(Z>1) d[X+Z-2][Y+Z-2]=-1;
    For(i,1,K) Solve(i-1,m+i-1,i);
    For(i,0,K) val[i]=1ll*Work(i)*inv[i]%Mod*inv[K-i]%Mod*sgn(K-i)%Mod;
    g[1]=1; For(i,1,K) Rof(j,i+1,1) g[j]=(1ll*g[j]*(Mod-i)+g[j-1])%Mod;
    ans=1ll*val[0]*g[K-Z+2]%Mod;
    For(i,1,K)
    {
        For(j,1,K+1) g[j]=1ll*(g[j]-g[j-1]+Mod)*Pow(Mod-i,Mod-2)%Mod;
        ans=(ans+1ll*val[i]*g[K-Z+1])%Mod;
        Rof(j,K+1,1) g[j]=(1ll*g[j]*(Mod-i)+g[j-1])%Mod;
    } cout<<ans<<endl;
    // cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 17ms
memory: 5068kb

input:

148 129 48 144 105 13

output:

467058311

result:

ok single line: '467058311'

Test #2:

score: 0
Accepted
time: 0ms
memory: 5084kb

input:

57 48 11 56 9 1

output:

951177245

result:

ok single line: '951177245'

Test #3:

score: 0
Accepted
time: 35ms
memory: 6572kb

input:

121 146 72 117 72 25

output:

284798523

result:

ok single line: '284798523'

Test #4:

score: 0
Accepted
time: 4ms
memory: 6532kb

input:

66 142 11 51 124 4

output:

542285716

result:

ok single line: '542285716'

Test #5:

score: 0
Accepted
time: 60ms
memory: 5424kb

input:

45 127 98 3 31 80

output:

116902187

result:

ok single line: '116902187'

Test #6:

score: 0
Accepted
time: 22ms
memory: 6280kb

input:

125 199 45 51 91 21

output:

715355617

result:

ok single line: '715355617'

Test #7:

score: 0
Accepted
time: 2ms
memory: 5760kb

input:

41 153 6 6 147 2

output:

190519561

result:

ok single line: '190519561'

Test #8:

score: 0
Accepted
time: 28ms
memory: 5304kb

input:

112 108 69 99 29 47

output:

481688971

result:

ok single line: '481688971'

Test #9:

score: 0
Accepted
time: 54ms
memory: 6552kb

input:

138 99 94 73 43 73

output:

667469005

result:

ok single line: '667469005'

Test #10:

score: 0
Accepted
time: 6ms
memory: 5012kb

input:

143 147 18 24 141 9

output:

763965115

result:

ok single line: '763965115'

Test #11:

score: 0
Accepted
time: 52ms
memory: 5396kb

input:

99 63 97 78 51 66

output:

130195301

result:

ok single line: '130195301'

Test #12:

score: 0
Accepted
time: 2ms
memory: 6272kb

input:

103 23 10 25 7 4

output:

674555733

result:

ok single line: '674555733'

Test #13:

score: 0
Accepted
time: 19ms
memory: 5120kb

input:

137 194 42 125 104 17

output:

416667361

result:

ok single line: '416667361'

Test #14:

score: 0
Accepted
time: 5ms
memory: 5216kb

input:

191 13 37 42 2 21

output:

530754407

result:

ok single line: '530754407'

Test #15:

score: 0
Accepted
time: 11ms
memory: 5128kb

input:

195 33 53 101 29 32

output:

851306824

result:

ok single line: '851306824'

Test #16:

score: 0
Accepted
time: 3ms
memory: 5088kb

input:

84 173 8 70 70 6

output:

25135799

result:

ok single line: '25135799'

Test #17:

score: 0
Accepted
time: 11ms
memory: 6700kb

input:

39 53 49 37 6 9

output:

640044940

result:

ok single line: '640044940'

Test #18:

score: 0
Accepted
time: 29ms
memory: 5160kb

input:

135 129 68 134 86 16

output:

910022919

result:

ok single line: '910022919'

Test #19:

score: 0
Accepted
time: 16ms
memory: 6140kb

input:

62 74 56 28 12 46

output:

774987233

result:

ok single line: '774987233'

Test #20:

score: 0
Accepted
time: 42ms
memory: 5344kb

input:

87 135 81 27 44 58

output:

629485683

result:

ok single line: '629485683'

Test #21:

score: 0
Accepted
time: 21ms
memory: 5100kb

input:

148 199 44 79 81 40

output:

369408819

result:

ok single line: '369408819'

Test #22:

score: -100
Wrong Answer
time: 2ms
memory: 6140kb

input:

18 195 5 17 151 5

output:

740771679

result:

wrong answer 1st lines differ - expected: '198068951', found: '740771679'