1708：无限链计数
时间限制: 3000 ms 内存限制: 262144 KB
【题目描述】
你可以用前t个小写字母来组成两段都无限长的链.
要求这些链中不能出现n个给定的串中的任何一个，请问有多少个满足条件的不同的无限链呢？
两个相同的两端均无限长的链A和B需要满足的条件为A[i+k]=B[i]对于任意的i都成立，其中k为任意整数。
例如t=2，给定串为{ab,ba}，那么只有 …aaa…与 …bbb…两个，如果给定串为{ab}，则有…aaa…,…bbb…,…bbbbaaa…三个。
【输入】
第一行两个整数t和n，含义如题所述。
接下来n行每行一个字符串表示一个不能出现的串。
【输出】
输出一行一个整数表示答案，如果有无限多个输出-1，保证答案不超过231-1
。
【输入样例】
2 2
ab
ba
【输出样例】
2
【提示】
【数据规模与约定】
对于20%的数据，t≤2，n=1；
对于另外30%的数据，t≤2；
对于100%的数据，n≤1000，t≤6，每个给定的串长度不超过10。
【题解】
首先建立AC自动机。并对AC自动机求强连通分量。
发现如果有非简单环，则肯定是-1因为他可以在一个上跑无限圈在到另一个跑任意圈在回来跑无数圈。
还有就是一条路径上有>=3个环,则-1，（在第一个环上跑无限圈到第二个环跑任意圈，在第三个环跑无数圈）。
然后就是拓扑排序解决有多少条路径保证开头结尾都是环。
代码如下：
#include<bits/stdc++.h> using namespace std; const int N=1e4+5; int n,m,dfn[N],low[N],cnt; char c[12]; struct trie { int er[6],fail,pan; }a[N]; inline void insert() { int len=strlen(c+1),now=0; for(int i=1;i<=len;i++) { if(!a[now].er[c[i]-‘a‘]) a[now].er[c[i]-‘a‘]=++cnt; now=a[now].er[c[i]-‘a‘]; } a[now].pan=1; } queue <int> que; inline void get_fail() { for(int i=0;i<=n-1;i++) if(a[0].er[i]) que.push(a[0].er[i]); while(!que.empty()) { int now=que.front();que.pop(); a[now].pan|=a[a[now].fail].pan; for(int i=0;i<=n-1;i++) { if(a[now].er[i]) { a[a[now].er[i]].fail=a[a[now].fail].er[i]; que.push(a[now].er[i]); } else a[now].er[i]=a[a[now].fail].er[i]; } } } //aczidongji //----------------------------------------------- //tarjan struct pigu { int dao,ne; }aa[N*10],b[N*10]; int last1[N],last2[N],top,size1,panh[N],siz,cnt1,size2,st[N],dui[N],bian[N],dian[N],ru[N],f[N],ge[N]; bool book[N]; inline void lingjiebiao1(int x,int y) { aa[++size1].dao=y; aa[size1].ne=last1[x]; last1[x]=size1; } inline void lingjiebiao2(int x,int y) { b[++size2].dao=y; ru[y]++; b[size2].ne=last2[x]; last2[x]=size2; } inline void dfs(int now) { dfn[now]=low[now]=++cnt1; book[now]=1;st[++top]=now; for(int i=last1[now];i;i=aa[i].ne) { if(dfn[aa[i].dao]==0) { dfs(aa[i].dao); low[now]=min(low[now],low[aa[i].dao]); } else if(book[aa[i].dao]==1) low[now]=min(low[now],dfn[aa[i].dao]); } if(low[now]==dfn[now]) { int k;siz++; do { k=st[top--]; book[k]=0; dui[k]=siz; dian[siz]++; }while(k!=now); } } inline int build_bian() { for(int i=0;i<=cnt;i++) { if(a[i].pan==1) continue; for(int j=0;j<=n-1;j++) { if(a[a[i].er[j]].pan) continue; lingjiebiao1(i,a[i].er[j]); } } for(int i=0;i<=cnt;i++) if(dfn[i]==0&&!a[i].pan) dfs(i); for(int i=0;i<=cnt;i++) for(int j=last1[i];j;j=aa[j].ne) if(dui[i]!=dui[aa[j].dao]) lingjiebiao2(dui[i],dui[aa[j].dao]); else bian[dui[i]]++; for(int i=1;i<=siz;i++) if(bian[i]>dian[i]) { cout<<"-1"; return 0; } else if(bian[i]==dian[i]) panh[i]=1; } inline void tuopu() { for(int i=1;i<=siz;i++) if(ru[i]==0) que.push(i),ge[i]=panh[i]; while(!que.empty()) { int now=que.front();que.pop(); if(ge[now]>=3) { cout<<"-1"; return; } if(panh[now]) f[now]++; for(int i=last2[now];i;i=b[i].ne) { f[b[i].dao]+=f[now]; ru[b[i].dao]--; if(ru[b[i].dao]==0) que.push(b[i].dao); ge[b[i].dao]=max(ge[b[i].dao],ge[now]+panh[b[i].dao]); } } int ans=0; for(int i=1;i<=siz;i++) if(panh[i]) ans+=f[i]; cout<<ans; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%s",c+1); insert(); } get_fail(); if(build_bian()==0) return 0; tuopu(); return 0; }
原文：https://www.cnblogs.com/betablewaloot/p/12158505.html
