SRM 557 小记

250pt: 水题

500pt：状态压缩枚举，系统测试挂了，。。。

1000pt：可以这样抽象题意，构造长度为len的且包含模式串的总权值为0的串，求这样的串的个数，字符串由‘U’和‘D’组成，‘U’：+1 ‘D’：-1.

DP，套了个AC自动机，大材小用了- -

状态很简单的，转移的时候要注意转移到的状态是否已经包含模式串

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