QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#419671 | #7974. 染色 | kkkgjyismine4 | 100 ✓ | 453ms | 29456kb | C++14 | 2.0kb | 2024-05-24 08:55:12 | 2024-05-24 08:55:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,mx=5e5;
int fac[500005],ifac[500005];
int mul(int a,int b){return 1ll*a*b%mod;}
void add(int &x,const int y){if((x+=y)>=mod)x-=mod;}
void sub(int &x,const int y){if((x+=(mod-y))>=mod)x-=mod;}
int C(int n,int m){if(n<m)return 0;return mul(fac[n],mul(ifac[m],ifac[n-m]));}
int n,m,k,Wn[1<<21|1],f[1<<21|1],g[1<<21|1],limit,L,r[1<<21|1];
int qpow(int a,int b){
int c=1;
while(b){if(b&1)c=mul(c,a);a=mul(a,a),b>>=1;}
return c;
}
void ntt(int *a,int o){
for(int i=0;i<limit;++i)if(i<r[i])swap(a[i],a[r[i]]);int now=3;if(o<0)now=qpow(3,mod-2);
for(int m=1;m<limit;m<<=1){
int Gi=qpow(now,mod/(m<<1));
Wn[0]=1;for(int j=1;j<=m;++j)Wn[j]=mul(Wn[j-1],Gi);
for(int i=0;i<limit;i+=(m<<1))
for(int j=0;j<m;++j){
int x=a[i+j],y=mul(a[i+j+m],Wn[j]);
a[i+j]=x+y,a[i+j+m]=x+mod-y;
if(a[i+j]>=mod)a[i+j]-=mod;
if(a[i+j+m]>=mod)a[i+j+m]-=mod;
}
}
if(o<0){
int inv=qpow(limit,mod-2);
for(int i=0;i<limit;++i)a[i]=mul(a[i],inv);
}
}
int main(){
cin>>n>>m>>k;
fac[0]=ifac[0]=ifac[1]=1;
for(int i=1;i<=mx;++i)fac[i]=mul(fac[i-1],i);
for(int i=2;i<=mx;++i)ifac[i]=mul(ifac[mod%i],mod-mod/i);
for(int i=1;i<=mx;++i)ifac[i]=mul(ifac[i],ifac[i-1]);
limit=1,L=0;while(limit<=2*n*m)limit<<=1,++L;
for(int i=0;i<limit;++i)r[i]=((r[i>>1]>>1)|((i&1)<<L-1));
for(int i=0;i<=k;++i){
f[i]=mul(ifac[i],ifac[k-i]);
if(i&1)f[i]=(mod-f[i])%mod;
}
for(int d=0;d<=n*m;++d)if(n*m-k-d>=0)g[d]=mul(ifac[n*m-k-d],ifac[d]);
ntt(f,1),ntt(g,1);
for(int i=0;i<limit;++i)f[i]=mul(f[i],g[i]);ntt(f,-1);
for(int i=0;i<=n*m;++i)f[i]=mul(f[i],mul(fac[i],fac[n*m-i]));
int ans=0;
for(int i=0;i<=n;++i)
for(int j=0;j<=m;++j){
int ct=(n-i)*j+i*(m-j);
if((i+j)&1)sub(ans,mul(f[ct],mul(C(n,i),C(m,j))));
else add(ans,mul(f[ct],mul(C(n,i),C(m,j))));
}
int inv2=(mod+1)/2;
for(int i=1;i<=n+m;++i)ans=mul(ans,inv2);
cout<<ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 4ms
memory: 15480kb
input:
3 5 7
output:
105
result:
ok single line: '105'
Test #2:
score: 5
Accepted
time: 6ms
memory: 15384kb
input:
4 4 8
output:
144
result:
ok single line: '144'
Test #3:
score: 5
Accepted
time: 4ms
memory: 15312kb
input:
9 7 53
output:
11271960
result:
ok single line: '11271960'
Test #4:
score: 5
Accepted
time: 8ms
memory: 14340kb
input:
10 10 60
output:
711797984
result:
ok single line: '711797984'
Test #5:
score: 5
Accepted
time: 12ms
memory: 15268kb
input:
50 100 100
output:
684521374
result:
ok single line: '684521374'
Test #6:
score: 5
Accepted
time: 6ms
memory: 14524kb
input:
69 69 99
output:
205514286
result:
ok single line: '205514286'
Test #7:
score: 5
Accepted
time: 6ms
memory: 13944kb
input:
500 10 3232
output:
571588252
result:
ok single line: '571588252'
Test #8:
score: 5
Accepted
time: 12ms
memory: 14144kb
input:
70 70 4800
output:
851456413
result:
ok single line: '851456413'
Test #9:
score: 5
Accepted
time: 81ms
memory: 21460kb
input:
100 1000 50000
output:
437541409
result:
ok single line: '437541409'
Test #10:
score: 5
Accepted
time: 88ms
memory: 22492kb
input:
316 316 4238
output:
753478761
result:
ok single line: '753478761'
Test #11:
score: 5
Accepted
time: 90ms
memory: 23944kb
input:
201 479 30001
output:
594408179
result:
ok single line: '594408179'
Test #12:
score: 5
Accepted
time: 370ms
memory: 26664kb
input:
706 706 706
output:
835727049
result:
ok single line: '835727049'
Test #13:
score: 5
Accepted
time: 355ms
memory: 28624kb
input:
2023 233 2023
output:
801992885
result:
ok single line: '801992885'
Test #14:
score: 5
Accepted
time: 181ms
memory: 18200kb
input:
402 402 1000
output:
940937548
result:
ok single line: '940937548'
Test #15:
score: 5
Accepted
time: 188ms
memory: 18672kb
input:
707 333 999
output:
732112489
result:
ok single line: '732112489'
Test #16:
score: 5
Accepted
time: 445ms
memory: 29456kb
input:
600 600 18000
output:
579276872
result:
ok single line: '579276872'
Test #17:
score: 5
Accepted
time: 453ms
memory: 27616kb
input:
389 1047 40001
output:
186903191
result:
ok single line: '186903191'
Test #18:
score: 5
Accepted
time: 387ms
memory: 29136kb
input:
707 707 42837
output:
468460621
result:
ok single line: '468460621'
Test #19:
score: 5
Accepted
time: 385ms
memory: 28800kb
input:
100 5000 32346
output:
460579847
result:
ok single line: '460579847'
Test #20:
score: 5
Accepted
time: 155ms
memory: 19252kb
input:
501 501 251001
output:
1
result:
ok single line: '1'