这题其实和之前考的那个无限链一样，而且还是简化版本，，直接建AC自动机然后在trie上dfs，找一个环而且经过的点不为结束点就好了，然而智障的我居然忘记了怎么写AC自动机。。明明那个时候理解的很透彻的说。。看来不复习的话什么东西都会忘记啊。。唉。。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int N=1e5+5; int n; int cnt,ch[N][2]; int fail[N],q[N],val[N]; bool vis[N],ins[N]; char s[N]; inline void insert() { scanf("%s",s); int x=1,len=strlen(s); fo(i,0,len-1) { char c=s[i]-'0'; if (!ch[x][c])ch[x][c]=++cnt; x=ch[x][c]; } val[x]=1; } inline void acmach() { int t=0,w=1; q[0]=1,fail[0]=1; while (t!=w) { int x=q[t++]; fo(i,0,1) { int v=ch[x][i]; if (!v) { ch[x][i]=ch[fail[x]][i]; continue; } int k=fail[x]; while (!ch[k][i])k=fail[k]; k=ch[k][i]; fail[v]=k; val[v]|=val[k]; q[w++]=v; } } } inline bool dfs(int x) { ins[x]=1; fo(i,0,1) { int v=ch[x][i]; if (ins[v])return 1; if (vis[v]||val[v])continue; vis[v]=1; if (dfs(v))return 1; } ins[x]=0; return 0; } int main() { scanf("%d",&n); cnt=1; fo(i,0,1)ch[0][i]=1; fo(i,1,n)insert(); acmach(); if (dfs(1))puts("TAK"); else puts("NIE"); return 0; }