求助 WA
查看原帖
求助 WA
1074583
_Revali_楼主2024/10/10 20:43

record

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD = 1e9 + 7, inv2 = 500000004;
int n, m, l;
ll jc[305], inv[305], dp[305][305];
int fpow(ll a, int b){
	ll mul = 1;
	while(b){
		if(b & 1) mul = a * mul % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return mul;
}
void init(){
	jc[0] = 1;
	for(int i = 1; i <= n; i++)	jc[i] = jc[i - 1] * i % MOD;
	inv[n] = fpow(jc[n], MOD - 2);
	for(int i = n; i >= 1; i--) inv[i - 1] = inv[i] * i % MOD;
}
ll C(int x, int y){
	return jc[x] * inv[y] % MOD * inv[x - y] % MOD;
}
int calc(int l){
	memset(dp, 0, sizeof(dp));
	dp[0][0] = 1;
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= m; j++){
			for(int k = 1; k <= min(i, min(l, j + 1)); k++){ // 链 
				ll ls = jc[k], cl = C(n + k - i - 1, k - 1);
				if(k > 1) ls *= inv2;
				ls %= MOD;
				dp[i][j] += cl * dp[i - k][j - k + 1] % MOD * ls % MOD;
				dp[i][j] %= MOD;
			}
			for(int k = 2; k <= min(i, min(l, j)); k++){ // 环 
				ll sl = jc[k - 1], cl = C(n + k - i - 1, k - 1);
				if(k > 2) sl *= inv2;
				sl %= MOD;
				dp[i][j] += cl * dp[i - k][j - k] % MOD * sl % MOD;
				dp[i][j] %= MOD;
			}
		}
	}
	return dp[n][m];
}
int main(){
	cin >> n >> m >> l;
	init();
	cout << (calc(l) - calc(l - 1)) % MOD;
	return 0;
}
//(n m) = n! * inv[m!] * inv[(n - m)!]
2024/10/10 20:43
加载中...