标签：析合树
析合树就是用来处理这一种值域连续段的问题的。
我们回顾一下题目，要求不存在长度为 \([2, n - 1]\) 之间的连续段，换句话说，就是根节点下恰有 \(n - 1\) 个节点，且没有任何一个字段是题目中要求的连续段。
我们记这样的答案为 \(A_n\) 也就是我们要求的答案。直接解决是 Hard 的，我们考虑容斥一下，算存在连续段的方案数。
首先需要分类讨论：
根是合点
不妨以递增顺序的合点为例，显然递减的情况是一样的。
设 \(I_x\) 表示前 \(x\) 位有多少种填法，使得任意一个前缀都不是连续段。
\[I_x = \sum_{i = 1}^{x - 1} I_i(x - i)! \]前面方案乘上后面随便的方案之和即可。
这一种情况的答案就是 \(2\sum_{i = 1}^{n} I_i(n - i)!\)。
根是析点
这一步我们要知道子树中任意一个子段都不是连续段，这个就是我们之前设的 \(A\) 数组，同样考虑递推求出来。
首先要枚举有几个儿子，然后乘上这些段的答案即可。
那么我们还需要 DP 计算出 \(n\) 个点放在 \(j\) 段中的方案。
然后递推出 \(A\) 数组即可。
代码
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define F(i, a, b) for (int i = (a); i <= (b); i++)
#define dF(i, a, b) for (int i = (a); i >= (b); i--)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 405, M = (N << 1), inf = 1e16;
int mod, n, m, A[N], I[N], fac[N], B[N][N];
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> mod;
fac[0] = 1;
F(i, 1, 400) I[i] = fac[i] = fac[i - 1] * i % mod;
F(i, 2, 400)
F(j, 1, i - 1)
I[i] = (I[i] - I[j] * fac[i - j] % mod + mod) % mod;
B[0][0] = 1;
F(i, 1, 400) F(j, 1, i) F(k, 1, i)
B[i][j] = (B[i][j] + B[i - k][j - 1] * fac[k] % mod) % mod;
A[1] = 1, A[2] = 2, A[3] = 0;
F(i, 4, 400) {
A[i] = fac[i];
F(j, 1, i - 1)
A[i] = (A[i] - 2 * I[j] * fac[i - j] % mod + mod) % mod;
F(j, 4, i - 1)
A[i] = (A[i] - B[i][j] * A[j] % mod + mod) % mod;
}
F(i, 1, n) {
int x;
cin >> x;
cout << A[x] << '\n';
}
return 0;
}