QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#430090 | #977. Local Maxima | grass8cow# | AC ✓ | 573ms | 109628kb | C++17 | 824b | 2024-06-03 13:59:04 | 2024-06-03 13:59:04 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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"