BZOJ5336 TJOI2018 party

Description

Xiaodou took part in the garden party of NOI. Every project completed in the venue will get a medal. The medal will only be N, O, I. He collected a string of K medals at the meeting.
The honor rule is that the longest common subsequence length of medal string and honor string is the final reward level of adzuki bean.
Now it is known that the length of honor string is N, and there will not be three consecutive medals named NOI on the honor string, that is, there will not be sub string NOI in the medal.
Now Xiaodou wants to know how many different legitimately honored strings will be corresponding to each reward level.

Input

There are two numbers in the first line. N and K represent the length of honor string and the length of medal string collected by adzuki bean.
In the second line, there are K characters, which means that Xiaodou gets the medal string.
N<=1000 & K<=15

Output

There are K+1 lines in total. Line i indicates the number of different legal reward strings with the final reward level of i-1 for adzuki bean. It may be a large number, and the result is modeled as 10 ^ 9 + 7.

Sample Input

3 2
NO

Sample Output

1
19
6
Tips
The strings with the longest common subsequence length 0 are: III;
The strings with the longest common subsequence length 2 are: NON, NNO, NOO, ONO,INO, NIO;
In addition to NOI, the remaining 19 (26-6-1) species are the longest common subsequence with a length of 1.

First, when we calculate lsm, the difference between two adjacent DP values is at most one, so we use this to construct the state. Take the 01 string after DP value difference as the state, and then DP the state. Because the only special case we need to consider is NOI, it's good to add one dimension to record the state

#include<bits/stdc++.h>
using namespace std;
#define K 20
#define N 1010
#define S (1<<16)
#define Mod 1000000007
int n,k,bit[K],ans[K]={0};
int now[K]={0},res[K]={0},a[K];
int T[S][3]={0};
int dp[2][3][S]={0},ind=0,frm=1;
/*
dp The second dimension in the array
0->No special restrictions
1->The end is N.
2->The end is NO.
*/
/*
N->0
O->1
I->2
*/
void add(int &x,int y){x=(x+y)%Mod;}
int countsiz(int s){int cnt=0;while(s)cnt++,s-=s&-s;return cnt;}
int main(){
    scanf("%d%d",&n,&k);
    getchar();
    for(int i=1;i<=k;i++){
        char c;scanf("%c",&c);
        if(c=='N')a[i]=0;
        if(c=='O')a[i]=1;
        if(c=='I')a[i]=2;
    }
    bit[1]=1;for(int i=2;i<=k;i++)bit[i]=bit[i-1]<<1;
    int up=(1<<k)-1;
    for(int s=0;s<=up;s++){
        for(int i=1;i<=k;i++)
            now[i]=now[i-1]+(bool)(s&bit[i]);
        for(int typ=0;typ<3;typ++){
            for(int i=1;i<=k;i++)
                if(a[i]==typ)res[i]=now[i-1]+1;
                else res[i]=max(res[i-1],now[i]);
            for(int i=1;i<=k;i++)T[s][typ]|=bit[i]*(res[i]-res[i-1]);
        }
    }
    dp[ind][0][0]=1;
    for(int i=1;i<=n;i++){
        ind^=1;frm^=1;
        memset(dp[ind],0,sizeof(dp[ind]));
        for(int s=0;s<=up;s++){
            //No limit - > no limit (currently O or I)
            add(dp[ind][0][T[s][1]],dp[frm][0][s]);
            add(dp[ind][0][T[s][2]],dp[frm][0][s]);
            //No limit - > limit 1 (currently N)
            add(dp[ind][1][T[s][0]],dp[frm][0][s]);
            //Limit 1 - > no limit (I currently appears)
            add(dp[ind][0][T[s][2]],dp[frm][1][s]);
            //Limit 1 - > limit 1 (currently N)
            add(dp[ind][1][T[s][0]],dp[frm][1][s]);
            //Limit 1 - > limit 2 (currently O)
            add(dp[ind][2][T[s][1]],dp[frm][1][s]);
            //Limit 2 - > no limit (current O)
            add(dp[ind][0][T[s][1]],dp[frm][2][s]);
            //Limit 2 - > limit 1 (currently N)
            add(dp[ind][1][T[s][0]],dp[frm][2][s]);
        }
    }
    for(int s=0;s<=up;s++)
        for(int i=0;i<3;i++)
            add(ans[countsiz(s)],dp[ind][i][s]);
    for(int i=0;i<=k;i++)printf("%d\n",ans[i]);
    return 0;
}