QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#35659 | #977. Local Maxima | Froggygua | AC ✓ | 2302ms | 109868kb | C++17 | 939b | 2022-06-17 20:45:24 | 2022-06-17 20:45:26 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define N 3020
typedef long long ll;
int n,m,mod,fac[N*N],ifac[N*N],dp[N][N];
inline void add(int &x,int y){(x+=y)>=mod?x-=mod:233;}
int qpow(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1LL*ans*a%mod;
a=1LL*a*a%mod;
b>>=1;
}
return ans;
}
void init(int n){
fac[0]=1;
for(int i=1;i<=n;++i){
fac[i]=1LL*fac[i-1]*i%mod;
}
ifac[n]=qpow(fac[n],mod-2);
for(int i=n-1;i>=0;--i){
ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
}
}
inline int C(int n,int m){
return 1LL*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>mod;
init(n*m);
dp[1][1]=n*m;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
add(dp[i+1][j],1LL*dp[i][j]*C(n*m-i*j-1,j-1)%mod*fac[j]%mod*(n-i)%mod);
add(dp[i][j+1],1LL*dp[i][j]*C(n*m-i*j-1,i-1)%mod*fac[i]%mod*(m-j)%mod);
}
}
cout<<dp[n][m]<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7748kb
input:
2 2 1000000007
output:
16
result:
ok "16"
Test #2:
score: 0
Accepted
time: 0ms
memory: 7688kb
input:
4 3 1000000007
output:
95800320
result:
ok "95800320"
Test #3:
score: 0
Accepted
time: 2ms
memory: 8128kb
input:
100 100 998244353
output:
848530760
result:
ok "848530760"
Test #4:
score: 0
Accepted
time: 2ms
memory: 9788kb
input:
79 78 435515903
output:
306910591
result:
ok "306910591"
Test #5:
score: 0
Accepted
time: 4ms
memory: 8108kb
input:
69 74 715090997
output:
611101520
result:
ok "611101520"
Test #6:
score: 0
Accepted
time: 2ms
memory: 9916kb
input:
77 67 221878187
output:
215381310
result:
ok "215381310"
Test #7:
score: 0
Accepted
time: 0ms
memory: 10048kb
input:
70 66 537039721
output:
352526401
result:
ok "352526401"
Test #8:
score: 0
Accepted
time: 1688ms
memory: 94680kb
input:
2952 2408 973899449
output:
400429421
result:
ok "400429421"
Test #9:
score: 0
Accepted
time: 1386ms
memory: 80244kb
input:
2484 2435 713449813
output:
79762013
result:
ok "79762013"
Test #10:
score: 0
Accepted
time: 2024ms
memory: 102648kb
input:
2904 2783 227396761
output:
120446329
result:
ok "120446329"
Test #11:
score: 0
Accepted
time: 1970ms
memory: 95836kb
input:
2654 2908 161249083
output:
100452853
result:
ok "100452853"
Test #12:
score: 0
Accepted
time: 1911ms
memory: 96604kb
input:
2819 2657 722796007
output:
643358934
result:
ok "643358934"
Test #13:
score: 0
Accepted
time: 2302ms
memory: 109868kb
input:
3000 3000 143115311
output:
76718331
result:
ok "76718331"