【CF1515E Phoenix and Computers】（插入法dp）

原题链接

题意

给定 \(n\)，\(M\)。你有 \(n\) 台电脑排成一排，你需要依次开启所有电脑。

你可以手动开启一台电脑。在任意时刻，若电脑 \(i-1\) 与电脑 \(i+1\) 都已经开启 \((1<i<n)\)，电脑 \(i\) 将立刻被自动开启。你不能再开启已经开启的电脑。

求你有多少种开启电脑的方案。两个方案不同当且仅当你手动开启的电脑的集合不同，或是手动开启电脑的顺序不同。答案对 \(M\) 取模。

思路

对于最终所有电脑的状态，一定是类似于\(一段手动开启+一个自动开启+一段手动开启 \cdots\) 的形式，于是可以想到对所有连续手动开启的段进行 dp。

设 \(f_{i,j}\) 表示将 \(i\) 台电脑划分为 \(j\) 个连续段的方案，不难得到转移方程：

• 第 \(i+1\) 台电脑单独开一段，那么它可以安置在前 \(j\) 段任意两段之间或者两侧，所以 \(f_{i,j} \times(j+1) \to f_{i+1,j+1}\)

• 第 \(i+1\) 台电脑放入这 \(j\) 段当中，由于可以放在每一段的两侧，所以 \(f_{i,j} \times 2j \to f_{i+1,j}\)

对于 \(j\) 段电脑，那么就代表有 \(j-1\) 台电脑可以被自动开启，于是当 \(i+j-1=n\) 时，就可以统计答案。

code：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5050;
int f[N][N],n,mod,ans;
void add(int &a,int b){a+=b;if(a>mod) a-=mod;}
int main()
{
	scanf("%d%d",&n,&mod);f[1][1]=1;
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=n;j++)
	    {
	    	if(i+j-1==n) add(ans,f[i][j]);
	    	add(f[i+1][j+1],1ll*f[i][j]*(j+1)%mod);
	    	add(f[i+1][j],1ll*f[i][j]*2*j%mod);
		}
	printf("%d\n",ans);
	return 0;
}