CF 1515E - Phoenix and Computers

• 可以发现手动点亮的一定是一段一段的，中间恰好间隔一个自动点亮的。

  枚举每一段 \(l...r\) 第一个被点亮的位置 \(p\)，则 \(l...p-1,p+1...r\) 这两部分点亮的顺序是各自确定的，

  而方案数则为

  \[\sum_{p = 1}^{r - l + 1}\binom {r - l}{p - 1} = 2^{r - l} \]

• 于是可以进行 dp，设 \(f_{i,j}\) 表示 \(i\) 位置为自动点亮，前面一共手动点亮了 \(j\) 个的方案数。

  转移枚举上一个 \(i\) 即可，然后把先增的位置依次插入在操作序列中。

  复杂度 \(O(n^3)\)。

• vp 的时候，没想到，想的是倒着考虑，每次将 \(1,2,3\) 个连续的点亮的位置熄灭，做一个 \(O(n^4)\) 的 dp。

  以为能过 \(n = 400\)。

#include <bits/stdc++.h>
using namespace std;

const int N = 405;

int n, mod, f[N][N], c[N][N], ans, b[N];

int main() {
	scanf("%d%d", &n, &mod);
	
	for (int i = 0; i <= n; i++) {
		c[i][0] = 1;
		
		for (int j = 1; j <= i; j++) 
			c[i][j] = (c[i - 1][j - 1] + c[i - 1][j])%mod;
	} 
	
	b[0] = 1;
	
	for (int i = 1; i <= n; i++)
		b[i] = b[i - 1]*2%mod;
	
	f[0][0] = 1;
		
	for (int i = 2; i <= n + 1; i++) 
		for (int j = 1; j < i; j++)
			for (int k = 0; k < i - 1; k++)
				f[i][j] = (f[i][j] + 1ll*f[k][j - (i - k - 1)]*b[i - k - 2]%mod*c[j][i - k - 1])%mod;
	
	for (int i = 1; i <= n; i++)
		ans = (ans + f[n + 1][i])%mod;
	
	printf("%d\n", ans);
}

CF 1515E - Phoenix and Computers

原文：https://www.cnblogs.com/iqx37f/p/14851539.html