P2375 [NOI2014] 动物园 题解

· · 题解

前置知识

Border Theory ，KMP 。

思路

  1. 看到小于等于 {|s|\over2} 的 border 个数，如果你学过 Border Theory，一定会想起一个定理，

    s的所有长度大于 \left \lfloor {|s|\over2} \right \rfloor 的 border 长度与 |S| 构成一个等差数列 。

  2. 考虑有人没学过，我们可以严谨证明一下。证明这个定理之前需要先证明另一个定理。

    若 p,q 均为 s 的周期，且 p+q \le |s| ，则 \gcd(p,q) 也是 s 的周期 。（如果 \forall i\le |s|-T,s_i=s_{i+T}，则称 T 为 s 的周期。）

    看起来很抽象其实证明比较简单，我们先设 p>q 。

    当 i\le q 时 ，s_i=s_{i+p}=s_{i+p-q} 即 s_i=s_{i+(p-q)} 。

    当 i>q 时 ，s_i=s_{i-q}=s_{i-q+p} 即 s_i=s_{i+(p-q)} 。

    上面都是根据周期的定义直接得到的，所以我们证到了 p-q 也是 s 的周期。根据辗转相减法可以知道 \gcd(p,q) 也是 s 的周期。（就是一直套娃，套到 \gcd 中有一个为零时，另一个数就是 \gcd 同时也是被证明的周期）

  3. 好回到一开始的定理，我们先假设最长 border 长度为 n-p ,另有一长度为 n-q 的 border 。那么 p,q 是周期，且 p,q\le {n\over 2} ,所以 p+q\le n ,根据刚才证的定理可以知道 \gcd(p,q) 也是周期，那么 n-\gcd(p,q) 就是 border。又因为 n-p 是最长 border，所以 p\le \gcd(p,q) ，就可以直接得到 p=\gcd(p,q) 也就是 p\mid q ，这告诉我们所有可能的 q 都是 p 的倍数。由于限制只有长度大于 {n\over 2} ，所以一定是连续存在的，就构成了一个等差数列。

  4. 有了这个结论，回到这道题。我们只要找到小于等于 {n\over 2} 的最长的 border 就可以快速算答案了（预处理出 border 的个数）。然后根据等差数列的性质，先用原长和最长 border 求出公差，就可以列式快速算了。这种写法的时间复杂就非常好理解是 O(n) 的。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10,mod=1e9+7;
char s[N];
int nxt[N],num[N],ans,jg[N];
void solve()
{
    cin>>(s+1);
    int n=strlen(s+1);
    num[1]=nxt[1]=0;
    for(int i=2,j=0;i<=n;i++)
    {
        while(s[j+1]!=s[i]&&j)j=nxt[j];
        if(s[j+1]==s[i])j++;
        nxt[i]=j;
        num[i]=num[j]+(j?1:0); 
    }
    ans=1;
    for(int i=2;i<=n;i++)
    {
        int k1=nxt[i],d=i-k1;   
        if(k1*2<=i){jg[i]=num[k1]+(k1?1:0),ans=ans*(jg[i]+1)%mod;continue;}//特判最长的小于等于n/2的情况
        int x=(2*k1-i)/(2*d),k2=k1-x*d;
        if(x*(2*d)!=2*k1-i)k2=nxt[k2];
        jg[i]=num[k2]+(k2?1:0);
        ans=ans*(jg[i]+1)%mod;
    }
    cout<<ans<<'\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--)solve();
}