QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#396058 | #3082. Ascending Matrix | Graphcity | WA | 60ms | 6700kb | C++20 | 2.4kb | 2024-04-22 11:23:21 | 2024-04-22 11:23:21 |
Judging History
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'