QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#35659#977. Local MaximaFroggyguaAC ✓2302ms109868kbC++17939b2022-06-17 20:45:242022-06-17 20:45:26

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-06-17 20:45:26]
  • 评测
  • 测评结果:AC
  • 用时:2302ms
  • 内存:109868kb
  • [2022-06-17 20:45:24]
  • 提交

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"