T7 [TJOI2018] 游园会
只能说是道有意思的好题。
一般来说遇到这种题我们想到的都会是设 \(f_{i,\dots}\) 表示长度为 \(i\)，然后后面跟一堆状态的情况。此题需要我们满足两个条件：
- LCS 的长度；
- 不能出现 \(\texttt{NOI}\) 的子串。
第二个限制我们可以通过状态设计来解决，但第一个很棘手，因为我们没有办法通过枚举 LCS 的长度来转移。这里就引入了这道题的重头：DP of DP。我们可以通过状压把 LCS 数组的状态设到转移方程里。可以这么做的理由如下：
观察 LCS 的转移方法：
\[\text{LCS}_{i,j}=\max\begin{cases}\text{LCS}_{i-1,j-1}+1&t_i=s_j\\\max(\text{LCS}_{i,j-1},\text{LCS}_{i-1,j})&t_i\ne s_j\end{cases} \]我们发现：
- 转移只涉及 \(i-1\) 行和 \(i\) 行，故可以滚动数组处理；
- \(\text{LCS}_{i,j}-\text{LCS}_{i,j-1}\le1\)，说明原数组差分后是一个 \(\texttt{01}\) 串。所以可以状压。
所以我们定义状态：\(f_{i,s,l}\) 表示考虑到第 \(i\) 位、\(\text{LCS}\) 数组状态为 \(s\)、与 \(\texttt{NOI}\) 的匹配长度为 \(l\) 的方案数。之后转移容易。
代码中我们需要实现三个函数：
- 编码函数（encode），把数组压成一个状态；
- 解码函数（decode），把状态解码成数组；
- 计算函数（trans），把状态解码、转移、再编码。
可以结合代码理解。
#include<bits/stdc++.h>
using namespace std;
constexpr int MOD=1e9+7;
int n,k;
string s;
void add(int&x,int y){
x=x+y>=MOD?x+y-MOD:x+y;
}
int f[2][1<<15][3],g[2][16],ans[16],p[300],cnt[1<<15];
void decode(int s){
for(int i=0;i<=k;++i)g[0][i]=0;
for(int i=1;i<=k;++i)g[0][i]=s>>(i-1)&1;
for(int i=1;i<=k;++i)g[0][i]+=g[0][i-1];
}
int encode(){
int s=0;
for(int i=1;i<=k;++i)s|=(g[1][i]-g[1][i-1])<<(i-1);
return s;
}
void trans(int cur,int S,int l,int c,int x){
if(!x||(l==2&&c==2))return;
int nxt=l==0?1:0;
if(!l&&!c)nxt=1;
else if(l==1&&c==1)nxt=2;
decode(S);
for(int i=0;i<=k;++i)g[1][i]=0;
for(int i=1;i<=k;++i){
if(p[(int)s[i]]==l)g[1][i]=max(g[1][i],g[0][i-1]+1);
g[1][i]=max({g[1][i],g[0][i],g[1][i-1]});
}
add(f[cur][encode()][nxt],x);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>k>>s;
p['N']=0,p['O']=1,p['I']=2;
s=' '+s;
f[0][0][0]=1;
for(int i=1;i<=n;++i){
for(int s=0;s<1<<k;++s)
for(int l=0;l<3;++l)
f[i&1][s][l]=0;
for(int s=0;s<1<<k;++s)
for(int l=0;l<3;++l){
trans(i&1,s,l,0,f[(i&1)^1][s][0]);
trans(i&1,s,l,1,f[(i&1)^1][s][1]);
trans(i&1,s,l,2,f[(i&1)^1][s][2]);
}
}
for(int s=0;s<1<<k;++s)cnt[s]=cnt[s>>1]+(s&1);
for(int s=0;s<1<<k;++s)
for(int l=0;l<3;++l)
add(ans[cnt[s]],f[n&1][s][l]);
for(int i=0;i<=k;++i)cout<<ans[i]<<'\n';
return 0;
}