【luogu P4590】游园会（DP套DP）

游园会

题目链接：luogu P4590

题目大意

给你一个匹配字符串，然后问你对于所有的长度为 n 的字符串，满足不存在 NOI 的子串，跟匹配字符串 LCS 为 x 的有多少个，对于每个 x 都求出答案。
（两个字符串都由 NOI 三个字符组成）

思路

（LCS 是最长公共子序列长度，讲给不知道的人，比如我）

DP套DP

就是内层有一个 DP，然后外层的 DP 用内层 DP 的结果作为状态来 DP。
比如就是一个 DP 求答案的东西，要你求有多少个情况满足答案是这个。

这题

首先我们思考内层 DP：
设 $f_{i,j}$ 为第一个串匹配到 $i$，第二个串匹配到 $j$ 的 LCS。
$f_{i,j}=f_{i-1,j-1}+1(s{1}_i=s{2}_j)$
$f_{i,j}=\max \{f_{i-1,j},f_{i,j-1}\}(s{1}_i\ne s{2}_j)$

那我们考虑一个串加入一个新的字符（比如第一个串），那我们就要维护 $f_i$ 这个数组。
（那既然是维护数组，肯定是加入多的，维护少的）
但是似乎还是不行啊，找点性质，发现相邻两个差不会大于 $1$，所以差分一下就 $2^{|s2|}$ 状压了。

然后你可以预处理当前数组再放一个字符会转到什么数组。
然后再看一个限制条件：不能出现 NOI 子串。

那这个也不难，就记录当期是有 N 后缀，还是 NO 后缀，还是啥都没有。
然后转移一下即可。

代码

#include<cstdio>
#include<iostream>
#define ll long long
#define mo 1000000007

using namespace std;

const int M = 1 << 15;
int n, K, nxt[M][3], fr[15], to[15];
ll f[2][M][3], ans[16];
char s[15], p[] = {
    'N', 'O', 'I'};

int main() {
    
	scanf("%d %d", &n, &K);
	scanf("%s", s);
	
	for (int i = 0; i < 1 << K; i++) {
    
		for (int j = 0; j < K; j++) fr[j] = (i >> j) & 1;
		for (int j = 1; j < K; j++) fr[j] += fr[j - 1];
		for (int j = 0; j < 3; j++) {
    
			for (int k = 0; k < K; k++) {
    
				to[k] = (s[k] == p[j]) ? fr[k - 1] + 1 : max(fr[k], !k ? 0 : to[k - 1]);
				nxt[i][j] |= (to[k] - (!k ? 0 : to[k - 1])) << k;
			}
		}
	}
	
	f[0][0][0] = 1;
	for (int i = 0; i < n; i++) {
    
		for (int j = 0; j < 1 << K; j++) {
    
			(f[(i & 1) ^ 1][nxt[j][1]][0] += f[i & 1][j][0] + f[i & 1][j][2]) %= mo;
			(f[(i & 1) ^ 1][nxt[j][2]][0] += f[i & 1][j][0] + f[i & 1][j][1]) %= mo;
			(f[(i & 1) ^ 1][nxt[j][0]][1] += f[i & 1][j][0] + f[i & 1][j][1] + f[i & 1][j][2]) %= mo;
			(f[(i & 1) ^ 1][nxt[j][1]][2] += f[i & 1][j][1]) %= mo;
		}
		for (int j = 0; j < 1 << K; j++) for (int k = 0; k < 3; k++)
			f[i & 1][j][k] = 0;
	}
	
	for (int i = 0; i < 1 << K; i++) {
    
		int num = 0; for (int j = 0; j < K; j++) if ((i >> j) & 1) num++;
		(ans[num] += f[n & 1][i][0] + f[n & 1][i][1] + f[n & 1][i][2]) %= mo;
	}
	for (int i = 0; i <= K; i++) printf("%lld\n", ans[i]);
	
	return 0;
}