QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#466853 | #7974. 染色 | NaCly_Fish | 100 ✓ | 16ms | 13704kb | C++14 | 1.6kb | 2024-07-08 11:06:04 | 2024-07-08 11:06:05 |
Judging History
answer
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 500007
#define ll long long
#define p 998244353
using namespace std;
inline int power(int a,int t){
int res = 1;
while(t){
if(t&1) res = (ll)res*a%p;
a = (ll)a*a%p;
t >>= 1;
}
return res;
}
int inv[N],fac[N],ifac[N];
void init(int n){
inv[1] = fac[0] = fac[1] = ifac[0] = 1;
for(int i=2;i<=n;++i) fac[i] = (ll)fac[i-1]*i%p;
ifac[n] = power(fac[n],p-2);
for(int i=n-1;i;--i) ifac[i] = (ll)ifac[i+1]*(i+1)%p;
for(int i=2;i<=n;++i) inv[i] = (ll)fac[i-1]*ifac[i]%p;
}
inline int binom(int n,int m){
if(n<m) return 0;
return (ll)fac[n]*ifac[m]%p*ifac[n-m]%p;
}
void solve(int n,int k,int *h){
h[0] = binom(n,k);
h[1] = -2*binom(n-1,n-k)%p;
for(int i=2;i<=n;++i)
h[i] = -((ll)(i-2)*h[i-2] - (ll)(1-2*k+n)*h[i-1])%p*inv[n+1-i]%p;
for(int i=1;i<=n;++i) h[i] = (h[i]+h[i-1])%p;
}
int n,m,k;
int f[N],g[N];
int main(){
scanf("%d%d%d",&n,&m,&k);
init(n*m+1);
int t,bm = 1;
g[0] = (m&1)?-1:1;
for(int i=0;i<m;++i) g[i+1] = (ll)g[i]*(i-m)%p*inv[i+1]%p;
for(int i=0;i<=n;++i){
for(int j=0;j<=m;++j){
t = i*j+(n-i)*(m-j);
f[t] = (f[t] + (ll)bm*g[j])%p;
}
bm = (ll)bm*(i-n)%p*inv[i+1]%p;
}
solve(n*m,k,g);
int ans = 0;
for(int i=0;i<=n*m;++i) ans = (ans + (ll)f[i]*g[i])%p;
ans = (ll)ans*power(2,p-n-m-1)%p;
printf("%d",(ans+p)%p);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 1ms
memory: 9872kb
input:
3 5 7
output:
105
result:
ok single line: '105'
Test #2:
score: 5
Accepted
time: 1ms
memory: 10024kb
input:
4 4 8
output:
144
result:
ok single line: '144'
Test #3:
score: 5
Accepted
time: 0ms
memory: 10016kb
input:
9 7 53
output:
11271960
result:
ok single line: '11271960'
Test #4:
score: 5
Accepted
time: 0ms
memory: 10008kb
input:
10 10 60
output:
711797984
result:
ok single line: '711797984'
Test #5:
score: 5
Accepted
time: 1ms
memory: 8108kb
input:
50 100 100
output:
684521374
result:
ok single line: '684521374'
Test #6:
score: 5
Accepted
time: 2ms
memory: 9984kb
input:
69 69 99
output:
205514286
result:
ok single line: '205514286'
Test #7:
score: 5
Accepted
time: 0ms
memory: 9872kb
input:
500 10 3232
output:
571588252
result:
ok single line: '571588252'
Test #8:
score: 5
Accepted
time: 0ms
memory: 9980kb
input:
70 70 4800
output:
851456413
result:
ok single line: '851456413'
Test #9:
score: 5
Accepted
time: 2ms
memory: 10648kb
input:
100 1000 50000
output:
437541409
result:
ok single line: '437541409'
Test #10:
score: 5
Accepted
time: 4ms
memory: 10792kb
input:
316 316 4238
output:
753478761
result:
ok single line: '753478761'
Test #11:
score: 5
Accepted
time: 4ms
memory: 10844kb
input:
201 479 30001
output:
594408179
result:
ok single line: '594408179'
Test #12:
score: 5
Accepted
time: 12ms
memory: 13620kb
input:
706 706 706
output:
835727049
result:
ok single line: '835727049'
Test #13:
score: 5
Accepted
time: 11ms
memory: 13424kb
input:
2023 233 2023
output:
801992885
result:
ok single line: '801992885'
Test #14:
score: 5
Accepted
time: 6ms
memory: 11124kb
input:
402 402 1000
output:
940937548
result:
ok single line: '940937548'
Test #15:
score: 5
Accepted
time: 0ms
memory: 11480kb
input:
707 333 999
output:
732112489
result:
ok single line: '732112489'
Test #16:
score: 5
Accepted
time: 11ms
memory: 12456kb
input:
600 600 18000
output:
579276872
result:
ok single line: '579276872'
Test #17:
score: 5
Accepted
time: 13ms
memory: 13268kb
input:
389 1047 40001
output:
186903191
result:
ok single line: '186903191'
Test #18:
score: 5
Accepted
time: 16ms
memory: 13704kb
input:
707 707 42837
output:
468460621
result:
ok single line: '468460621'
Test #19:
score: 5
Accepted
time: 16ms
memory: 13624kb
input:
100 5000 32346
output:
460579847
result:
ok single line: '460579847'
Test #20:
score: 5
Accepted
time: 2ms
memory: 12048kb
input:
501 501 251001
output:
1
result:
ok single line: '1'