QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#30618#977. Local Maximawh_ZH#AC ✓2815ms109308kbC++111.1kb2022-04-30 14:39:572022-04-30 14:39:59

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-30 14:39:59]
  • 评测
  • 测评结果:AC
  • 用时:2815ms
  • 内存:109308kb
  • [2022-04-30 14:39:57]
  • 提交

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"