[Luogu p4590] garden party (DP set DP)

Garden party

Topic link ：luogu P4590

The main idea of the topic

Give you a matching string , Then ask you for all the lengths n String , Satisfaction doesn't exist NOI The string of , Match the string LCS by x How many , For each x Find the answer .
（ Both strings are composed of NOI Three characters make up ）

Ideas

（LCS Is the length of the longest common subsequence , Tell it to people who don't know , For example, I ）

DP set DP

There is one in the inner layer DP, Then the outer layer DP With inner layer DP The result comes as a state DP.
For example, a DP Something to find the answer , How many situations do you want to meet? The answer is this .

This question

First, let's think about the inner layer DP：
set up $f_{i,j}$ Match the first string to $i$, The second string matches $j$ Of 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)$

Let's consider adding a new character to a string （ For example, the first string ）, Then we have to maintain $f_i$ This array .
（ Since it is maintaining arrays , It must be more , Less maintenance ）
But it still doesn't seem to work , Find some properties , It is found that the difference between adjacent two will not be greater than $1$, So the difference is $2^{|s2|}$ Shape pressed .

Then you can preprocess the current array and put another character into which array it will go .
Then look at a limiting condition ： Cannot appear NOI Substring .

Then this is not difficult , Record the current period N suffix , still NO suffix , Or nothing .
Then transfer it .

Code

#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;
}