SRM 557小記

250pt: 水題
500pt：狀態壓縮枚舉，系統測試掛了，囧。。。
1000pt：可以這樣抽象題意，構造長度為len的且包含模式串的總權值為0的串，求這樣的串的個數，字符串由‘U’和‘D’組成，‘U’：+1     ‘D’：-1.
DP，套了個AC自動機，大材小用了- -
狀態很簡單的，轉移的時候要注意轉移到的狀態是否已經包含模式串
[cpp] 
#include<cstdio> 
#include<cstring> 
#include<string> 
#include<vector> 
using  namespace std; 
const int mod = 1000000009; 
const int M = 100; 
const int CD = 26; 
int sz; 
int Q[M]; 
int ch[M][CD]; 
int ID[128]; 
int fail[M]; 
int val[M]; 
void Init(){ 
    fail[0]=0;  val[0]=0; 
    sz=1; 
    memset(ch[0],0,sizeof(ch[0])); 
    for(int i=0;i<26;i++) ID[i+'A']=i; 
} 
void Insert(const char *s){ 
    int p=0; 
    for(;*s;s++){ 
        int c=ID[*s]; 
        if(!ch[p][c]){ 
            memset(ch[sz],0,sizeof(ch[sz])); 
            fail[sz]=val[sz]=0; 
            ch[p][c]=sz++; 
        } 
        p=ch[p][c]; 
    } 
    val[p]=1; 
} 
void Construct(){ 
    int *s=Q,*e=Q,v; 
    for(int i=0;i<CD;i++) { 
        if(ch[0][i]) { 
            fail[ch[0][i]]=0; 
            *e++ = ch[0][i]; 
        } 
    } 
    while(s!=e){ 
        int u=*s++; 
        for(int i=0;i<CD;i++){ 
            if(v=ch[u][i]) { 
                *e++=v; 
                fail[v]=ch[fail[u]][i]; 
                val[v]|=val[fail[v]]; 
            }  else { 
                ch[u][i]=ch[fail[u]][i]; 
            } 
        } 
    } 
} 
class FoxAndMountain{ 
public: 
    int dp[55][55][55][2];//長度 節點  和  是否包含模式串 
    int count(int n, string S) { 
        Init(); 
        Insert(S.c_str()); 
        Construct(); 
        //for(int i=0;i<sz;i++) printf("fail[%d]=%d ",i,fail[i]);puts(""); 
        int H = 26; 
        dp[0][0][0][0]=1; 
        for(int i=0;i<=n;i++) 
        { 
            for(int j=0;j<sz;j++) 
            { 
                for(int h=0;h<H;h++) 
                { 
                    for(int flag=0;flag<2;flag++) 
                    { 
                        if(!dp[i][j][h][flag]) continue; 
                        int x=ch[j][ID['U']],fx=val[x]|flag; 
                        int y=ch[j][ID['D']],fy=val[y]|flag; 
                        dp[i+1][x][h+1][fx]=(dp[i+1][x][h+1][fx]+dp[i][j][h][flag])%mod; 
                        if(h) dp[i+1][y][h-1][fy]=(dp[i+1][y][h-1][fy]+dp[i][j][h][flag])%mod; 
                    } 
                } 
            } 
        } 
        int ans=0; 
        for(int i=0;i<sz;i++) 
        { 
            ans+=dp[n][i][0][1];ans%=mod; 
        } 
        return ans; 
    } 
};