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;
    }
};

补充：软件开发 , C++ ,