Solution
这题的话。。一开始想的是不是上一个trie就消失了但是后来发现好像我还是太年轻qwq
比较容易联想到。。AC自动机，多串匹配嘛
然后就。。考虑一下AC自动机的匹配过程，就是一直沿着trie上的节点走然后没得走了就跳\(fail\)
那所以如果说我们要构造一个无限长的无法匹配到的串的话，首先在trie上面走的时候就不能碰到某个模式串的结尾节点，然后又因为要构造一个。。无限长的串。。那。。找一个环然后一直绕着走就好了
所以现在的问题就变成了，我们要在AC自动机上面找一个环，这个环中的每个点都不是结尾节点，并且每个点的\(fail\)都不是结尾节点（不然跳过去匹配一下就匹配上了，这个有点坑。。一开始WA了就是这个原因qwq）
那所以求完\(fail\)数组再从根dfs一下就好了
一个小trick就是为了。。方便的话。。我们在建\(fail\)的时候可以直接将失配的地方的\(ch\)直接指到\(fail\)跳转到的地方，这样就不用每次都借助\(fail\)来跳了（貌似是。。几百万年前机房的小伙伴给我科普的奇妙写法qwq）
代码大概长这个样子：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define MOD 1000000007
#define ll long long
using namespace std;
const int N=30010,AC=N,C=2;
int n,m;
char s[N];
namespace Ac{/*{{{*/
queue<int> q;
int ch[AC][C],cnt[AC],fail[AC],nok[AC],vis[AC];
int tot,rt;
void init(){tot=0; rt=0;}
int newnode(){
cnt[++tot]=0; return tot;
}
void insert(char *s,int len){
int now=rt,c;
for (int i=0;i<len;++i){
c=s[i]-'0';
if (!ch[now][c]) ch[now][c]=newnode();
now=ch[now][c];
}
nok[now]=true;
}
void build_fail(){
int u,v;
q.push(rt);
while (!q.empty()){
v=q.front(); q.pop();
for (int i=0;i<C;++i){
if (!ch[v][i]) {ch[v][i]=ch[fail[v]][i];continue;}
if (v){
if (nok[ch[fail[v]][i]])
nok[ch[v][i]]=true;
fail[ch[v][i]]=ch[fail[v]][i];
}
else
fail[ch[v][i]]=0;
q.push(ch[v][i]);
}
}
}
bool dfs(int x){
vis[x]=1;//ing
int u;
for (int i=0;i<C;++i){
u=ch[x][i];
if (nok[u]) continue;
if (vis[u]==1||(vis[u]==0&&dfs(u))) return true;
}
vis[x]=-1;//end
return false;
}
void solve(){
build_fail();
memset(vis,0,sizeof(vis));
bool ans=false;
ans=dfs(rt);
if (ans) printf("TAK\n");
else printf("NIE\n");
}
};/*}}}*/
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
#endif
Ac::init();
scanf("%d",&n);
for (int i=1;i<=n;++i){
scanf("%s",s);
Ac::insert(s,strlen(s));
}
Ac::solve();
}