QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#430090#977. Local Maximagrass8cow#AC ✓573ms109628kbC++17824b2024-06-03 13:59:042024-06-03 13:59:04

Judging History

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

  • [2024-06-03 13:59:04]
  • 评测
  • 测评结果:AC
  • 用时:573ms
  • 内存:109628kb
  • [2024-06-03 13:59:04]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,m,jc[9010000],ij[9001000],mod;
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 dp[3010][3010];
int O(int a,int b){return 1ll*jc[a]*ij[a-b]%mod;}
void ad(int &x,int y){x+=y;if(x>=mod)x-=mod;}
int main(){
    scanf("%d%d%d",&n,&m,&mod);jc[0]=1;
    for(int i=1;i<=n*m;i++)jc[i]=1ll*i*jc[i-1]%mod;
    ij[n*m]=qpow(jc[n*m],mod-2);for(int i=n*m;i;i--)ij[i-1]=1ll*i*ij[i]%mod;
    dp[1][1]=1;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        if(j<m)(dp[i][j+1]+=1ll*dp[i][j]*O(n*m-i*j-1,i-1)%mod*i%mod)%=mod;
        if(i<n)(dp[i+1][j]+=1ll*dp[i][j]*O(n*m-i*j-1,j-1)%mod*j%mod)%=mod;
    }
    printf("%lld\n",1ll*dp[n][m]*jc[n]%mod*jc[m]%mod);
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 8020kb

input:

2 2 1000000007

output:

16

result:

ok "16"

Test #2:

score: 0
Accepted
time: 0ms
memory: 8048kb

input:

4 3 1000000007

output:

95800320

result:

ok "95800320"

Test #3:

score: 0
Accepted
time: 0ms
memory: 8328kb

input:

100 100 998244353

output:

848530760

result:

ok "848530760"

Test #4:

score: 0
Accepted
time: 2ms
memory: 8368kb

input:

79 78 435515903

output:

306910591

result:

ok "306910591"

Test #5:

score: 0
Accepted
time: 0ms
memory: 8268kb

input:

69 74 715090997

output:

611101520

result:

ok "611101520"

Test #6:

score: 0
Accepted
time: 2ms
memory: 8340kb

input:

77 67 221878187

output:

215381310

result:

ok "215381310"

Test #7:

score: 0
Accepted
time: 2ms
memory: 8368kb

input:

70 66 537039721

output:

352526401

result:

ok "352526401"

Test #8:

score: 0
Accepted
time: 347ms
memory: 99676kb

input:

2952 2408 973899449

output:

400429421

result:

ok "400429421"

Test #9:

score: 0
Accepted
time: 289ms
memory: 82276kb

input:

2484 2435 713449813

output:

79762013

result:

ok "79762013"

Test #10:

score: 0
Accepted
time: 409ms
memory: 107528kb

input:

2904 2783 227396761

output:

120446329

result:

ok "120446329"

Test #11:

score: 0
Accepted
time: 417ms
memory: 98572kb

input:

2654 2908 161249083

output:

100452853

result:

ok "100452853"

Test #12:

score: 0
Accepted
time: 405ms
memory: 100616kb

input:

2819 2657 722796007

output:

643358934

result:

ok "643358934"

Test #13:

score: 0
Accepted
time: 573ms
memory: 109628kb

input:

3000 3000 143115311

output:

76718331

result:

ok "76718331"