4572: [Scoi2016]围棋轮廓线DP KMP

国际惯例的题面:

这种题目显然DP了，看到M这么小显然要状压。
然后就是具体怎么DP的问题。
首先我们可以暴力状压上一行状态，然后逐行转移。复杂度n*3^m+3^(m*2)，显然过不去。

考虑状态的特殊性，每个位置是黑子白子我们并不关心，我们只关心与模板的匹配情况。
于是我们可以f(i,S,x,y)表示我们决策到i行j列，S表示上一行哪些位置和这一行哪些位置能与模板第一行完全匹配，x表示当前行与模板第一行匹配长度，y表示当前行与模板第二行匹配长度。
转移的话就枚举当前行下一个位置填什么颜色棋子(或空着)即可，复杂度n*(3^m)m*c*c*(2^m)*3，显然也凉了。
但是，我们发现如果一行能与模板第一行完全匹配，显然这个匹配位置最少在这一行的位置c。这样就能把次数中的m变成m-c+1。
这样仍旧不能AC。因为这只是普通的状压DP，显然有很多无用状态。

轮廓线DP的巧妙之处在于:因为采用了逐格转移，它压缩的状态可以部分是上一行的，部分是这一行的。
于是我们可以f(i,j,S,x,y)表示我们决策到i行j列，S表示上一行>=j的哪些位置和这一行<j的哪些位置能与模板第一行完全匹配，x表示当前行与模板第一行匹配长度，y表示当前行与模板第二行匹配长度。
我们枚举下一个格子填什么颜色的棋子，进行转移即可。复杂度n*m*3(m-c+1)*(c^2)*3。

代码:

 #include<cstdio>

 typedef long long int lli;

 const int maxs=<<,maxl=;

 const int mod=1e9+;

 char ina[maxl],inb[maxl];

 int faila[maxl],failb[maxl],nxta[maxl][],nxtb[maxl][];

 int f[][maxs][maxl][maxl];

 int n,m,c,q,full,mask,cur;

 lli ans;

 inline lli fastpow(lli base,int tim) {

     lli ret = ;

     while(tim) {

         ret = ( tim &  ) ? ret * base % mod : ret;

         base = ( tim >>=  ) ? base * base % mod : base;

     }

     return ret;

 }

 inline char gid(char c) {

     return c == 'W' ?  : c == 'B' ?  : ;

 }

 inline void kmp(char* s,int* fail,int nxt[maxl][]) {

     for(int i=;i<=c;i++) s[i] = gid(s[i]);

     fail[] = fail[] = ;

     for(int i=,j=;i<=c;i++) {

         while( j && s[j+] != s[i] ) j = fail[j];

         fail[i] = ( j += ( s[j+] == s[i] ) );

     }

     for(int i=;i<=c;i++) for(int cur=;cur<;cur++) {

         int k = i;

         while( k && s[k+] != cur ) k = fail[k];

         nxt[i][cur] = ( k += ( s[k+] == cur ) );

     }

 }

 inline void reset(int f[maxs][maxl][maxl]) {

     for(int i=;i<full;i++) for(int j=;j<=c;j++) for(int k=;k<=c;k++) f[i][j][k] = ;

 }

 int main() {

     scanf("%d%d%d%d",&n,&m,&c,&q) , full =  << ( m - c +  ) , mask = full - ;

     while(q--) {

         scanf("%s%s",ina+,inb+) , kmp(ina,faila,nxta) , kmp(inb,failb,nxtb) , reset(f[cur=]) , f[cur][][][] = ;

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

             reset(f[cur^=]);

             for(int j=;j<full;j++) for(int pa=;pa<c;pa++) for(int pb=;pb<c;pb++) f[cur][j][][] = ( f[cur][j][][] + f[cur^][j][pa][pb] ) % mod;

             for(int j=;j<=m;j++) {

                 reset(f[cur^=]);

                 for(int sta=;sta<full;sta++) for(int pa=;pa<c;pa++) for(int pb=;pb<c;pb++) if( f[cur^][sta][pa][pb] )for(int sel=;sel<;sel++) {

                     int nowa = nxta[pa][sel] , nowb = nxtb[pb][sel] , nowsta = sta;

                     if( j >= c ) nowsta &= ( mask ^ (  << ( j - c ) ) ); // clear bit j - c .

                     if( nowa == c ) nowsta ^=  << ( j - c ) , nowa = faila[nowa]; // set bit j - c .

                     if( nowb == c ) {

                         if( sta & (  << ( j - c ) ) ) continue; // paired .

                         else nowb = failb[nowb];

                     }

                     f[cur][nowsta][nowa][nowb] = ( f[cur][nowsta][nowa][nowb] + f[cur^][sta][pa][pb] ) % mod;

                 }

             }

         }

         ans = fastpow(,n*m);

         for(int sta=;sta<full;sta++) for(int pa=;pa<c;pa++) for(int pb=;pb<c;pb++) ans = ( ans - f[cur][sta][pa][pb] + mod ) % mod;

         printf("%lld\n",ans);

     }

     return ;

 }

もうこの手を　離さないから笑い合えるよ
我已不会再放手所以一起欢笑吧
またこの場所から　ふたり歩き出そう　この道を
让我们再次从这里出发踏上这条道路
朝の澄んだ陽射し　夜空に瞬く星
清晨干净的阳光夜空中闪烁的繁星
たわいもないこと　分け合って感じるぬくもり
不管多琐碎的事互相分享的温暖
ひとりきりの記憶　思い出してしまうたび
每当我回想起独自一人的记忆
いつも鄰で　撫でてくれてたから　笑えた
你总在我身边抚摸着我朝我微笑

巴特西

4572: [Scoi2016]围棋轮廓线DP KMP

最新文章

热门文章

巴特西

4572: [Scoi2016]围棋 轮廓线DP KMP

最新文章

热门文章

4572: [Scoi2016]围棋轮廓线DP KMP