BZOJ5336【TJOI2018】Party

Problem

【TJOI2018】Party

$\mathrm{Time\;Limit:\;60\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

小豆参加了$\mathrm{NOI}$的游园会，会场上每完成一个项目就会获得一个奖章，奖章只会是N,O,I的字样。在会场上他收集到了$K$个奖章组成的串。
兑奖规则是奖章串和兑奖串的最长公共子序列长度为小豆最后奖励的等级。
现在已知兑奖串长度为$N$，并且在兑奖串上不会出现连续三个奖章为NOI，即奖章中不会出现子串NOI。
现在小豆想知道各个奖励等级会对应多少个不同的合法兑奖串。

Input

第一行两个数，$N,K$分别代表兑奖串的长度，小豆收集的奖章串的长度。
第二行一共$K$个字符，表示小豆得到奖章串。

Output

一共$K+1$行，第$i$行表示小豆最后奖励等级为$i-1$的不同的合法兑奖串的个数，可能这个数会很大，结果对$10^9+7$取模。

Sample Input

3 2
NO

Sample Output

1
19
6

Explanation

最长公共子序列长度$0$的串有：III
最长公共子序列长度$2$的串有：NON, NNO, NOO, ONO, INO, NIO
除去NOI，余下的$19\;(26-6-1)$种为最长公共子序列长度为$1$。

HINT

$N\le1000$，$K\le15$

标签：DP套DP 状压DP

Solution

观察求最长公共子序列的$\mathrm{DP}$，发现在其中一个维度上，$dp$值是不下降的，并且相邻两者间差为$0$或$1$。由于题目中$K\le15$，我们可以将$\mathrm{DP}$数组的一行差分后进行状态压缩。
当两个串做最长公共子序列时，我们可以将二维$\mathrm{DP}$看作在$A$串后面每次添一个字符，然后枚举$B$串的每个位置，看新加入的字符会产生哪些影响。将每个横行的$dp$值差分状压后，可以当成一个一维$\mathrm{DP}$，只是每次的状态都是一个表示一整行的二进制数。这样枚举$A$中添哪个字符即可从一个状态转移到另一个状态。
对于”不能含子串NOI“的限制，我们只需要再多记录一维状态$[0/1/2]$表示当前匹配到NOI的哪个位置，若转移后匹配到第三个位置，则不能转移。
预处理状态转移$trans[sta][c]$表示$sta$状态上在$A$串添字符$c$能得到的状态，用$f[i][j][k]$表示当前填到第$i$位，状态为$j$，匹配到NOI的$k$位置上，枚举添哪个字符，设最后一位转到$l$，若$l\ne3$，则$f[i][j][k]$对$f[i+1][trans[j][c]][l]$有贡献。
$\blacktriangle​$注意：空间有点卡，将$f​$数组第一维滚动即可。

Code

#include <bits/stdc++.h>
#define MAX_N 1000
#define STANUM (1<<15)
#define P 1000000007
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, s[20]; char str[20];
int trans[STANUM][3], ans[20];
int f[2][STANUM][3], g[20], h[20];
int nxt[3][3] = {{1, 0, 0}, {1, 2, 0}, {1, 0, 3}};
int num(char ch) {
    if (ch == 'N') return 0;
    if (ch == 'O') return 1;
    return 2;
}
void compress(int *arr, int &x) {
    x = 0;
    for (int i = 1; i <= m; i++)
        x |= (arr[i]-arr[i-1])<<(i-1);
}
void express(int *arr, int x) {
    arr[0] = 0;
    for (int i = 1; i <= m; i++)
        arr[i] = arr[i-1]+(x>>(i-1)&1);
}
void init() {
    f[0][0][0] = 1;
    for (int i = 1; i <= m; i++) s[i] = num(str[i]);
    for (int c = 0; c < 3; c++) {
        for (int sta = 0; sta < (1<<m); sta++) {
            express(g, sta), memset(h, 0, sizeof h);
            for (int i = 1; i <= m; i++)
                h[i] = max(g[i], h[i-1]), 
                h[i] = max(h[i], g[i-1]+(c == s[i]));
            compress(h, trans[sta][c]);
        }
    }
}
int main() {
    read(n), read(m), scanf("%s", str+1), init();
    for (int i = 0, c = 0; i < n; i++, c ^= 1)
        for (int sta = 0; sta < (1<<m); sta++)
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) if (nxt[j][k]^3)
                    (f[c^1][trans[sta][k]][nxt[j][k]] += f[c][sta][j]) %= P;
                f[c][sta][j] = 0;
            }
    for (int sta = 0; sta < (1<<m); sta++) for (int i = 0; i < 3; i++)
        (ans[__builtin_popcount(sta)] += f[n&1][sta][i]) %= P;
    for (int i = 0; i <= m; i++) printf("%d\n", ans[i]);
    return 0;
}