长了集训Day5

世界尽头

与

冷酷仙境

---

上午

T1 无限之环

猜了一下结论，最长公共前缀长度一定不超过两倍的最长串长度

没想到猜中了，然而统计答案出了一点问题，被扣了50pts

void insert(ll x){
    ll pos=0;
    rep(i,1,lenMax*2){
        ll ch=s[x][i]-'0';
        if(!trie[pos][ch])
            trie[pos][ch]=++tot;
        pos=trie[pos][ch];
        count_end[pos]++;
    }
}
void query(ll x){
    ll pos=0;
    rep(i,1,lenMax*2){
        ll ch=s[x][i]-'0';
        pos=trie[pos][ch];
        if(count_end[pos]>1) ans=max(ans,i); 
    }
}

用count计数器统计经过的点，经过两次以上的点即为公共前缀

下午

T1 DNA序列

WA机发力了

比赛时毫无疑问地爆蛋了

解决思路，所有非法串做一遍WA机，把结束位置在踹树上做flag标记，踹树上任一位置一定是某个非法串的前缀

在某个位置跳fail指针，寻找该位置后缀是否有flag标记，即检验该位置后缀是否含有某个非法串，如果找到，同样用flag标记该位置

在踹树上有直接连接的两点u,v，如果都没有flag，则计a[i][j]=1表示u带着后缀经一次转移转移到v有一种方案（转移后等同于将v加入构造串，形成v的后缀，已经被确定不含病毒串）

借用一个结论，对a数组做n次矩阵乘法，求出任一点经n次转移转移到另一点的方案数，用快速幂优化

答案为对aⁿ[0][i](0<=i&&i<=踹树大小)的求和