UPD 2023.12.31：失手把原来的博文删掉了，这篇是补档。
引入
在一类序列计数问题中，状态转移的过程可能与相邻的已插入元素的具体信息相关（e.g. 插入一个新元素时，需要知道与其插入位置相邻的两个元素的值是多少，才可进行状态转移，如「JOI Open 2016」摩天大楼）。这类问题通常的特点是，如果只考虑在序列的两端插入，问题将容易解决（或者说有更简便的状态记录方式）。连续段 dp 这种转移策略便因此而生：它可以最大程度利用两端插入时的良好性质，同时还能与排列集成双射，是解决这类依赖邻项的排列计数问题的利器。
模型
所谓“连续段”本质上只是一种转移策略，这种策略在与排列成双射的同时，还能通过一定的性质使某些难以记录的状态便于记录。解题过程中多可按形象意义上的“连续段”理解。
连续段 dp 的元素插入操作只会在连续段的两端进行，通过用于新建连续段，插入至已有连续段的两端，用于合并两连续段三类转移方式来进行状态转移（如有疑点建议了解基本模型后查看下文“说明”）。通常，我们会按某种特定的顺序插入所有元素，每次插入元素时，对三类转移方式进行分类讨论：将插入的元素作为一个新连续段插入，将元素插入至一个已有连续段的两端，将元素用于合并两个连续段，分别会导致什么状态变化。
我们先从最基础的模型说起。这类问题形如求满足某些限制的 \(n\) 个元素的排列数量，通常情况下我们会设 \(f_{i, j}\) 表示考虑前 \(i\) 个元素，已形成 \(j\) 个连续段的方案数（视题目限制不同可能会在此基础上记录更多信息，此处不考虑其余限制）。则上述三种基本转移方式对应：
-
将被插入元素用于新建连续段：\(f_{i, j} \times (j + 1) \to f_{i + 1, j + 1}\)，系数 \(j + 1\) 表示可以在 \(j\) 个连续段之间的任意空隙插入新连续段。
-
将被插入元素用于合并两连续段：\(f_{i, j} \times (j - 1) \to f_{i + 1, j - 1}\)，\(j\) 个顺次排列的连续段两两间会形成 \(j - 1\) 种合并方案。
-
插入元素至已有连续段的两端：\(f_{i, j} \times 2j \to f_{i + 1, j}\)，\(j\) 个连续段两端均可插入。部分题目左侧插入和右侧插入的状态转移可能不同，此时需分类讨论。
在此对读者可能产生的疑点与误区做一下说明：
-
dp 过程中不考虑各连续段的状态如何，只考虑整体上存在多少个连续段，各连续段的状态的总和是多少。
-
一般连续段 dp 中关于顺序问题有两种理解方式：一类是将连续段视为有序的，即各连续段间的相对顺序决定连续段内元素在原序列中的相对顺序；另一类则是将连续段视为无序的，即连续段之间彼此独立，只有两连续段合并时的相对顺序才会决定段内元素的相对顺序。绝大部分情况下这两种方法都是可行的，笔者采用前者展开叙述。
-
通过三种转移方式所得到的结果，一定与原序列成一一对应（也即，与原序列的全排列成双射），因为不同的插入方式本质上决定着元素在原序列中的位置（可以理解为笛卡尔树的建树过程）。
-
连续段 dp 之所以能够避免记录信息的问题，是因为元素的插入，连续段的合并等操作均在连续段的两端进行，而在这类题目中，这种策略能使得状态维护变得简单。
-
提一下可能会有人误解的一件事情：“插入”并非考虑插入元素在最终序列中的绝对位置，只是考虑当前局面下元素的相对位置。打个不太严谨的比方，就像向一个初始为空的 vector 中不断 insert 元素的过程。
所以，如果说普通的 dp 是将原问题划分为若干个子问题求解后合并，连续段 dp 更像是一边扩大问题规模，一边合并子问题以解决原问题。
例题
CF1515 E. Phoenix and Computers
对于本题，稍作尝试后发现单侧插入具有良好的性质。考虑连续段 dp，我们将连续段定义为连续的一段已被打开的电脑。
由于本题中的插入和合并操作较为特殊，在给出解法前先提一个技巧，考虑连续段 dp 时可以先考虑仅对于一个连续段，其在端点处的插入操作是怎样的；仅对于两个连续段，其合并操作是怎样的，再由此归纳至如何整体考虑。
记 \(f_{i, j}\) 表示共考虑 \(i\) 个电脑，组成了 \(j\) 个连续段的方案数，则
-
在已有连续段的一端插入新元素：如果我们直接在端点紧邻的位置插入，有 \(f_{i, j} \times 2j \to f_{i + 1, j}\)；如果我们在与端点相隔 1 格的位置插入，\(f_{i, j} \times 2j \to f_{i + 2, j}\)，由题意知这样仍能保证连续段数量不变。
-
合并两连续段：根据题意，我们可以用两个电脑来连接两连续段，具体地，我们可以在两连续段间插入两个电脑并打开其中一个，因此有 \(f_{i, j} \times 2(j - 1) \to f_{i + 2, j - 1}\)；还可以插入三个电脑并打开中间那个，也可以实现合并的过程，有 \(f_{i, j} \times (j - 1) \to f_{i + 3, j - 1}\)
-
作为新的连续段插入：\(f_{i, j} \times (j + 1) \to f_{i + 1, j + 1}\)
显然最后只会也只应该剩下一个连续段，即答案为 \(f_{n, 1}\)。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int N = 400 + 10;
i64 f[N][N], n, MOD;
inline void pl(i64& x, i64 y) {(x += y) %= MOD;}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> MOD;
f[0][0] = 1;
for(int i = 0; i < n; i++){
for(int j = 0; j <= i; j++){
if(i <= n - 1) pl(f[i + 1][j], f[i][j] * j * 2);
if(i <= n - 2) pl(f[i + 2][j], f[i][j] * j * 2);
if(j >= 2 && i <= n - 2) pl(f[i + 2][j - 1], f[i][j] * (j - 1) * 2);
if(j >= 2 && i <= n - 3) pl(f[i + 3][j - 1], f[i][j] * (j - 1));
pl(f[i + 1][j + 1], f[i][j] * (j + 1));
}
}
cout << f[n][1] << "\n";
}
P7967 [COCI2021-2022#2] Magneti
记覆盖区间表示磁铁经过放置，最左端磁铁和最右端的磁铁的位置组成的区间。
我们先做一个转化：考虑对于一种磁铁的排列顺序 \(p\)，我们求出其极小的覆盖区间长度（i.e. 将所有磁铁尽可能紧凑地放置后，覆盖区间的长度），记该长度为 \(D(p)\)，则剩余的 \(l - D(p)\) 个空位可以在磁铁之间及被覆盖区间之外任意放置，组合数学算得方案数为 \(\binom{l - D(p) + n}{n}\)。记 \(g(x)\) 表示有多少个排列 \(p\) 满足 \(D(p) = x\)，答案显然为 \(\sum \binom{l - i + n}{n}g(i)\)，考虑如何求 \(g\)。
首先注意到对于两相邻磁铁 \(i, j\)，若 \(r_i < r_j\)，则只需考虑 \(r_j\) 的限制，因此我们按 \(r_i\) 从小到大插入元素。记当前覆盖区间长度为 \(k\)，显然我们需要维护这个 \(k\) 才能进行状态转移。当我们在两端插入磁铁时，可以直接令 \(k \gets k + r_i\)，但若在两相邻磁铁 \(x, y\) 之间插入，需要令 \(k \gets k + 2r_i - \max(r_x, r_y)\)，用到了已插入元素的具体信息。面对这种插入位置在端点便于维护，在相邻元素之间难以维护的时候，想到连续段 dp。
记 \(f_{i, j, k}\) 表示插入了前 \(i\) 个元素，形成 \(j\) 个连续段，目前覆盖区间长度为 \(k\) 的方案数。
-
插入至已有连续段的一端：\(f_{i, j, k} \times 2j \to f_{i + 1, j, k + r_{i + 1}}\)
-
作为新的连续段插入：\(f_{i, j, k} \times (j + 1) \to f_{i + 1, j + 1, k + 1}\)
-
合并两连续段：\(f_{i, j, k} \times (j - 1) \to f_{i + 1, j - 1, k + 2r_{i + 1} - 1}\)，新元素会对 \(k\) 产生 \(2r_{i + 1} - 1\) 的贡献。
可能有的读者还是会对 \(k\) 的转移感到疑惑，其实连续段 dp 过程中，我们更多地会将“连续段”视作“子问题”，连续段之间互相独立，只有在合并时才会互相产生影响。上文中 \(k\) 统计的只是每个“子问题”中覆盖区间长度的总和，因此当我们新建，插入，合并的时候 \(k\) 通过如上方式转移。
最终有 \(g(i) = f_{n, 1, i}\)，按此前得到的式子计算即可。
通常连续段 dp 最后作为结果的值都是 \(f_{n, 1, ...}\)，因为最终各子问题都应被合并进总问题。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int N = 50 + 5, L = 10000 + 100, MOD = 1e9 + 7;
int f[N][N][L], r[N], g[L];
inline void pl(int& x, int y) {x += y; if(x >= MOD) x -= MOD;}
i64 fact[L], invfact[L];
inline i64 ksm(i64 a, i64 b){
i64 r = 1;
while(b){
if(b & 1) r = r * a % MOD;
a = a * a % MOD; b >>= 1;
}
return r;
}
inline i64 binom(int n, int m) {return fact[n] * invfact[m] % MOD * invfact[n - m] % MOD;}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
fact[0] = invfact[0] = 1;
for(int i = 1; i < L; i++)
fact[i] = fact[i - 1] * i % MOD, invfact[i] = ksm(fact[i], MOD - 2);
int n, l; cin >> n >> l;
for(int i = 1; i <= n; i++)
cin >> r[i];
sort(r + 1, r + n + 1);
f[0][0][0] = 1;
for(int i = 0; i < n; i++) for(int j = 0; j <= i; j++)
for(int k = 0; k < l; k++){
if(k + r[i + 1] <= l)
pl(f[i + 1][j][k + r[i + 1]], 1ll * f[i][j][k] * j * 2 % MOD);
if(k + r[i + 1] * 2 - 1 <= l && j >= 2)
pl(f[i + 1][j - 1][k + r[i + 1] * 2 - 1], 1ll * f[i][j][k] * (j - 1) % MOD);
pl(f[i + 1][j + 1][k + 1], 1ll * f[i][j][k] * (j + 1) % MOD);
}
for(int i = 0; i <= l; i++)
g[i] = f[n][1][i];
int ans = 0;
for(int i = 0; i <= l; i++)
pl(ans, binom(l - i + n, n) * g[i] % MOD);
cout << ans << "\n";
}
「JOI Open 2016」摩天大楼
注意到绝对值求和的形式，因此考虑将权值 \(a\) 排序以规避绝对值。下文默认 \(a\) 已按从小到大排序，且插入元素的顺序亦为从小到大。
记当前所有相邻项的绝对值之和为 \(k\)，当我们在两个已有相邻项之间插入新元素 \(a_i\) 时，经过尝试我们发现新的 \(k\) 值依赖于已有元素的具体取值。让我们重点考虑一下在端点处插入的情况，表面上我们需要知道端点元素的值 \(x\) 并令 \(k \gets k + a_i - x\)，但是事实上，由于对于一个单调递增的序列 \(b\)，其相邻项间绝对值之和 = \(\sum b_i - b_{i - 1} = b_n - b_1\)，这意味着，如果新插入的元素不是连续段的边界（如果一个端点被称为“边界”，则这个端点处不会再有新的元素插入），我们可以暂时忽略这个元素对 \(k\) 的贡献，利用作为连续段边界的元素来统一处理这些贡献。
比较容易发现，每个未经过合并的连续段都是一个单谷序列（即 \(\exists k \in [1, n], a_i > a_{i + 1} \forall i \in [1, k - 1] , a_i < a_{i + 1} \forall i \in [k, n - 1]\)），如果确定了连续段的左右边界，并知道连续段中的最小元素（称这个最小元素的位置为“中间”），则这个连续段相邻项间的绝对值之和 = 右边界元素的值 - 中间元素的值 + 左边界元素的值 - 中间元素的值。我们将这三种贡献拆开，作为独立的三部分分别考虑：
-
“边界”可以在合并两连续段时被添加，此时 \(k' \gets k + 2a_i\)，因为它同时作为了左侧连续段的右边界及右侧连续段的左边界。或者将插入元素强行作为边界插入到到目前最左侧 / 最右侧的连续段的左端 / 右端上，此时 \(k' \gets k + a_i\)。
-
“中间”元素其实就是一个连续段中第一个被插入的元素，我们只需要在新建连续段时，\(k' \gets k - 2a_i\)。（注意在实现时必须分类讨论这个“中间”元素是否作为连续段的边界，如果“中间”元素同时作为边界的话，\(k' \gets k - a_i\) 即可。）
这样一来，我们完成了关于 \(k\) 的转移。因此记 \(f_{i, j, k, d}\) 表示考虑了前 \(i\) 个元素，形成了 \(j\) 个连续段，贡献和为 \(k\)，已存在 \(d\) 个边界（此处及下文的“边界”意为“被强行插入到最左端 / 最右端的边界”），满足以上约束的方案数。我们可以按如下方式写出状态转移方程：
- 作为一个新的连续段插入到不为边界的间隙中，即 \(f_{i + 1, j + 1, k - 2a_{i + 1}, d} \gets f_{i, j, k, d} \times (j + 1 - d)\)。
- \((j \geq 2)\) 合并两个连续段，即 \(f_{i + 1, j - 1, k + 2a_{i + 1}, d} \gets f_{i, j, k, d} \times (j - 1)\)。
- \((j \geq 1)\) 作为一个新元素插入到某个连续段的非边界端点处，即 \(f_{i + 1, j, k, d} \gets f_{i, j, k, d} \times (2j - d)\)。
- \((d < 2)\) 作为一个新的连续段作为边界插入，即 \(f_{i + 1, j + 1, k - a_{i + 1}, d + 1} \gets f_{i, j, k, d} \times (2 - d)\)。
- \((d < 2, j \geq 1)\) 作为一个新元素作为边界端点插入到某个连续段，即 \(f_{i + 1, j, k + a_{i + 1}, d + 1} \gets f_{i, j, k, d} \times (2 - d)\)。
最终答案为 \(Ans = \sum \limits_{i = 0} ^ {L} f_{n, 1, i, 2}\)。
然而，分析一下时间复杂度，记 \(V\) 表示 \(a_i\) 的值域，则 \(k\) 这一维的状态数会达到 \(\mathcal{O}(nV)\)，总复杂度 \(\mathcal{O}(n ^ 3V)\)，对于本题是一个错误的复杂度。
瓶颈在哪里呢？前面提到 \(k\) 的状态数达到 \(\mathcal{O}(nV)\)，但是事实上最终统计答案时有用的状态数仅是 \(\mathcal{O}(L)\) 的。但是，按照我们 dp 的分析过程，这 \(\mathcal{O}(nV)\) 个状态是不能直接省去的，因为 \(k\) 在转移过程中可增可减，可以达到 \(\mathcal{O}(nV)\) 的状态数。是否能换一种角度考虑贡献，使得贡献的转移只增不减，从而能够尽可能地去除无用状态呢？
考虑一种差分的思想：\(\forall i < j, a_j - a_i = \sum \limits_{k = i} ^ {j - 1} a_{k + 1} - a_k\)，则此时 \(a_{k + 1} - a_k\) 对总贡献的贡献为所有贡献中满足 \(i \leq k < j\) 的 \(a_j - a_i\) 数量。
形式化一下，记 \(b\) 为对 \(a\) 进行任意重排列后的序列，\(g(i)\) 表示 \(b_i\) 这个数值在 \(a\) 中的位置（\(\text{i.e. } a_{g(i)} = b_i\)）。显然总贡献即 \(\sum b_{i + 1} - b_i = \sum a_{g(i + 1)} - a_{g(i)}\)，记 \(x_i = \min(g(i), g(i + 1)), y_i = \max(g(i), g(i + 1))\)，依据上文差分的方法可以将总贡献写作 \(\sum a_{y_i} - a_{x_i} = \sum \sum \limits_{k = x_i}^{y_i - 1}a_{k + 1} - a_k\)，因此可以说明 \(a_{k + 1} - a_k\) 对总贡献的贡献为满足 \(x_i \leq k < y_i\) 的 \((x_i, y_i)\) 数量，也即前述结论。
它其实就是个差分。但是从贡献的角度考虑也能归为一种叫微元贡献法的 trick。其本质为，面对多个不同的贡献，但我们可以用若干个微元组合出所有不同贡献时，可以考虑此类微元贡献法。
由于上文提到 \(a_{k + 1} - a_k\) 对总贡献的贡献为所有贡献中满足 \(i \leq k < j\) 的 \(a_j - a_i\) 数量，而我们插入元素的顺序是从小到大，因此此后在每个连续段的两个端点处插入的新元素，都一定且仅能构成 \(1\) 次这样的 \(i \leq k < j\)。（“一定”是因为连续段的端点处一定会插入新的值，“仅能”是因为插入新的值后新的值一定会大于 \(a_k\)，无法再组成新的 \(i \leq k < j\)。)
由于确定一个边界后无法再向边界处插入新元素/连续段，因此边界的数量会降低此后新元素对总贡献的增量，仍然需要单独记录边界的数量 \(d\)。
设计 dp 状态为 \(f_{i, j, k, d}\)，意为考虑 \(a\) 中前 \(i\) 个元素构成了 \(j\) 个连续段，当前总贡献为 \(k\)，边界数量为 \(d\) 的方案数。综上，当我们插入一个新数 \(a_{i + 1}\) 时，新的总贡献 \(k' = k + (a_{i + 1} - a_i) \times (2j - d)\)，并且可以直接忽略 \(k' > L\) 的无用状态。
最后，考虑连续段 dp 的几种转移即可。记 \(k' \gets k + (a_{i + 1} - a_i) \times (2j - d)\)。当我们插入 \(a_{i + 1}\) 时，
- 作为一个新的连续段插入到不为边界的间隙中，即 \(f_{i + 1, j + 1, k', d} \gets f_{i, j, k, d} \times (j + 1 - d)\)。
- \((j \geq 2)\) 作为中间点合并两个连续段，即 \(f_{i + 1, j - 1, k', d} \gets f_{i, j, k, d} \times (j - 1)\)。
- \((j \geq 1)\) 作为一个新元素插入到某个连续段的非边界端点处，即 \(f_{i + 1, j, k', d} \gets f_{i, j, k, d} \times (2j - d)\)。
- \((d < 2)\) 作为一个新的连续段作为边界插入，即 \(f_{i + 1, j + 1, k', d + 1} \gets f_{i, j, k, d} \times (2 - d)\)。
- \((d < 2, j \geq 1)\) 作为一个新元素作为边界端点插入到某个连续段，即 \(f_{i + 1, j, k', d + 1} \gets f_{i, j, k, d} \times (2 - d)\)。
答案显然为 \(Ans = \sum \limits_{i = 0} ^ {L} f_{n, 1, i, 2}\)。
值得一提的是，上文提及的两种 dp 方法中，\(k\) 都并非仅考虑 \(a\) 中这前 \(i\) 个元素互相之间的总贡献，而是提前计算了这些元素之后所能产生的一切贡献，从而规避了后效性。这里也分享一篇介绍这种贡献提前计算的好文。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int N = 100 + 10, MOD = 1e9 + 7, M = 1000 + 10;
inline void pl(int &x, i64 y) {x = (y + x) % MOD;}
int f[N][N][M][3], a[N];
void solve() {
int n, l; cin >> n >> l;
for(int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + n + 1);
f[0][0][0][0] = 1;
for(int i = 0; i < n; i++) for(int j = 0; j <= i; j++)
for(int k = 0; k <= l; k++) for(int d = 0; d < 3; d++) {
i64 p = k + (a[i + 1] - a[i]) * (2 * j - d), t = f[i][j][k][d];
if(!t) continue;
if(p > l) continue;
pl(f[i + 1][j + 1][p][d], t * (j + 1 - d));
if(j >= 2) pl(f[i + 1][j - 1][p][d], t * (j - 1));
if(j >= 1) pl(f[i + 1][j][p][d], t * (2 * j - d));
if(d < 2) pl(f[i + 1][j + 1][p][d + 1], t * (2 - d));
if(d < 2 && j >= 1) pl(f[i + 1][j][p][d + 1], t * (2 - d));
}
int ans = 0;
for(int i = 0; i <= l; i++)
pl(ans, f[n][1][i][2]);
cout << (n == 1 ? 1 : ans) << "\n";
}
模拟赛题：弹弹床
题意简述：给定序列 \(\{a_n\}, a_i \in \{0, 1\}\)。求长为 \(n\) 的排列的数量，要求对于所有 \(i \in [1, n - 1]\)，如果 \(a_{p_i} = 1\) 那么 \(p_i > p_{i +1}\)，否则 \(p_i < p_{i + 1}\)，对每个 \(k\) 求 \(p_n = k\) 的方案数，\(n \leq 5000\)。
我们先暂时忽视 \(p_n = k\) 的限制，看看解题的大体框架是什么。
很自然地想到从 \(1\) 到 \(n\) 插入数，便于确定大小关系。首先一件显然的事情是 \(a_1\) 必须为 \(0\)，然后之后如果只在序列的两端插入，那么 \(1\) 的左边只能插入 \(a_{p_i} = 1\)，右边只能插入 \(a_{p_i} = 0\)。有了这个性质，我们来尝试一下连续段 dp。容易发现一个连续段肯定是一段单谷序列，且单谷的左边（不包含最低点）一定均为 \(a_{p_i} = 1\) 的元素，最低点及右边均为 \(a_{p_i} = 0\) 的元素。
更进一步地，可以发现只有 \(a_i = 0\) 的 \(i\) 可以用于新建连续段，只有 \(a_i = 1\) 的 \(i\) 可以用于合并连续段，而 \(a_i = 0\) 与 \(a_i = 1\) 时都能插入至已有连续段，不过前者是插入在连续段之右，后者则是在左。
这样就得到了一个简单的状态转移：
- \(\text{create: } f_{i - 1, j} \times (j + 1) \to f_{i, j + 1}, a_i = 0\)。
- \(\text{merge: } f_{i - 1, j} \times (j - 1) \to f_{i, j - 1}, a_i = 1\)。
- \(\text{insert: } f_{i - 1, j} \times j \to f_{i, j}\)。
如果不限制 \(p_n\)，答案即为 \(f_{n, 1}\)......吗？这里其实是有一些不严谨的成分在里面的，比如说我们这样进行 dp 会导致最终序列一定满足 \(a_{p_n} = 0\)，但事实上原题中并没有这样的要求。熟练的人可以很容易地看出解决思路：加入一维状态，表示是否存在“右边界”，转移时增加讨论即可。不过鉴于原问题限制了 \(p_n\)，且下文我们解决原问题的方式暗中便规避了这一问题，因此在下文我们会沿用这一不带“边界”的状态设计及转移。
现在我们要对每个 \(p_n = k\) 都求出答案。可以发现最容易入手的方式是，仍然从 \(1\) 到 \(n\) 插入元素，在插入 \(k\) 时进行一些讨论。你当然可以选择直接加一个右边界的状态，但是这样的复杂度是 \(\Theta(n ^ 3)\) 的，且基本没有优化的余地。那么应该怎么做呢？
接下来比较人类智慧。考虑我们 dp 求出的 \(f\) 数组事实上包含了所有前缀的信息，即 \([1, i]\) 形成 \(j\) 个连续段在满足题设条件下的排列总数，那么我们一定可以对后缀再进行一次这样的 dp，求出 \(g_{i, j}\) 表示 \([i, n]\) 形成 \(j\) 个连续段的方案数。注意这里由于是反向 dp 所以连续段呈单峰，转移会发生一些条件上的变化，具体读者可自行思考。
考虑 \(p_n = k\) 时怎么合并 \(f_{i - 1}\) 和 \(g_{i + 1}\) 两部分信息，一个令人惊讶的事实是，连续段是支持拼接的！也即，我们可以用连续段来合并连续段，将 \([1, i - 1]\) 形成的 \(j\) 个连续段与 \([i + 1, n]\) 形成的 \(j / j - 1 / j + 1\) 个连续段交错拼接，形成 \(1\) 个最终的连续段。虽然这么做看起来很野蛮，但是与连续段 dp 的正确性证明一致，我们仍然可以证明这样做与所有排列成双射，具体可仿照笛卡尔树。
知道了连续段可以支持拼接后，原问题也就迎刃而解了。考虑对每个 \(k\)，其答案为 \(\sum \limits_{j = 1} ^ n 2 \times f_{k - 1, j} \times g_{k + 1, j} + f_{k - 1, j} \times g_{k + 1, j - 1} + f_{k - 1, j - 1} \times g_{k + 1, j}\)。前一项带系数 \(2\) 是因为拼接方式有 \([1, i - 1]\) 的连续段靠前，\([i + 1, n]\) 的连续段靠前两种方式，而后两项系数为 \(1\) 则是因为拼接方式唯一。而不管哪种方式，我们都可以直接把 \(k\) 接到最后，正确性容易证明。总复杂度 \(\Theta(n ^ 2)\)，此题结。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int mod = 1e9 + 7, N = 5000 + 10;
namespace basic {
inline int add(int x, int y) {return (x + y >= mod ? x + y - mod : x + y);}
inline int dec(int x, int y) {return (x - y < 0 ? x - y + mod : x - y);}
inline void ad(int &x, int y) {x = add(x, y);}
inline void de(int &x, int y) {x = dec(x, y);}
inline int qpow(int a, int b) {
int r = 1;
while(b) {
if(b & 1) r = 1ll * r * a % mod;
a = 1ll * a * a % mod; b >>= 1;
}
return r;
}
inline int inv(int x) {return qpow(x, mod - 2);}
int fac[N], ifac[N];
inline void fac_init(int n = N - 1) {
fac[0] = 1;
for(int i = 1; i <= n; i++)
fac[i] = 1ll * fac[i - 1] * i % mod;
ifac[n] = inv(fac[n]);
for(int i = n - 1; i >= 0; i--)
ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
}
int invx[N];
inline void inv_init(int n = N - 1) {
invx[1] = 1;
for(int i = 2; i <= n; i++)
invx[i] = 1ll * (mod - mod / i) * invx[mod % i] % mod;
}
inline int binom(int n, int m) {
if(n < m || m < 0) return 0;
return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
int rev[N];
inline void rev_init(int n) {
for(int i = 1; i < n; i++)
rev[i] = (rev[i >> 1] >> 1) + (i & 1 ? n >> 1 : 0);
}
}
using namespace basic;
int f[N][N], g[N][N], a[N];
int main() {
// freopen("jump.in", "r", stdin);
// freopen("jump.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int n; cin >> n;
string str; cin >> str;
for(int i = 1; i <= n; i++) {
a[i] = (str[i - 1] == 'L' ? 1 : 0);
}
f[0][0] = 1;
for(int i = 1; i <= n; i++) {
for(int j = 0; j < i; j++) {
if(!f[i - 1][j]) continue;
ad(f[i][j], 1ll * j * f[i - 1][j] % mod);
if(a[i] == 1 && j) {
ad(f[i][j - 1], 1ll * (j - 1) * f[i - 1][j] % mod);
}
if(a[i] == 0) {
ad(f[i][j + 1], 1ll * (j + 1) * f[i - 1][j] % mod);
}
}
}
g[n + 1][0] = 1;
for(int i = n; i >= 1; i--) {
for(int j = 0; j < n + 1 - i; j++) {
if(!g[i + 1][j]) continue;
ad(g[i][j], 1ll * j * g[i + 1][j] % mod);
if(a[i] == 0 && j) {
ad(g[i][j - 1], 1ll * (j - 1) * g[i + 1][j] % mod);
}
if(a[i] == 1) {
ad(g[i][j + 1], 1ll * (j + 1) * g[i + 1][j] % mod);
}
}
}
if(n == 1) {
cout << 1 << "\n";
return 0;
}
for(int i = 1; i <= n; i++) {
int ans = 0;
for(int j = 1; j <= n; j++) {
ad(ans, 2ll * f[i - 1][j] * g[i + 1][j] % mod);
if(j) {
ad(ans, 1ll * f[i - 1][j] * g[i + 1][j - 1] % mod);
ad(ans, 1ll * f[i - 1][j - 1] * g[i + 1][j] % mod);
}
}
cout << ans << " ";
}
}