QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#30618 | #977. Local Maxima | wh_ZH# | AC ✓ | 2815ms | 109308kb | C++11 | 1.1kb | 2022-04-30 14:39:57 | 2022-04-30 14:39:59 |
Judging History
answer
#include<bits/stdc++.h>
#define re signed
#define LL long long
inline int read() {
char c=getchar();int x=0;while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-48,c=getchar();return x;
}
const int maxn=3005;
int dp[maxn][maxn],ans,mod,fac[maxn*maxn],ifac[maxn*maxn];
inline int C(int n,int m) {
return m>n?0:1ll*fac[n]*ifac[n-m]%mod*ifac[m]%mod;
}
inline int qm(int x) {return x>=mod?x-mod:x;}
inline int dqm(int x) {return x<0?x+mod:x;}
int n,m;
int main() {
n=read(),m=read(),mod=read();
dp[1][1]=n*m;fac[0]=ifac[0]=ifac[1]=1;
for(re int i=1;i<=n*m;++i)fac[i]=1ll*fac[i-1]*i%mod;
for(re int i=2;i<=n*m;++i)ifac[i]=1ll*(mod-mod/i)*ifac[mod%i]%mod;
for(re int i=2;i<=n*m;++i)ifac[i]=1ll*ifac[i-1]*ifac[i]%mod;
for(re int i=1;i<=n;++i)
for(re int j=1;j<=m;j++) {
if(i==n||j==m) {ans=qm(ans+1ll*dp[i][j]*fac[n*m-i*j]%mod);continue;}
dp[i+1][j]=qm(dp[i+1][j]+1ll*dp[i][j]*j%mod*(n-i)%mod*C(n*m-i*j-1,j-1)%mod*fac[j-1]%mod);
dp[i][j+1]=qm(dp[i][j+1]+1ll*dp[i][j]*i%mod*(m-j)%mod*C(n*m-i*j-1,i-1)%mod*fac[i-1]%mod);
}
printf("%d\n",ans);
return 0;
}
/*
100 100 998244353
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3724kb
input:
2 2 1000000007
output:
16
result:
ok "16"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
4 3 1000000007
output:
95800320
result:
ok "95800320"
Test #3:
score: 0
Accepted
time: 5ms
memory: 4236kb
input:
100 100 998244353
output:
848530760
result:
ok "848530760"
Test #4:
score: 0
Accepted
time: 4ms
memory: 4124kb
input:
79 78 435515903
output:
306910591
result:
ok "306910591"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3992kb
input:
69 74 715090997
output:
611101520
result:
ok "611101520"
Test #6:
score: 0
Accepted
time: 4ms
memory: 4120kb
input:
77 67 221878187
output:
215381310
result:
ok "215381310"
Test #7:
score: 0
Accepted
time: 3ms
memory: 4084kb
input:
70 66 537039721
output:
352526401
result:
ok "352526401"
Test #8:
score: 0
Accepted
time: 2229ms
memory: 93844kb
input:
2952 2408 973899449
output:
400429421
result:
ok "400429421"
Test #9:
score: 0
Accepted
time: 1895ms
memory: 80128kb
input:
2484 2435 713449813
output:
79762013
result:
ok "79762013"
Test #10:
score: 0
Accepted
time: 2524ms
memory: 100892kb
input:
2904 2783 227396761
output:
120446329
result:
ok "120446329"
Test #11:
score: 0
Accepted
time: 2492ms
memory: 95752kb
input:
2654 2908 161249083
output:
100452853
result:
ok "100452853"
Test #12:
score: 0
Accepted
time: 2391ms
memory: 95848kb
input:
2819 2657 722796007
output:
643358934
result:
ok "643358934"
Test #13:
score: 0
Accepted
time: 2815ms
memory: 109308kb
input:
3000 3000 143115311
output:
76718331
result:
ok "76718331"