CF1515 E. Phoenix and Computers

E. Phoenix and Computers

题目大意

初始状态时，有 $n(n\leqslant 400)$ 台没有启动的电脑，每次你可以选择手动一台电脑，当一条未启动的电脑相邻的两台电脑都已经启动时，中间的电脑会自动启动，请问将所有的电脑都启动，你一共有多少种启动方案？答案对 $M(10^8\leqslant M\leqslant 10^9)$ 取模。

思路

一开始看到这个 $n\leqslant 400$ 就想到可以用区间dp，最一开始设条件 $f[i][j][k]$，代表区间 $[i,j]$ 中有 $k$ 个电脑是手动启动的，再仔细想想其实每个区间如果长度一致那么他们就没有任何区别，所以将dp改为 $f[i][j]$，表示将连续 $i$ 个关闭的电脑全部启动且操作数为 $j$ 的方案数。

通过枚举从左到右的第一台自动启动的电脑位置 $k$ 来进行转移，由于从 $[1,k-1]$ 这些电脑都是手动启动的，所以要讨论纯手动启动 $k-1$ 台电脑所需的方案数。

这里用归纳法的方法求，令需要手动启动的电脑数为 $n$ 台，所需的方案数为 $g(n)$

当 $n=1$ 时，$g(1)=1$。

当 $n=2$ 时，$g(2)=g(1)\cdot 2$，因为每次开启的新电脑一定是接着已开启的电脑的

…

当 $n$ 时，$g(n)=g(n-1)\cdot 2=\cdots=2^{n-1}$，于是我们得到了 $g(n)$ 的表达式

最后就是状态转移方程了，$f[i][j]$ 含义就是将连续 $i$ 个关闭的电脑全部启动且操作数为 $j$ 的方案数，为了枚举不发生重复，再加入一个条件就是：这 $i$ 个电脑如果编号从 $1$ 到 $i$，那么 $0$ 号和 $i+1$ 号电脑都认为是自动启动的，那么有如下转移方程:

$$f[i][j]=\sum_{k=2}^{min\{i-1,j\}}g(k-1)\tbinom{j}{k-1}f[i-k][j-k+1]$$

我们从左到右分析这个转移方程：

$\sum_{k=2}^{min\{i-1,j\}}$:

1. $k=2,k\leqslant i-1$ 表示自动启动的电脑不可能在最左或最右两个位置
2. $k\leqslant j$ 表示剩下一定要至少手动启动一台电脑

$g(k-1)$: 表示手动启动 $k-1$ 台电脑所需的方案数

$\tbinom{j}{k-1}$: 表示从 $j$ 个手动启动的方案中选 $k-1$ 个用于左侧的手动启动，因为左侧和右侧启动顺序的毫不相干的，所以可以直接从 $j$ 中选取

$f[i-k][j-k+1]$: 是从 $f[i-k][j-(k-1)]$ 中的来的，左侧一共划去了 $k$ 台电脑，手动启动了 $k-1$ 台电脑

参考代码

我就直接按照上述转移方程写了记忆化搜索，没有转成循环的形式

预处理组合数，时间复杂度 $O(N^3)$

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
const int N = 400 + 10;
int n, P;
int C[N][N], dp[N][N], mi[N];
int rec(int i, int j) {
	if (i == 1) return 1;
	if (dp[i][j] != -1) {
		return dp[i][j];
	}
	if (i == j) {
		return dp[i][j] = mi[i-1];
	}
	int res = 0;
	for (int k = 2; k <= min(i-1, j); k++) {
		res = (res + mi[k-2] * C[j][k-1] % P * rec(i-k, j-k+1)) % P;
	}
	return dp[i][j] = res;
}
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	memset(dp, -1, sizeof(dp));
	cin >> n >> P;
	for (int i = 0; i <= n; i++) {
		mi[i] = C[i][0] = 1ll;
		for (int j = 1; j <= i; j++) {
			C[i][j] = (C[i-1][j] + C[i-1][j-1]) % P;
			mi[i] = (mi[i] + C[i][j]) % P;
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		ans = (ans + rec(n, i)) % P;
	}
	cout << ans << '\n';
	return 0;
}

学习参考

SCN- 的博客