QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#716998#9561. 树数叔术thomaswmy0 566ms4104kbC++141.1kb2024-11-06 16:35:382024-11-06 16:35:38

Judging History

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

  • [2024-11-06 16:35:38]
  • 评测
  • 测评结果:0
  • 用时:566ms
  • 内存:4104kb
  • [2024-11-06 16:35:38]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N=160;
typedef long long ll;

int qpow(int x,ll y,int p) {
	int z=1;
	for(;y;y>>=1) {
		if(y&1) z=1ll*z*x%p;
		x=1ll*x*x%p;
	}
	return z;
}

int n,V,Mod;
int fac[N],inv[N];
int f[2][N][N];

int C(int x,int y) {
	if(x<y || y<0) return 0;
	return 1ll*fac[x]*inv[y]%Mod*inv[x-y]%Mod;
}

int main() {
	scanf("%d%d%d",&n,&V,&Mod);
	if(V>=n) {
		printf("0");
		return 0;
	}
	fac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%Mod;
	inv[n]=qpow(fac[n],Mod-2,Mod);
	for(int i=n-1;i>=0;i--) inv[i]=1ll*inv[i+1]*(i+1)%Mod;
	int now=0;
	f[0][1][1]=n;
	for(int i=1;i<=V;i++) {
		for(int j=1;j<=n;j++) for(int k=1;k<=j;k++) f[now^1][j][k]=0;
		for(int j=1;j<=n;j++) {
			for(int k=1;k<=j;k++) {
				if(!f[now][j][k]) continue;
				for(int p=k+1;p<=j;p++) {
					f[now^1][j][p]=(f[now^1][j][p]+1ll*f[now][j][k]*C(j-k,j-p)%Mod)%Mod;
				}
				for(int p=j+1;p<=n;p++) {
					f[now^1][p][k+1]=(f[now^1][p][k+1]+1ll*f[now][j][k]*C(n-j,n-p)%Mod*fac[p-j]%Mod*j%Mod)%Mod;
				}
			}
		}
		now^=1;
	}
	printf("%d",f[now][n][n]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 5
Accepted
time: 0ms
memory: 3888kb

input:

1 1 624295285

output:

0

result:

ok single line: '0'

Test #2:

score: 5
Accepted
time: 0ms
memory: 3832kb

input:

4 684813415 564954712

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Wrong Answer
time: 0ms
memory: 3824kb

input:

4 2 844826878

output:

410169168

result:

wrong answer 1st lines differ - expected: '24', found: '410169168'

Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 0ms
memory: 3960kb

input:

6 4 956647977

output:

618062190

result:

wrong answer 1st lines differ - expected: '238320', found: '618062190'

Subtask #3:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 3ms
memory: 3908kb

input:

48 26 424594716

output:

421956444

result:

wrong answer 1st lines differ - expected: '362283012', found: '421956444'

Subtask #4:

score: 0
Wrong Answer

Test #16:

score: 50
Accepted
time: 0ms
memory: 3840kb

input:

150 526250070 197316869

output:

0

result:

ok single line: '0'

Test #17:

score: 0
Wrong Answer
time: 566ms
memory: 4104kb

input:

149 116 671784452

output:

595286328

result:

wrong answer 1st lines differ - expected: '18945228', found: '595286328'