题意与poj2778类似，给出禁止出现的字串，求构造长度为L的字符串的方案数。

AC自动机+DP

题目没有要求结果取模。所以需要使用高精，于是写了java

输入字符可能包含不可见字符。。

java中的char和C中的char不一样。。。。

java写AC自动机写丑了。。。 = =。。

由于L不大。所以直接dp就可以了。

dp方程： 

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.math.BigInteger;import java.util.LinkedList;import java.util.Queue; public class poj1625 {    static node pool[];    static int tot,N,M,P;    static int Map[];    public static void main(String[] args) throws IOException{        pool = new node[150];        tot = 0;        BufferedReader cin =                    new BufferedReader(new InputStreamReader(System.in,"ISO-8859-1"));        String[] arg= cin.readLine().split(" ");        N = Integer.parseInt(arg[0]);        M = Integer.parseInt(arg[1]);        P = Integer.parseInt(arg[2]);        String s = cin.readLine();        table(s);        pool[0] = new node(N);        node init = pool[0];        for (int i=0;i
      
        q = new LinkedList
       
        ();        q.offer(root);        root.f=null;        for (int i=0;i
       
      

 

找到了一个强悍的高精度模版（Orz）。。

附C++代码。。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #define rep(i,a,b) for (int i=a;i
             
              
                :: max () - (unsigned long long) BASE * BASE;class bignum{ private: int digits[MAXD]; int D; public: friend ostream &operator<<(ostream &out,bignum &c); inline void trim() { while(D > 1 && digits[D-1] == 0 ) D--; } inline void dealint(long long x) { memset(digits,0,sizeof(digits)); D=0; do { digits[D++]=x%BASE; x/=BASE; } while(x>0); } inline void dealstr(char *s) { memset(digits,0,sizeof(digits)); int len = strlen(s),first = (len + DIG -1)%DIG + 1; D = (len+DIG-1)/DIG; for(int i = 0; i < first; i++) digits[D-1] = digits[D-1]*10 + s[i] - '0'; for(int i = first, d = D-2; i < len; i+=DIG,d--) for(int j = i; j < i+DIG; j++) digits[d] = digits[d]*10 + s[j]-'0'; trim(); } inline char *print() { trim(); char *cdigits = new char[DIG * D + 1]; int pos = 0,d = digits[D-1]; do { cdigits[pos++] = d % 10 + '0'; d/=10; } while(d > 0); reverse(cdigits,cdigits+pos); for(int i = D - 2; i >= 0; i--,pos += DIG) for(int j = DIG-1,t = digits[i]; j >= 0; j--) { cdigits[pos+j] = t%10 + '0'; t /= 10; } cdigits[pos] = '\0'; return cdigits; } bignum() { dealint(0); } bignum(long long x) { dealint(x); } bignum(int x) { dealint(x); } bignum(char *s) { dealstr(s); } inline bool operator < (const bignum &o) const { if(D != o.D) return D < o.D; for(int i = D-1; i>=0; i--) if(digits[i] != o.digits[i]) return digits[i] < o.digits[i]; return false; //equal } bool operator > (const bignum & o)const { return o < *this; } bool operator <= (const bignum & o)const { return !(o < *this); } bool operator >= (const bignum & o)const { return !(*this < o); } bool operator != (const bignum & o)const { return o < *this || *this < o; } bool operator == (const bignum & o)const { return !(o < *this) && !(*this < o); } bignum &operator++() { *this = *this + 1; return *this; } bignum operator ++(int) { bignum old = *this; ++(*this); return old; } inline bignum operator << (int p) const { bignum temp; temp.D = D + p; for (int i = 0; i < D; i++) temp.digits [i + p] = digits [i]; for (int i = 0; i < p; i++) temp.digits [i] = 0; return temp; } inline bignum operator >> (int p) const { bignum temp; temp.D = D - p; for (int i = 0; i < D - p; i++) temp.digits [i] = digits [i + p]; for (int i = D - p; i < D; i++) temp.digits [i] = 0; return temp; } bignum &operator += (const bignum &b) { *this = *this + b; return *this; } bignum &operator -= (const bignum &b) { *this = *this - b; return *this; } bignum &operator *= (const bignum &b) { *this = *this * b; return *this; } bignum &operator /= (const bignum &b) { *this = *this / b; return *this; } bignum &operator %= (const bignum &b) { *this = *this % b; return *this; } inline bignum operator + (const bignum &o) const { bignum sum = o; int carry = 0; for (sum.D = 0; sum.D < D || carry > 0; sum.D++) { sum.digits [sum.D] += (sum.D < D ? digits [sum.D] : 0) + carry; if (sum.digits [sum.D] >= BASE) { sum.digits [sum.D] -= BASE; carry = 1; } else carry = 0; } sum.D = max (sum.D, o.D); sum.trim (); return sum; } inline bignum operator - (const bignum &o) const { bignum diff = *this; for (int i = 0, carry = 0; i < o.D || carry > 0; i++) { diff.digits [i] -= (i < o.D ? o.digits [i] : 0) + carry; if (diff.digits [i] < 0) { diff.digits [i] += BASE; carry = 1; } else carry = 0; } diff.trim (); return diff; } inline bignum operator * (const bignum &o) const { bignum prod = 0; unsigned long long sum = 0, carry = 0; for (prod.D = 0; prod.D < D + o.D - 1 || carry > 0; prod.D++) { sum = carry % BASE; carry /= BASE; for (int j = max (prod.D - o.D + 1, 0); j <= min (D - 1, prod.D); j++) { sum += (unsigned long long) digits [j] * o.digits [prod.D - j]; if (sum >= BOUND) { carry += sum / BASE; sum %= BASE; } } carry += sum / BASE; prod.digits [prod.D] = sum % BASE; } prod.trim (); return prod; } inline bignum range (int a, int b) const { bignum temp = 0; temp.D = b - a; for (int i = 0; i < temp.D; i++) temp.digits [i] = digits [i + a]; return temp; } inline double double_div (const bignum &o) const { double val = 0, oval = 0; int num = 0, onum = 0; for (int i = D - 1; i >= max (D - 3, 0); i--, num++) val = val * BASE + digits [i]; for (int i = o.D - 1; i >= max (o.D - 3, 0); i--, onum++) oval = oval * BASE + o.digits [i]; return val / oval * (D - num > o.D - onum ? BASE : 1); } inline pair 
               
                 divmod (const bignum &o) const { bignum quot = 0, rem = *this, temp; for (int i = D - o.D; i >= 0; i--) { temp = rem.range (i, rem.D); int div = (int) temp.double_div (o); bignum mult = o * div; while (div > 0 && temp < mult) { mult = mult - o; div--; } while (div + 1 < BASE && !(temp < mult + o)) { mult = mult + o; div++; } rem = rem - (o * div << i); if (div > 0) { quot.digits [i] = div; quot.D = max (quot.D, i + 1); } } quot.trim (); rem.trim (); return make_pair (quot, rem); } inline bignum operator / (const bignum &o) const { return divmod (o).first; } inline bignum operator % (const bignum &o) const { return divmod (o).second; } inline bignum power (int exp) const { bignum p = 1, temp = *this; while (exp > 0) { if (exp & 1) p = p * temp; if (exp > 1) temp = temp * temp; exp >>= 1; } return p; } inline bignum factorial() const { bignum ans = 1, num = *this; if (num == 0 || num == 1) return ans; while (!(num < 0 || num == 0)) { ans = ans * num; num = num - 1; } return ans; }};ostream &operator<<(ostream &out, bignum &c){ out<
                
                 > (istream &in,bignum &c){ char s[500]; in>>s; c = s; return in;}///-----------以上高精度模版----------------///-----------以下AC自动机模版----------------const int MAXC = 50;const int MAXN = 110;struct Tnode{ Tnode *ch[MAXC]; Tnode *f; int flag; void reset(){ f=NULL; flag=0; memset(ch,0,sizeof(ch)); }} *init;Tnode pool[MAXN];int cnt ;int tab[512];int N,M,P;int lx(char c){ return tab[c];}void insert(char *s){ Tnode *now = init; while(*s){ int p = lx(*s++); if (!now->ch[p]){ now->ch[p]=&pool[++cnt]; pool[cnt].reset(); } now = now->ch[p]; } now->flag++;}queue 
                 
                   q;void build(){ q.push(init); while(!q.empty()){ Tnode *now = q.front(); q.pop(); rep(i,0,MAXC){ if (now->ch[i]){ Tnode *p=now->f; while(p && !p->ch[i]) p=p->f; now->ch[i]->f = p?p->ch[i]:init; q.push(now->ch[i]); } } } init->f=init; rep(i,0,MAXC) if (init->ch[i]) q.push(init->ch[i]); else init->ch[i]=init; while(!q.empty()){ Tnode *now = q.front(); if (now->f->flag) now->flag=true; q.pop(); rep(i,0,MAXC) if (now->ch[i]) q.push(now->ch[i]); else now->ch[i]=now->f->ch[i]; }}///-----------以上AC自动机模版----------------char s[100];bignum f[60][MAXN];void dp(){ f[0][0]=1; rep(i,0,M) rep(j,0,cnt+1){ if (pool[j].flag) continue; rep(k,0,N) f[i+1][pool[j].ch[k]-init]+=f[i][j]; } bignum ans; rep(i,0,cnt+1){ if (pool[i].flag) continue; ans+=f[M][i]; } cout << ans << endl;}int main(){ freopen("in.txt","r",stdin); scanf("%d%d%d\n",&N,&M,&P); scanf("%s",s); pool[0].reset(); init=&pool[0]; rep(i,0,N) tab[s[i]]=i; rep(i,0,P){ scanf("%s",s); insert(s); } build(); dp();}