QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#840752#9561. 树数叔术juan_123100 ✓95ms29096kbC++142.0kb2025-01-02 23:43:462025-01-02 23:43:47

Judging History

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

  • [2025-01-02 23:43:47]
  • 评测
  • 测评结果:100
  • 用时:95ms
  • 内存:29096kb
  • [2025-01-02 23:43:46]
  • 提交

answer

/*
去逃避
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
int mod,n,v;
int qp(int p,int q){
	int ans =1,pro = p;
	while(q){
		if(q&1)ans = ans*pro%mod;
		pro = pro*pro%mod;q>>=1;
	}
	return ans;
}
int dp[155][155][155],f[155][155];
int jie[10005],inv[10005];
int CC[1005][1005];
int C(int n,int m){if(n<m or m<0)return 0;return CC[n][m];}
signed main(){
	
	cin >> n >> v >> mod;
	CC[0][0]=1;
	for(int i = 1;i<=1000;i++){
		CC[i][0]=CC[i][i]=1;
		for(int j = 1;j<i;j++)CC[i][j] = (CC[i-1][j]+CC[i-1][j-1])%mod;
	}
	if(v>n){cout << 0 << endl;return 0;}
	dp[0][1][0] = 1;
	for(int i = 1;i<=v;i++){
		memset(f,0,sizeof(f));
		for(int j = 0;j<=n;j++){
			for(int l =0;l<=n;l++){
				if(!dp[i-1][j][l])continue;
				for(int k = 0;k+j+l<=n;k++){
					if(!k){
						f[j+k][l] = (f[j+k][l]+dp[i-1][j][l])%mod;
						continue;
					}
					//在树边上加入 k 个点
	//				cout << " " << C(j+l-1+(k-1),k) << endl;
					f[j+k][l] = (f[j+k][l]+dp[i-1][j][l]%mod*C(j+l-1+(k-1),k))%mod;
				}
			}
		}
		//在虚点上插入 k 个点
		for(int j =0;j<=n;j++){
			for(int l=0;l<=n;l++){
				if(!f[j][l])continue;
				for(int k =0;k<=l;k++){
					if(!k){
						dp[i][j][l] = (dp[i][j][l]+f[j][l])%mod;
						continue;
					}
					dp[i][j+k][l-k] = (dp[i][j+k][l-k]+f[j][l]%mod*C(l,k))%mod;
				}
			}
		}
		//什么都没选减掉
		for(int j =0;j<=n;j++)for(int l =0;l<=n;l++){
			if(!dp[i-1][j][l])continue;
			dp[i][j][l] = (dp[i][j][l]-dp[i-1][j][l]+mod)%mod;
			//边上挂一个
			dp[i][j+1][l+1] = (dp[i][j+1][l+1]+dp[i-1][j][l]*(j+l-1))%mod;
			//点上挂一个
			dp[i][j+1][l] = (dp[i][j+1][l]+dp[i-1][j][l]*(j+l))%mod;
		}
	//	for(int j =0;j<=n;j++){
	//		for(int l =0;l<=n;l++){
	//			cout << dp[i][j][l] << " ";
	//		}
	///		cout << endl;
	//	}
	//	cout << "---------" << endl;
	}
	int ans = dp[v][n][0];
	for(int i = 1;i<=n;i++)ans = ans*i%mod;
	cout << ans << endl;
	return 0;
}/*
5 3 998244353
*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 3ms
memory: 11996kb

input:

1 1 624295285

output:

0

result:

ok single line: '0'

Test #2:

score: 5
Accepted
time: 3ms
memory: 12476kb

input:

4 684813415 564954712

output:

0

result:

ok single line: '0'

Test #3:

score: 5
Accepted
time: 3ms
memory: 12756kb

input:

4 2 844826878

output:

24

result:

ok single line: '24'

Test #4:

score: 5
Accepted
time: 4ms
memory: 12832kb

input:

4 17724073 252218682

output:

0

result:

ok single line: '0'

Test #5:

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

input:

4 3 697681963

output:

384

result:

ok single line: '384'

Subtask #2:

score: 15
Accepted

Test #6:

score: 15
Accepted
time: 0ms
memory: 11952kb

input:

6 4 956647977

output:

238320

result:

ok single line: '238320'

Test #7:

score: 15
Accepted
time: 0ms
memory: 12360kb

input:

6 450615260 491361886

output:

0

result:

ok single line: '0'

Test #8:

score: 15
Accepted
time: 3ms
memory: 12028kb

input:

6 5 339344353

output:

933120

result:

ok single line: '933120'

Test #9:

score: 15
Accepted
time: 3ms
memory: 11924kb

input:

6 3 842228619

output:

23760

result:

ok single line: '23760'

Test #10:

score: 15
Accepted
time: 0ms
memory: 12008kb

input:

6 5 331699652

output:

933120

result:

ok single line: '933120'

Subtask #3:

score: 30
Accepted

Test #11:

score: 30
Accepted
time: 2ms
memory: 13204kb

input:

48 26 424594716

output:

362283012

result:

ok single line: '362283012'

Test #12:

score: 30
Accepted
time: 3ms
memory: 11724kb

input:

49 1000000000 738885247

output:

0

result:

ok single line: '0'

Test #13:

score: 30
Accepted
time: 6ms
memory: 13700kb

input:

48 39 688951620

output:

598399200

result:

ok single line: '598399200'

Test #14:

score: 30
Accepted
time: 3ms
memory: 12480kb

input:

50 476039414 292870080

output:

0

result:

ok single line: '0'

Test #15:

score: 30
Accepted
time: 6ms
memory: 14216kb

input:

50 48 245196368

output:

123576912

result:

ok single line: '123576912'

Subtask #4:

score: 50
Accepted

Test #16:

score: 50
Accepted
time: 3ms
memory: 12008kb

input:

150 526250070 197316869

output:

0

result:

ok single line: '0'

Test #17:

score: 50
Accepted
time: 95ms
memory: 26164kb

input:

149 116 671784452

output:

18945228

result:

ok single line: '18945228'

Test #18:

score: 50
Accepted
time: 88ms
memory: 28044kb

input:

146 144 906402626

output:

438777234

result:

ok single line: '438777234'

Test #19:

score: 50
Accepted
time: 94ms
memory: 28208kb

input:

147 143 705666477

output:

70408701

result:

ok single line: '70408701'

Test #20:

score: 50
Accepted
time: 95ms
memory: 29096kb

input:

150 147 453481175

output:

336290325

result:

ok single line: '336290325'