连续段dp/线头dp

dp

learn from

来点套路，线头dp通常都是状态转移依赖于前后相邻项得技术题的一种通解

在一类序列计数问题中，状态转移的过程可能会跟相邻的已插入元素的信息有关

这类问题的常见特点是：如果只需要考虑从序列的两端加入新元素，问题会特别简单/好记录状态

连续段dp正式利用这种性质，同时连续段dp还可以和排列构成双射

所谓的连续段其实是一种转移策略，通常我们的插入只会在“连续段”的两端进行，并且我们会以某一种特定顺序插入元素，当插入一个新元素时我们会用三种分类讨论来考虑这个元素的贡献：

1. 把这个元素作为一个新的连续段插入
2. 插入一个已有连续段的两侧
3. 用于合并两个连续段

基础模型

求满足某些限制的 $n$ 个元素的排列数量

状态设计：设 $f_i,j$ 表示前 $i$ 个元素构成 $j$ 个连续段的方案数，当然限制更多的时候我们肯定是可以考虑继续往状态塞更多东西的

于是三种对应的转移方式，我们用箭头表示转移

1. 新连续段：$f_{i,j}\times (j+1)\to f_{i+1,j+1}$ ，其中系数 $j+1$ 的意思是可以在当前 $j$ 个连续段的任意一个缝隙里面插入
2. 用于合并：$f_{i,j}\times (j-1)\to f_{i+1,j-1}$，两两考虑合并
3. 插入已有连续段的两端：$f_{i,j}\times 2j=f_{i+1,j}$，每个连续段前后都可以插入，当然有一些题目从前面插入和从后面效果不同那就需要分两类讨论一下

有一些混淆点：

1. dp过程我们并不咋在乎每个连续段自己的状态是什么，只记录连续段的数量，以及状态的总和
2. 一般对于问题理解有两种方式：一是把连续段视为有序的，也就是连续段的相对顺序决定元素在原序列的相对顺序；另一种则是视为无序的，也就是连续段之间毫无关系，只有合并的顺序才决定元素的相对顺序。一般两种方法都是可以的，但是前者貌似更好理解，那就按前者写吧
3. 转移的结果一定和原序列的全排列构成双射

例1：CF1515E

容易发现单侧插入的性质是比较好的，于是不妨考虑连续段

本题中可以定义连续段为依托打开的电脑

本题的插入和合并比较奇怪，于是我们先再给出一个思路：先考虑两个连续段合并、一个连续段前后插入的情况是怎么样的，然后拓展到多个连续段的情况

我们设 $f_{i,j}$ 表示我们一共考虑了 $i$ 个电脑，其中构成了 $j$ 个连续段的方案数

非常注意的是，我们只是说 $i$ 个电脑，不是前 $i$ 个电脑，这是需要注意的

假如我们希望在已有连续段的一段插入，我们其实有两种情况：

如果挨着端点插入，那么有 $f_{i,j}\times 2j\to f_{i+1,j}$，这是容易的，但是不能忽略我们还可以在端点隔一个的地方插入，这样就相当于我们一次插入了两个元素，那就是 $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>
#define int long long
using namespace std;
int n,M;
int f[5005][5005];
signed main(){
    cin>>n>>M;
    f[0][0]=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<=i;j++){
            if(i+2<=n){
                if(j>=1)f[i+2][j]=(f[i+2][j]+f[i][j]*2*j)%M;
                if(j>=2) f[i+2][j-1]=(f[i+2][j-1]+f[i][j]*2*(j-1)%M)%M;
            }
            if(i+3<=n){
                if(j>=2) f[i+3][j-1]=(f[i+3][j-1]+f[i][j]*(j-1)%M)%M;
            }
            if(j>=1) f[i+1][j]=(f[i+1][j]+f[i][j]*2*j%M)%M;
            f[i+1][j+1]=(f[i+1][j+1]+f[i][j]*(j+1)%M)%M;
        }
    }
    cout<<f[n][1];
}