QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#466853#7974. 染色NaCly_Fish100 ✓16ms13704kbC++141.6kb2024-07-08 11:06:042024-07-08 11:06:05

Judging History

你现在查看的是最新测评结果

  • [2024-07-08 11:06:05]
  • 评测
  • 测评结果:100
  • 用时:16ms
  • 内存:13704kb
  • [2024-07-08 11:06:04]
  • 提交

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'