b179 cans

题目还是比较有意思也蛮好懂。。。，首先用病毒健串 ，首先dp[i][j][k] 表示 第i天 长度为j，在ac 自动机上走到了k节点的状态多少。当然可以滚动一下，然后考虑两个回答。一个扔进垃圾桶的很简单。只要dp[day][1][k]都加入ans1即可。   关键点是。 如果现在这个串长度大于在ac自动机上走到的点。那么显然删除首字母还在这个位置、反之就去找他的fail指针。然后如果走到了单词结尾节点。就累加ans2...程序大概就是这样（还有一点其实也很易懂）不是单词结尾节点才可以转移。。

哦对了。洗了ac自动机忘了调用调了一个小时的我去一边哭一下会儿。。。

#include<cstdio>
#include<cstdlib>
#include<iostream> 
#include<cstring>
#include<string>
#include<queue>
#include<map>
#include<algorithm>
#define  Clear(s) memset((s),0,sizeof((s)))
#define forup(i,a,b)  for(int i=a;i<=b;i++)
#define fordown(i,a,b)  for(int i=a;i>=b;i--)
using namespace std;
const int N = 1000010;
const int M = 1000010;

struct AC{
    int ch[N][5],f[N];
    int val[N],cnt[N];
    int top;
    int len[N];
    
    void insert(char *T, int num){
        int n = strlen(T);
        int x = 0;
        for(int i = 0; i < n; i++){
            int c = T[i]-'a';
            if( !ch[x][c] ) ch[x][c] = ++top,len[top]=len[x]+1;
            x = ch[x][c];
        }
        val[x] = num;//说明这个是某个字串的末尾。。。    
    }
    void getfail(){
        queue<int> Q;
        for(int c = 0; c < 4; c++){
            int u = ch[0][c];
            if(u) f[u] = 0, Q.push(u);
        }
        
        while( !Q.empty() ){
            int r = Q.front(); Q.pop();
                      if(val[f[r]])  val[r]=1;
            for(int c = 0; c < 4; c++){
                int u = ch[r][c];
            
                if( !u ){ ch[r][c] = ch[ f[r] ][c]; continue; } //补上所有不存在的边
                Q.push(u);    
                int v = f[r];
                while( v && !ch[v][c] ) v = f[v];
                f[u] = ch[v][c];
            }
        }    
    }
    int  find(char *T)
    {int n=strlen(T);
      int x=0;
        for(int i=0;i<n;i++)
        { int c=T[i]-'a';
          x=ch[x][c];
          if(val[x])
          {puts("0 1");exit(0);}
		}
		return x;
	}
	
  
}ac;   

int n,T;
int main(){
   char str[n];
   scanf("%s%d%d",str,&T,&n);
   char s[n];
   forup(i,1,n)
   {scanf("%s",s);
      ac.insert(s,i);
   }
   ac.getfail();
   //
   int dp[2][103][2000];
   int ans1=0,ans2=0;
   int day=0;
   int len=strlen(str);
   int w=ac.find(str);
   dp[day][len][w]=1;
  ///
 /* forup(i,0,ac.top)
  {
  forup(y,0,3) cout<<ac.ch[i][y];
   cout<<endl;}
     /*/
   #define k day
forup(o,1,T)
  {  //cout<<o<<endl;
   day=day^1;
     Clear(dp[day]);
  	  for (int i=0;i<=ac.top;i++)  
  	  if(!ac.val[i])
  	  {
                 for (int j=1;j<=100;j++)  
                   if (dp[1-k][j][i])  
                   {    
                         if (j==1) ans1=(ans1+dp[1-k][j][i])%10007;  
                         else   
                         if (ac.len[i]>j-1)  
                         {    
                                int t=ac.f[i];  
                                dp[k][j-1][t]+=dp[1-k][j][i];   
                                dp[k][j-1][t]%=10007;    
                         }else  
                         {  
                                dp[k][j-1][i]+=dp[1-k][j][i];  
                                dp[k][j-1][i]%=10007;  
                         }  
                         for (int h=0;h<4;h++)  
                         {  
                                dp[k][j+1][ac.ch[i][h]]+=dp[1-k][j][i];   
                                dp[k][j+1][ac.ch[i][h]]%=10007;  
                        
                                if(ac.val[ac.ch[i][h]])
                                    ans2=(ans2+dp[1-k][j][i])%10007; 
							
                         }  
				   }     
			}
    }  
       printf("%d %d\n",ans1,ans2);  
    return 0;
}