2020.2.22 bzoj5336 party

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<cmath>
#define int long long
#define rep(i,a,n) for(register int i=a;i<=n;++i)
#define dwn(i,n,a) for(register int i=n;i>=a;--i)
#define mod 1000000007
using namespace std;
int n,k,m,g[1<<15][3],a[20],b[20],flag1,flag2=1,t[1<<15],ans[20],dp[2][1<<15][3];
char ch[20],str[5]="NOI";
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
void write(int x)
{
    if(!x)return;
    if(x<0)putchar('-'),x=-x;
    write(x/10);
    putchar('0'+x%10);
}
int get(int s,int c)
{
    rep(i,1,k)a[i]=a[i-1]+(s&1),s>>=1;
    rep(i,1,k)b[i]=max(max(b[i-1],a[i]),a[i-1]+(str[c]==ch[i]));
    dwn(i,k,1)s<<=1,s|=(b[i]-b[i-1]);
    return s;
}
signed main()
{
    n=read(),k=read();
    gets(ch+1);
    m=1<<k;
    dp[0][0][0]=1;
    rep(i,0,m-1)
        rep(c,0,2)
            g[i][c]=get(i,c);
    rep(i,1,n)
    {
        memset(dp[flag2],0,sizeof dp[flag2]);
        rep(j,0,m-1)
            rep(k,0,2)
            {
                int temp;
                rep(c,0,2)
                {
                    if(!c)temp=1;
                    else if(c<2)temp=(k==1)?2:0;
                    else temp=(k==2)?3:0;
                    if(temp==3) continue;
                    (dp[flag2][g[j][c]][temp]+=dp[flag1][j][k])%=mod;
                }
            }   
        flag1^=1,flag2^=1;
    }
    rep(i,0,m-1)
    {
        t[i]=t[i>>1]+(i&1);
        rep(j,0,2)(ans[t[i]]+=dp[flag1][i][j])%=mod;
    }
    rep(i,0,k)
    {
        if(ans[i])write(ans[i]);
        else putchar('0');
        putchar('\n');
    }
    return 0;
}