QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#305986 | #7974. 染色 | JohnAlfnov | 100 ✓ | 119ms | 29532kb | C++14 | 1.8kb | 2024-01-16 07:52:36 | 2024-01-16 07:52:36 |
Judging History
answer
#include<bits/stdc++.h>
#define mod 998244353
#define en 499122177
using namespace std;
int di[500005],id[500005];
int powdv(int x,int y=mod-2){
int ans=1;
while(y){
if(y&1)ans=1ll*ans*x%mod;
y>>=1,x=1ll*x*x%mod;
}
return ans;
}
int C(int n,int m){
if(n<0||m<0||n<m)return 0;
return 1ll*di[n]*id[m]%mod*id[n-m]%mod;
}
int a[1<<21],ap[1<<21];
int b[1<<21],bp[1<<21];
int rev[1<<21];
void ntt(int l,int *c,int *d,int gs){
for(int i=0;i<(1<<l);++i)d[rev[i]]=c[i];
for(int i=1;i<(1<<l);i<<=1){
int o1=powdv(3,(mod-1)/i/2);
if(gs==-1)o1=powdv(o1);
for(int j=0;j<(1<<l);j+=i+i){
int o=1;
for(int k=j;k<j+i;++k){
int A=d[k],B=d[k+i];
d[k]=(A+1ll*o*B)%mod,d[k+i]=(A-1ll*o*B)%mod;
o=1ll*o*o1%mod;
}
}
}
if(gs==-1){
int cj=1;
for(int i=1;i<=l;++i)cj=1ll*cj*en%mod;
for(int i=0;i<(1<<l);++i)d[i]=1ll*d[i]*cj%mod;
}
}
int sc[500005];
int main(){
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
int N=n*m;
di[0]=1;
for(int i=1;i<=N;++i)di[i]=1ll*i*di[i-1]%mod;
id[N]=powdv(di[N]);
for(int i=N-1;i>=0;--i)id[i]=1ll*id[i+1]*(i+1)%mod;
for(int i=0;i<=k;++i)a[i]=1ll*(i%2==0?1:-1)*id[i]*id[k-i]%mod;
for(int i=0;i<=N-k;++i)b[i]=1ll*id[i]*id[N-k-i]%mod;
int cd=N+1;
while(cd&(cd-1))++cd;
int l=__builtin_ctz(cd);
for(int i=0;i<(1<<l);++i){
for(int j=0;j<l;++j)if(i&(1<<j))rev[i]^=1<<(l-j-1);
}
ntt(l,a,ap,1);
ntt(l,b,bp,1);
for(int i=0;i<(1<<l);++i)ap[i]=1ll*ap[i]*bp[i]%mod;
ntt(l,ap,a,-1);
for(int i=0;i<=N;++i)sc[i]=1ll*a[i]*di[i]%mod*di[N-i]%mod;
int ans=0;
for(int s=0;s<=n;++s)for(int t=0;t<=m;++t){
int xs=1ll*((s+t)%2==0?1:-1)*C(n,s)*C(m,t)%mod;
int gs=s*m+t*n-2*s*t;
ans=(ans+1ll*xs*sc[gs])%mod;
}
for(int i=1;i<=n+m;++i)ans=1ll*ans*en%mod;
ans=(ans+mod)%mod;
printf("%d\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 0ms
memory: 18304kb
input:
3 5 7
output:
105
result:
ok single line: '105'
Test #2:
score: 5
Accepted
time: 3ms
memory: 18244kb
input:
4 4 8
output:
144
result:
ok single line: '144'
Test #3:
score: 5
Accepted
time: 0ms
memory: 16200kb
input:
9 7 53
output:
11271960
result:
ok single line: '11271960'
Test #4:
score: 5
Accepted
time: 2ms
memory: 18248kb
input:
10 10 60
output:
711797984
result:
ok single line: '711797984'
Test #5:
score: 5
Accepted
time: 0ms
memory: 18312kb
input:
50 100 100
output:
684521374
result:
ok single line: '684521374'
Test #6:
score: 5
Accepted
time: 0ms
memory: 18312kb
input:
69 69 99
output:
205514286
result:
ok single line: '205514286'
Test #7:
score: 5
Accepted
time: 3ms
memory: 18128kb
input:
500 10 3232
output:
571588252
result:
ok single line: '571588252'
Test #8:
score: 5
Accepted
time: 3ms
memory: 18248kb
input:
70 70 4800
output:
851456413
result:
ok single line: '851456413'
Test #9:
score: 5
Accepted
time: 29ms
memory: 28728kb
input:
100 1000 50000
output:
437541409
result:
ok single line: '437541409'
Test #10:
score: 5
Accepted
time: 29ms
memory: 26860kb
input:
316 316 4238
output:
753478761
result:
ok single line: '753478761'
Test #11:
score: 5
Accepted
time: 28ms
memory: 18616kb
input:
201 479 30001
output:
594408179
result:
ok single line: '594408179'
Test #12:
score: 5
Accepted
time: 115ms
memory: 29532kb
input:
706 706 706
output:
835727049
result:
ok single line: '835727049'
Test #13:
score: 5
Accepted
time: 118ms
memory: 29148kb
input:
2023 233 2023
output:
801992885
result:
ok single line: '801992885'
Test #14:
score: 5
Accepted
time: 52ms
memory: 18812kb
input:
402 402 1000
output:
940937548
result:
ok single line: '940937548'
Test #15:
score: 5
Accepted
time: 53ms
memory: 19028kb
input:
707 333 999
output:
732112489
result:
ok single line: '732112489'
Test #16:
score: 5
Accepted
time: 117ms
memory: 25268kb
input:
600 600 18000
output:
579276872
result:
ok single line: '579276872'
Test #17:
score: 5
Accepted
time: 118ms
memory: 25532kb
input:
389 1047 40001
output:
186903191
result:
ok single line: '186903191'
Test #18:
score: 5
Accepted
time: 115ms
memory: 28800kb
input:
707 707 42837
output:
468460621
result:
ok single line: '468460621'
Test #19:
score: 5
Accepted
time: 119ms
memory: 29308kb
input:
100 5000 32346
output:
460579847
result:
ok single line: '460579847'
Test #20:
score: 5
Accepted
time: 57ms
memory: 19144kb
input:
501 501 251001
output:
1
result:
ok single line: '1'