BZOJ5336: [TJOI2018]party

BZOJ5336: [TJOI2018]party

https://lydsy.com/JudgeOnline/problem.php?id=5336

分析:

• 好题。
• 正常的思路是设\(f[i][j][0/1/2]\)表示前\(i\)个位置，与奖章串的\(lcs\)状态为\(j\)，匹配到\(NOI\)的第几位，然后转移。
• 那么问题是这个\(lcs\)的状态如何存储，打个表发现这个状态数很少，实际上也是这样的，因为在匹配\(lcs\)的过程中，相邻两位\(dp\)值最多差\(1\)，状态数\(2^k\)。
• 然后就做完了，预处理出来每个状态能转移到的状态即可。

代码:

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cstdlib>

using namespace std;

#define N 1050

#define mod 1000000007

char w[N];

int n,K;

typedef long long ll;

int tr[1<<15][3],sf[N],sg[N],cnt[1<<15];

ll f[2][1<<15][3],ans[N];

inline void upd(ll &x,ll y) {

    x=x+y; if(x>=mod) x-=mod;

}

int main() {

    scanf("%d%d%s",&n,&K,w+1);

    int i,mask=(1<<K)-1,s;

    for(s=0;s<=mask;s++) {

        for(i=1;i<=K;i++) {

            sf[i]=sf[i-1]+((s>>(i-1))&1);

        }

        for(i=1;i<=K;i++) {

            if(w[i]=='N') sg[i]=sf[i-1]+1;

            else sg[i]=max(sg[i-1],sf[i]);

            tr[s][0]|=(sg[i]-sg[i-1])*(1<<(i-1));

        }

        for(i=1;i<=K;i++) {

            if(w[i]=='O') sg[i]=sf[i-1]+1;

            else sg[i]=max(sg[i-1],sf[i]);

            tr[s][1]|=(sg[i]-sg[i-1])*(1<<(i-1));

        }

        for(i=1;i<=K;i++) {

            if(w[i]=='I') sg[i]=sf[i-1]+1;

            else sg[i]=max(sg[i-1],sf[i]);

            tr[s][2]|=(sg[i]-sg[i-1])*(1<<(i-1));

        }

    }

    f[0][0][0]=1;

    for(i=0;i<n;i++) {

        int i0=i&1,i1=(i+1)&1;

        for(s=0;s<=mask;s++) {

            //O/I->N

            upd(f[i1][tr[s][0]][1],f[i0][s][0]);

            //O/I->O

            upd(f[i1][tr[s][1]][0],f[i0][s][0]);

            //O/I->I

            upd(f[i1][tr[s][2]][0],f[i0][s][0]);

            //N->N

            upd(f[i1][tr[s][0]][1],f[i0][s][1]);

            //N->O

            upd(f[i1][tr[s][1]][2],f[i0][s][1]);

            //N->I

            upd(f[i1][tr[s][2]][0],f[i0][s][1]);

            //NO->N

            upd(f[i1][tr[s][0]][1],f[i0][s][2]);

            //NO->O

            upd(f[i1][tr[s][1]][0],f[i0][s][2]);

        }

        memset(f[i0],0,sizeof(f[i0]));

    }

    for(i=0;i<=mask;i++) cnt[i]=cnt[i>>1]+(i&1);

    for(s=0;s<=mask;s++) for(i=0;i<3;i++) upd(ans[cnt[s]],f[n&1][s][i]);

    for(i=0;i<=K;i++) printf("%lld\n",ans[i]);

}