@OceanEye5年前
12/13
01:50
AC自动机上DP
大概要点就是记得取模，其他的都很裸，这个数据范围也是随便跑的。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <cmath> #include <iostream> #include <bits/stdc++.h> #define ll long long #define INF 1000000000 #define p(x) ('0'<=x&&x<='9') #define For(i,a,b) for(int i=a;i<=b;++i) #define Rev(i,a,b) for(int i=a;i>=b;--i) char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } #undef p #define pb push_back #define pq priority_queue using namespace std; #define N 10010 #define BASE 'A' int root,pcnt; struct node { int sn[26],fail; bool The_end; int& operator[] (const int &x) { return sn[x]; } }pool[N]; int n,m; char s[70][110]; void init() { int node,_; char cur; read(n); read(m); For(i,1,n) scanf("%s",s[i]); root=pcnt=1; For(i,1,n) { node=root; _=0; while(s[i][_]) { cur=s[i][_]-BASE; if(!pool[node][cur]) pool[node][cur]=++pcnt; node=pool[node][cur]; ++_; } pool[node].The_end=1; } pool[1].fail=0; int q[65540],x; unsigned short int he,ta; he=ta=0; q[++he]=1; while(he!=ta) { x=q[++ta]; For(j,0,25) { node=pool[x][j]; if(!node) continue; q[++he]=node; pool[node].The_end|=pool[x].The_end; _=pool[x].fail; while(!pool[_][j]&&_) _=pool[_].fail; pool[node].fail=_?pool[_][j]:root; pool[node].The_end|=pool[pool[node].fail].The_end; } } } #undef BASE #define MOD 10007 int ksm(int x,int t) { int ret=1,cur=x; for(;t;t>>=1) { if(t&1) ret=(ret*cur)%MOD; cur=(cur*cur)%MOD; } return ret; } int ans; int dp[110][N]; bool inq[110][N]; void Tree_DP(int top) { int node,x,dep; pair<int,int> q[65540]; unsigned short int he,ta; he=ta=0; q[++he]=make_pair(1,0); dp[0][1]=1; while(he!=ta) { ++ta; x=q[ta].first; dep=q[ta].second; if(pool[x].The_end) continue; dp[dep][x]%=MOD; if(dep==top) { ans=(ans-dp[dep][x])%MOD; continue; } For(i,0,25) { node=x; while(!pool[node][i]&&node) node=pool[node].fail; node=node?pool[node][i]:root; dp[dep+1][node]+=dp[dep][x]; if(inq[dep+1][node]) continue; q[++he]=make_pair(node,dep+1); inq[dep+1][node]=1; } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); srand(time(NULL)); #ifdef LOCALTEST freopen("input.txt", "r", stdin); #endif init(); Tree_DP(m); printf("%d",(ans+ksm(26,m)+MOD)%MOD); return 0; } |