QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#288206 | #7974. 染色 | grass8cow | 100 ✓ | 204ms | 36664kb | C++17 | 1.8kb | 2023-12-22 10:40:59 | 2023-12-22 10:41:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,m,K;
const int mod=998244353,N=(1<<20),inv2=(mod+1)/2,G=3,GI=(mod+1)/3;
int qpow(int a,int b){
int c=1;
for(;b;b>>=1){
if(b&1)c=1ll*a*c%mod;
a=1ll*a*a%mod;
}
return c;
}
int jc[N+10],ij[N+10],p2[N+10],i2[N+10];
int C(int a,int b){
if(a<b||a<0||b<0)return 0;
return 1ll*jc[a]*ij[b]%mod*ij[a-b]%mod;
}
int lb[N],L;
void init(int n){
L=1;while(L<=n)L<<=1;
for(int i=0;i<L;i++)lb[i]=(lb[i>>1]>>1)|((i&1)?(L>>1):0);
}
void NTT(int *a,int fl){
for(int i=0;i<L;i++)if(i>lb[i])swap(a[i],a[lb[i]]);
for(int o=1;o<L;o<<=1){
int Wn=qpow(fl?G:GI,(mod-1)/(o<<1));
for(int i=0;i<L;i+=(o<<1))for(int j=0,w=1;j<o;j++,w=1ll*w*Wn%mod){
int x=a[i+j],y=1ll*w*a[i+j+o]%mod;
a[i+j]=(x+y)%mod,a[i+j+o]=(x-y)%mod;
}
}
if(!fl){
int I=qpow(L,mod-2);
for(int i=0;i<L;i++)a[i]=1ll*a[i]*I%mod;
}
}
void sieve(){
jc[0]=p2[0]=i2[0]=1;
for(int i=1;i<=N;i++)p2[i]=2*p2[i-1]%mod,i2[i]=1ll*inv2*i2[i-1]%mod,
jc[i]=1ll*i*jc[i-1]%mod;
ij[N]=qpow(jc[N],mod-2);
for(int i=N;i;i--)ij[i-1]=1ll*i*ij[i]%mod;
}
int fp[N+10],g[N+10],f[N+10];
int main(){
sieve();
scanf("%d%d%d",&n,&m,&K);
int ans=0,O=n*m;
init(O*2);
for(int i=0;i<=K;i++)f[i]=((i&1)?-1ll:1ll)*ij[i]*ij[K-i]%mod;
for(int i=0;i<=O-K;i++)g[i]=1ll*ij[i]*ij[O-K-i]%mod;
NTT(f,1),NTT(g,1);for(int i=0;i<L;i++)f[i]=1ll*f[i]*g[i]%mod;
NTT(f,0);
for(int e=0;e<=O;e++)fp[e]=1ll*jc[e]*jc[O-e]%mod*f[e]%mod;
/*for(int e=0;e<=O;e++)
for(int i=0;i<=min(e,K);i++)
(fp[e]+=((i&1)?-1ll:1ll)*jc[e]*ij[i]*ij[e-i]*jc[O-e]*ij[K-i]*ij[O-e-K+i]%mod)%=mod;*/
for(int x=0;x<=n;x++)for(int y=0;y<=m;y++){
int e=x*(m-y)+y*(n-x);
(ans+=(((x+y)&1)?-1ll:1ll)*C(n,x)*C(m,y)%mod*fp[e]%mod)%=mod;
}
return printf("%d",(1ll*ans*i2[n+m]%mod+mod)%mod),0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 8ms
memory: 27004kb
input:
3 5 7
output:
105
result:
ok single line: '105'
Test #2:
score: 5
Accepted
time: 8ms
memory: 28256kb
input:
4 4 8
output:
144
result:
ok single line: '144'
Test #3:
score: 5
Accepted
time: 12ms
memory: 26844kb
input:
9 7 53
output:
11271960
result:
ok single line: '11271960'
Test #4:
score: 5
Accepted
time: 8ms
memory: 27928kb
input:
10 10 60
output:
711797984
result:
ok single line: '711797984'
Test #5:
score: 5
Accepted
time: 9ms
memory: 26696kb
input:
50 100 100
output:
684521374
result:
ok single line: '684521374'
Test #6:
score: 5
Accepted
time: 10ms
memory: 27424kb
input:
69 69 99
output:
205514286
result:
ok single line: '205514286'
Test #7:
score: 5
Accepted
time: 10ms
memory: 26408kb
input:
500 10 3232
output:
571588252
result:
ok single line: '571588252'
Test #8:
score: 5
Accepted
time: 14ms
memory: 27604kb
input:
70 70 4800
output:
851456413
result:
ok single line: '851456413'
Test #9:
score: 5
Accepted
time: 53ms
memory: 27420kb
input:
100 1000 50000
output:
437541409
result:
ok single line: '437541409'
Test #10:
score: 5
Accepted
time: 48ms
memory: 35452kb
input:
316 316 4238
output:
753478761
result:
ok single line: '753478761'
Test #11:
score: 5
Accepted
time: 50ms
memory: 27760kb
input:
201 479 30001
output:
594408179
result:
ok single line: '594408179'
Test #12:
score: 5
Accepted
time: 194ms
memory: 36648kb
input:
706 706 706
output:
835727049
result:
ok single line: '835727049'
Test #13:
score: 5
Accepted
time: 202ms
memory: 36620kb
input:
2023 233 2023
output:
801992885
result:
ok single line: '801992885'
Test #14:
score: 5
Accepted
time: 93ms
memory: 32180kb
input:
402 402 1000
output:
940937548
result:
ok single line: '940937548'
Test #15:
score: 5
Accepted
time: 91ms
memory: 36388kb
input:
707 333 999
output:
732112489
result:
ok single line: '732112489'
Test #16:
score: 5
Accepted
time: 193ms
memory: 36580kb
input:
600 600 18000
output:
579276872
result:
ok single line: '579276872'
Test #17:
score: 5
Accepted
time: 199ms
memory: 36664kb
input:
389 1047 40001
output:
186903191
result:
ok single line: '186903191'
Test #18:
score: 5
Accepted
time: 204ms
memory: 36432kb
input:
707 707 42837
output:
468460621
result:
ok single line: '468460621'
Test #19:
score: 5
Accepted
time: 190ms
memory: 34460kb
input:
100 5000 32346
output:
460579847
result:
ok single line: '460579847'
Test #20:
score: 5
Accepted
time: 98ms
memory: 31864kb
input:
501 501 251001
output:
1
result:
ok single line: '1'