首页 > 代码库 > HDU2243_考研路茫茫――单词情结
HDU2243_考研路茫茫――单词情结
给出一些词根，问你有多少种长度为L的串包含至少一个词根。
去年就在敲这个题了，今年才敲出来，还是内牛满面之中。。。
要求包含至少一个的情况，需要求出所有的情况，减去一个都没有的情况就可以了。
对于给出的词根，上自动机。然后我们根据tire图可以得出关系状态转移的矩阵。
显然就是矩阵求和了，通过二分幂解决即可。这些地方都有一些技巧可言的。
一开始没有考虑压缩fail指针，考虑了非法的情况，真是wa出翔了。
召唤代码君：
#include <iostream>#include <cstring>#include <cstdio>#include <queue>typedef unsigned long long ll;using namespace std;ll n,L;ll next[55][26],fail[55],tag[55],N;struct Mat{ ll a[55][55]; Mat() { memset(a,0,sizeof a); } Mat operator + (Mat M) const { Mat tmp; for (ll i=0; i<=n; i++) for (ll j=0; j<=n; j++) tmp.a[i][j]=a[i][j]+M.a[i][j]; return tmp; } Mat operator * (Mat M) const { Mat tmp; for (ll i=0; i<=n; i++) for (ll j=0; j<=n; j++) for (ll k=0; k<=n; k++) tmp.a[i][j]+=a[i][k]*M.a[k][j]; return tmp; } Mat power(ll x) { Mat tmp1,tmp2; for (ll i=0; i<=n; i++){ tmp1.a[i][i]=1; for (ll j=0; j<=n; j++){ tmp2.a[i][j]=a[i][j]; } } while (x){ if (x&1) tmp1=tmp1*tmp2; x>>=1,tmp2=tmp2*tmp2; } return tmp1; } void output(){ for (ll i=0; i<=n; i++){ for (ll j=0; j<=n; j++) cout<<a[i][j]<<‘ ‘; cout<<endl; } }};ll add(){ fail[++N]=0,tag[N]=0; for (ll i=0; i<26; i++) next[N][i]=0; return N;}void insert(char s[]){ ll cur=0,k; for (ll i=0; s[i]; i++){ k=s[i]-‘a‘; if (!next[cur][k]) next[cur][k]=add(); cur=next[cur][k]; } tag[cur]=1;}void AC_build(){ queue<int> Q; Q.push(0); while (!Q.empty()){ ll cur=Q.front(),child,k; Q.pop(); for (ll i=0; i<26; i++){ child=next[cur][i]; if (child){ if (!cur) fail[child]=0; else{ for (k=fail[cur]; k && !next[k][i]; k=fail[k]) ; fail[child]=next[k][i]; } Q.push(child); } else next[cur][i]=next[fail[cur]][i]; } }}ll power(ll x,ll y){ ll tot=1; while (y){ if (y&1) tot=tot*x; y>>=1,x=x*x; } return tot;}int main(){ char s[55]; while (cin>>n>>L){ N=0; fail[0]=tag[0]=0; for (ll i=0; i<26; i++) next[0][i]=0; for (ll i=0; i<n; i++) { scanf("%s",s); insert(s); } AC_build(); for (ll i=0; i<=N; i++) if (tag[fail[i]]) tag[i]=1; n=N; Mat cur,E,ans; for (ll i=0; i<=n; i++) for (ll j=0; j<26; j++){ if (!tag[i] && !tag[next[i][j]]) cur.a[i][next[i][j]]++; } for (ll i=0; i<=n; i++) E.a[i][i]=1; Mat tmp=E; ll num=0,here=1; while (L>0){ if (L&1) { ans=ans+tmp*cur.power(L); num+=here*power(26,L); } L>>=1; here=here*power(26,L)+here; tmp=tmp*(cur.power(L)+E); } for(ll i=0; i<=n; i++) num-=ans.a[0][i]; cout<<num<<endl; } return 0;}
HDU2243_考研路茫茫――单词情结
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。