QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#806770 | #7974. 染色 | JohnAlfnov | 100 ✓ | 15ms | 13616kb | C++14 | 1.1kb | 2024-12-09 14:59:56 | 2024-12-09 14:59:58 |
Judging History
answer
#include<bits/stdc++.h>
#define mod 998244353
using namespace std;
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 di[500005],id[500005];
inline int C(int n,int m){
return 1ll*di[n]*id[m]%mod*id[n-m]%mod;
}
inline int CC(int n,int m){
return 1ll*di[m]*di[n-m]%mod;
}
int A[500005],B[500005],an[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;
an[0]=1;an[1]=(N-2*k+mod)%mod;
for(int n=1;n<N;++n){
an[n+1]=(1ll*an[1]*an[n]+(n-N-1ll+mod)*an[n-1])%mod*di[n]%mod*id[n+1]%mod;
}
int C2=1ll*id[k]*id[N-k]%mod;
for(int i=0;i<=N;++i)an[i]=1ll*CC(N,i)*an[i]%mod;
for(int a=0;a<=n;++a)A[a]=a%2?mod-C(n,a):C(n,a);
for(int b=0;b<=m;++b)B[b]=b%2?mod-C(m,b):C(m,b);
int he=0;
for(int a=0;a<=n;++a)for(int b=0;b<=m;++b){
he=(he+1ll*A[a]*B[b]%mod*an[a*(m-b)+b*(n-a)])%mod;
}
int ans=1ll*he*C2%mod*powdv((mod+1)/2,n+m)%mod;
printf("%d\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 5
Accepted
time: 1ms
memory: 10036kb
input:
3 5 7
output:
105
result:
ok single line: '105'
Test #2:
score: 5
Accepted
time: 0ms
memory: 11924kb
input:
4 4 8
output:
144
result:
ok single line: '144'
Test #3:
score: 5
Accepted
time: 2ms
memory: 11984kb
input:
9 7 53
output:
11271960
result:
ok single line: '11271960'
Test #4:
score: 5
Accepted
time: 0ms
memory: 11928kb
input:
10 10 60
output:
711797984
result:
ok single line: '711797984'
Test #5:
score: 5
Accepted
time: 2ms
memory: 11996kb
input:
50 100 100
output:
684521374
result:
ok single line: '684521374'
Test #6:
score: 5
Accepted
time: 0ms
memory: 9984kb
input:
69 69 99
output:
205514286
result:
ok single line: '205514286'
Test #7:
score: 5
Accepted
time: 0ms
memory: 9900kb
input:
500 10 3232
output:
571588252
result:
ok single line: '571588252'
Test #8:
score: 5
Accepted
time: 0ms
memory: 12072kb
input:
70 70 4800
output:
851456413
result:
ok single line: '851456413'
Test #9:
score: 5
Accepted
time: 5ms
memory: 12336kb
input:
100 1000 50000
output:
437541409
result:
ok single line: '437541409'
Test #10:
score: 5
Accepted
time: 4ms
memory: 12400kb
input:
316 316 4238
output:
753478761
result:
ok single line: '753478761'
Test #11:
score: 5
Accepted
time: 4ms
memory: 12488kb
input:
201 479 30001
output:
594408179
result:
ok single line: '594408179'
Test #12:
score: 5
Accepted
time: 12ms
memory: 13616kb
input:
706 706 706
output:
835727049
result:
ok single line: '835727049'
Test #13:
score: 5
Accepted
time: 15ms
memory: 13440kb
input:
2023 233 2023
output:
801992885
result:
ok single line: '801992885'
Test #14:
score: 5
Accepted
time: 6ms
memory: 12552kb
input:
402 402 1000
output:
940937548
result:
ok single line: '940937548'
Test #15:
score: 5
Accepted
time: 5ms
memory: 11848kb
input:
707 333 999
output:
732112489
result:
ok single line: '732112489'
Test #16:
score: 5
Accepted
time: 7ms
memory: 12448kb
input:
600 600 18000
output:
579276872
result:
ok single line: '579276872'
Test #17:
score: 5
Accepted
time: 13ms
memory: 13248kb
input:
389 1047 40001
output:
186903191
result:
ok single line: '186903191'
Test #18:
score: 5
Accepted
time: 7ms
memory: 13616kb
input:
707 707 42837
output:
468460621
result:
ok single line: '468460621'
Test #19:
score: 5
Accepted
time: 15ms
memory: 13500kb
input:
100 5000 32346
output:
460579847
result:
ok single line: '460579847'
Test #20:
score: 5
Accepted
time: 4ms
memory: 12640kb
input:
501 501 251001
output:
1
result:
ok single line: '1'