「TJOI 2018」游园会 Party
题目描述
小豆参加了 \(NOI\) 的游园会，会场上每完成一个项目就会获得一个奖章，奖章只会是 \(N, O, I\) 的字样。 在会场上他收集到了 \(K\) 个奖章组成的串。兑奖规则是奖章串和兑奖串的最长公共子序列长度为小豆最后奖励的等级。 现在已知兑奖串长度为 \(N\) ，并且在兑奖串上不会出现连续三个奖章为
NOI，即奖章中不会出现子串NOI。 现在小豆想知道各个奖励等级会对应多少个不同的合法兑奖串。\(N \leq 1000, K \leq 15\)
解题思路 :
首先吐槽一下这个题和 「BZOJ 3864」 几乎没有任何区别，省选放这种题真的合适吗？
考虑一个比较 \(naive\) 的做法，用一个想当然的 \(dp\) 来对答案计数
\(f[i][j][s1][s2]\) 表示长度为 \(i\) 的兑奖串与奖章串的 \(lcs = j\) 且 \(i-1\) 上的字母为 \(s1\) ，\(i\) 上的字母为 \(s2\) 的方案数
观察发现，这个东西转移需要知道与奖章串每一个前缀的 \(lcs\) 是多少，不然 \(i+1\) 的时候无法转移
于是就要维护当前的一个状态集合 \(S\) ，\(S_j\) 表示奖章串前缀 \(j\) 与当且兑奖串的 \(lcs\)
可以对 \(S\) 做一遍 \(lcs\) 的 \(dp\) 从 \(f[i][S]\) 转移到 \(f[i+1][S']\) ，但是 \(S\) 有至多 \(15\) 位，每一位的值至多为 \(15\)
显然无法直接表示为状态，于是需要进行简化状态.
观察发现，对于任意一个状态集合 \(S\), \(S_j -S_{j-1} \leq 1\)
不妨对 \(S\) 进行差分，那么每一位的值域范围就是 \([0,1]\) 了，可以用一个至多 \(2^{15}\) 的数来表示
于是只需要用类似于 \(lcs\) 的 \(dp\) 预处理出来 \(S\) 之间的转移，并额外用一个 \(dp\) 对答案计数即可
\(f[i][S][s1][s2]\) 表示长度为 \(i\) 的兑奖串，与奖章串的每一个前缀的 \(lcs\) 状态集合为 \(S\), 且 \(i-1\) 上的字母为 \(s1\) ，\(i\) 上的字母为 \(s2\) 的方案数
设 \(S'\) 为 \(S\) 能转移到的状态，判一下新加的字符是否会和 \(s1, s2\) 形成 \(NOI\) 再转移即可
预处理的复杂度是 \(O(2^k \times k)\) ，\(dp\) 的复杂度是 \(O(n \times 2^k)\)，总复杂度是 \(O(n \times 2^k)\)
/*program by mangoyang*/
#include<bits/stdc++.h>
#define inf (0x7f7f7f7f)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
int f = 0, ch = 0; x = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
if(f) x = -x;
}
const int N = 1005, K = (1 << 15) + 10, Mod = 1000000007;
char str[N];
int f[2][K][3][3], a[N], s[N], Ans[N], n, m, all;
inline void up(int &x, int y){ x += y; if(x >= Mod) x %= Mod; }
struct Node{ int x, s1, s2; }; vector<Node> g[K][3][3];
namespace Prework{
inline void GetTrans(int x){
for(int i = 0; i < m; i++)
if((1 << i) & x) a[i+1] = a[i] + 1; else a[i+1] = a[i];
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
for(int k = 0; k < 3; k++)
if(i != 0 || j != 1 || k != 2){
int res = 0;
for(int p = 1, ls = 0, now; p <= m; p++, ls = now){
now = Max(a[p], a[p-1] + (s[p] == k));
if(now > ls) res |= (1 << p - 1); else now = ls;
}
g[x][i][j].push_back((Node){res, j, k});
}
}
inline void realmain(){ for(int i = 0; i <= all; i++) GetTrans(i); }
}
int main(){
read(n), read(m), all = (1 << m) - 1;
scanf("%s", str + 1);
for(int i = 1; i <= m; i++){
if(str[i] == 'N') s[i] = 0;
if(str[i] == 'O') s[i] = 1;
if(str[i] == 'I') s[i] = 2;
}
Prework::realmain();
f[0][0][2][2] = 1;
for(int i = 0, o = 0; i < n; i++, o ^= 1){
memset(f[o^1], 0, sizeof(f[o^1]));
for(int j = 0; j <= all; j++)
for(int s1 = 0; s1 < 3; s1++)
for(int s2 = 0; s2 < 3; s2++)
for(int k = 0; k < g[j][s1][s2].size(); k++){
Node now = g[j][s1][s2][k];
int nxt = now.x, s3 = now.s1, s4 = now.s2;
up(f[o^1][nxt][s3][s4], f[o][j][s1][s2]);
}
}
for(int j = 0; j <= all; j++){
int tot = 0;
for(int i = 0; i < m; i++) tot += (j >> i) & 1;
for(int s1 = 0; s1 < 3; s1++)
for(int s2 = 0; s2 < 3; s2++) up(Ans[tot], f[n&1][j][s1][s2]);
}
for(int i = 0; i <= m; i++) cout << Ans[i] << endl;
return 0;
}