QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#359520 | #7974. 染色 | C1942huangjiaxu | 100 ✓ | 46ms | 16264kb | C++14 | 1.7kb | 2024-03-20 18:47:42 | 2024-03-20 18:47:42 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1<<19,P=998244353;
int n,m,t,k,fac[N],inv[N],f[N],w[N],A[N],B[N],lim,ans;
int ksm(int x,int y){
int res=1;
for(;y;y>>=1,x=1ll*x*x%P)if(y&1)res=1ll*res*x%P;
return res;
}
void up(int n){
lim=1;
while(lim<=n)lim<<=1;
}
int C(int n,int m){
return 1ll*fac[n]*inv[m]%P*inv[n-m]%P;
}
void init(){
fac[0]=inv[0]=fac[1]=inv[1]=1;
for(int i=2;i<N;++i)fac[i]=1ll*fac[i-1]*i%P,inv[i]=1ll*(P-P/i)*inv[P%i]%P;
for(int i=2;i<N;++i)inv[i]=1ll*inv[i-1]*inv[i]%P;
for(int mid=1,j,o;mid<N;mid<<=1)
for(w[j=mid]=1,o=ksm(3,(P-1)/(mid<<1)),++j;j<mid<<1;++j)w[j]=1ll*w[j-1]*o%P;
t=n*m,up(t);
}
inline int md(int x){
return x>=P?x-P:x;
}
void DFT(int *A){
for(int mid=lim>>1,j,k,*W,*a,*b,Y,R;mid;mid>>=1)
for(j=0,R=mid<<1;j<lim;j+=R)
for(k=0,W=w+mid,a=A+j,b=a+mid;k<mid;++k,++W,++a,++b)
*b=1ll*md(*a+P-(Y=*b))**W%P,*a=md(*a+Y);
}
void IDFT(int *A){
for(int mid=1,j,k,*W,*a,*b,Y,R;mid<lim;mid<<=1)
for(j=0,R=mid<<1;j<lim;j+=R)
for(k=0,W=w+mid,a=A+j,b=a+mid;k<mid;++k,++W,++a,++b)
Y=1ll**b**W%P,*b=md(*a+P-Y),*a=md(*a+Y);
reverse(A+1,A+lim);
for(int in=ksm(lim,P-2),i=0;i<lim;++i)A[i]=1ll*A[i]*in%P;
}
int main(){
scanf("%d%d%d",&n,&m,&k);
init();
for(int i=0;i<=k;++i)A[i]=md(1ll*(i&1?-1:1)*inv[i]*inv[k-i]%P+P);
for(int i=0;i<=t-k;++i)B[i]=1ll*inv[i]*inv[t-k-i]%P;
DFT(A),DFT(B);
for(int i=0;i<lim;++i)A[i]=1ll*A[i]*B[i]%P;
IDFT(A);
for(int i=0;i<=t;++i)f[i]=1ll*A[i]*fac[i]%P*fac[t-i]%P;
for(int i=0;i<=n;++i)for(int j=0;j<=m;++j)
ans=(ans+1ll*(i+j&1?-1:1)*C(n,i)*C(m,j)%P*f[i*(m-j)+j*(n-i)])%P;
ans=1ll*ans*ksm(P+1>>1,n+m)%P;
printf("%d\n",md(ans+P));
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 5ms
memory: 14340kb
input:
3 5 7
output:
105
result:
ok single line: '105'
Test #2:
score: 5
Accepted
time: 6ms
memory: 14936kb
input:
4 4 8
output:
144
result:
ok single line: '144'
Test #3:
score: 5
Accepted
time: 8ms
memory: 14692kb
input:
9 7 53
output:
11271960
result:
ok single line: '11271960'
Test #4:
score: 5
Accepted
time: 8ms
memory: 14700kb
input:
10 10 60
output:
711797984
result:
ok single line: '711797984'
Test #5:
score: 5
Accepted
time: 4ms
memory: 15032kb
input:
50 100 100
output:
684521374
result:
ok single line: '684521374'
Test #6:
score: 5
Accepted
time: 9ms
memory: 14572kb
input:
69 69 99
output:
205514286
result:
ok single line: '205514286'
Test #7:
score: 5
Accepted
time: 5ms
memory: 15584kb
input:
500 10 3232
output:
571588252
result:
ok single line: '571588252'
Test #8:
score: 5
Accepted
time: 9ms
memory: 15656kb
input:
70 70 4800
output:
851456413
result:
ok single line: '851456413'
Test #9:
score: 5
Accepted
time: 16ms
memory: 14876kb
input:
100 1000 50000
output:
437541409
result:
ok single line: '437541409'
Test #10:
score: 5
Accepted
time: 16ms
memory: 15324kb
input:
316 316 4238
output:
753478761
result:
ok single line: '753478761'
Test #11:
score: 5
Accepted
time: 13ms
memory: 16072kb
input:
201 479 30001
output:
594408179
result:
ok single line: '594408179'
Test #12:
score: 5
Accepted
time: 46ms
memory: 16264kb
input:
706 706 706
output:
835727049
result:
ok single line: '835727049'
Test #13:
score: 5
Accepted
time: 46ms
memory: 16212kb
input:
2023 233 2023
output:
801992885
result:
ok single line: '801992885'
Test #14:
score: 5
Accepted
time: 25ms
memory: 16264kb
input:
402 402 1000
output:
940937548
result:
ok single line: '940937548'
Test #15:
score: 5
Accepted
time: 21ms
memory: 15264kb
input:
707 333 999
output:
732112489
result:
ok single line: '732112489'
Test #16:
score: 5
Accepted
time: 45ms
memory: 16196kb
input:
600 600 18000
output:
579276872
result:
ok single line: '579276872'
Test #17:
score: 5
Accepted
time: 45ms
memory: 16132kb
input:
389 1047 40001
output:
186903191
result:
ok single line: '186903191'
Test #18:
score: 5
Accepted
time: 46ms
memory: 16200kb
input:
707 707 42837
output:
468460621
result:
ok single line: '468460621'
Test #19:
score: 5
Accepted
time: 39ms
memory: 16220kb
input:
100 5000 32346
output:
460579847
result:
ok single line: '460579847'
Test #20:
score: 5
Accepted
time: 27ms
memory: 16216kb
input:
501 501 251001
output:
1
result:
ok single line: '1'