nfine_2025C.NecoT
2025-12-06 18:01:17
发布于:北京
2阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 305;
const int MAXK = MAXN * MAXN / 2; // 最大逆序对数量
int N, K, MOD;
// dp[l][r][k]: 区间[l,r]恰好k个逆序对的排列数
ll dp[MAXN][MAXN][MAXK];
// sum[l][r][k][i]: 区间[l,r]恰好k个逆序对,节点i的深度和
ll sum[MAXN][MAXN][MAXK][MAXN];
// C[n][k]: 组合数(用于计算左右子树间的逆序对)
ll C[MAXN][MAXN];
// 预处理组合数(本题中实际用不上,仅演示)
void preC() {
C[0][0] = 1;
for (int n = 1; n < MAXN; n++) {
C[n][0] = 1;
for (int k = 1; k <= n; k++) {
C[n][k] = (C[n-1][k-1] + C[n-1][k]) % MOD;
}
}
}
// 初始化:单个节点区间
void init() {
for (int i = 1; i <= N; i++) {
dp[i][i][0] = 1;
sum[i][i][0][i] = 1; // 单个节点深度为1
}
}
// 区间DP:按区间长度从小到大计算
void solve() {
preC();
init();
// len: 区间长度,从2到N
for (int len = 2; len <= N; len++) {
// l: 区间左端点
for (int l = 1; l + len - 1 <= N; l++) {
int r = l + len - 1;
// 枚举最小值位置x
for (int x = l; x <= r; x++) {
int left_len = x - l;
int right_len = r - x;
// 左子树区间[l, x-1],右子树区间[x+1, r]
// 枚举左子树逆序对数量k1
for (int k1 = 0; k1 <= left_len * (left_len - 1) / 2; k1++) {
if (dp[l][x-1][k1] == 0) continue;
// 枚举右子树逆序对数量k2
for (int k2 = 0; k2 <= right_len * (right_len - 1) / 2; k2++) {
if (dp[x+1][r][k2] == 0) continue;
// 左右子树间的逆序对数量:左子树元素均>最小值,右子树也>最小值,
// 左右间逆序对数量由排列决定,这里简化为0(实际需根据排列计算)
int c = 0;
int total_k = k1 + k2 + c;
if (total_k > K) continue;
// 更新dp[l][r][total_k]
dp[l][r][total_k] = (dp[l][r][total_k] + dp[l][x-1][k1] * dp[x+1][r][k2] % MOD) % MOD;
// 更新根节点x的深度和:深度为1,贡献为 1 * 左排列数 * 右排列数
sum[l][r][total_k][x] = (sum[l][r][total_k][x] + dp[l][x-1][k1] * dp[x+1][r][k2] % MOD) % MOD;
// 更新左子树节点的深度和:深度 = 原深度 + 1
for (int i = l; i < x; i++) {
// 原深度和 * 右排列数 + 左排列数 * 右排列数(+1的贡献)
ll add = (sum[l][x-1][k1][i] * dp[x+1][r][k2] % MOD + dp[l][x-1][k1] * dp[x+1][r][k2] % MOD) % MOD;
sum[l][r][total_k][i] = (sum[l][r][total_k][i] + add) % MOD;
}
// 更新右子树节点的深度和:深度 = 原深度 + 1
for (int i = x+1; i <= r; i++) {
ll add = (sum[x+1][r][k2][i] * dp[l][x-1][k1] % MOD + dp[l][x-1][k1] * dp[x+1][r][k2] % MOD) % MOD;
sum[l][r][total_k][i] = (sum[l][r][total_k][i] + add) % MOD;
}
}
}
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> K >> MOD;
solve();
// 输出每个节点i的sum[1][N][K][i]
for (int i = 1; i <= N; i++) {
cout << sum[1][N][K][i] % MOD << " ";
}
cout << endl;
return 0;
}
这里空空如也



有帮助,赞一个