P7114 字符串匹配（题解）

Leap_Frog · 2020-12-05 21:46:05 · 题解

UPD : 补充一份考场代码

Description.

给定 S 求 S=(A+B)^i+C 且 F(A)\le F(C) 的方案数。

### Solution1（84pts？暴力枚举 $C$ 的长度，然后我们设 $X=A+B$，我们需要求出 $X^i+C=S$ 的方案数。也就是找出一个字符串的最小循环节。这是经典问题，直接 Hash + 枚举因数就好了，具体可以看[这里](https://www.luogu.com.cn/blog/daniu/solution-p3538) 然后我们需要求出把 $X$ 拆分成一个 $A+B$ 。因为 $A$ 肯定是一个 $S$ 的前缀，所以我们可以直接暴力预处理出 $F_{i,j}

（设 F_{i,j} 表示 1 到 i 中的所有前缀出现次数为奇数的字符数量，这个东西显然可以二维前缀和，复杂度 O(26\times N)
上面的最小循环节是 O(N\log N) 的，而我们又需要对于每个 C 枚举 i。
而此时 i 必须满足 mxlen_X\ |\ i\ |\ len_X （ mxlen_X 表示字符串 X 的最小循环节。
所以我们最终复杂度是 \sum_{i=1}^{N}\sum_{j|i}1 的。
这个东西应该是 O(N\log N) 的。
总复杂度 O(N\times (\log N+26)) 的。
如果写棵树状数组的话应该可以 O(N\log N\log 26)
~~话说我在考场上甚至忘了这个怎么算，直接打了个大爆搜发现是 1e7 左右~~
贴一个考场 84 分代码。

#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T &x)
{
    x=0;char c=getchar(),f=0;
    for(;c<48||c>57;c=getchar()) if(!(c^45)) f=1;
    for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    f?x=-x:0;
}
const int N=1048585;
struct Hash
{
    typedef unsigned long long ull;ull has1,has2;
    inline bool operator==(Hash b) const {return has1==b.has1&&has2==b.has2;}
    inline Hash operator+(Hash b) const {return(Hash){has1+b.has1,has2+b.has2};}
    inline Hash operator-(Hash b) const {return(Hash){has1-b.has1,has2-b.has2};}
    inline Hash operator*(Hash b) const {return(Hash){has1*b.has1,has2*b.has2};}
    inline Hash operator*(ull x) const {return(Hash){has1*x,has2*x};}
    inline Hash operator+(ull x) const {return(Hash){has1+x,has2+x};}
}B={149ull,1145141ull},has[N],bas[N];int qwq[1005],qaq[1005],qwqt=0;
int Q,n,pc,p[N],ls[N],st[N],tp,f[N][26];char v[N],a[N];
inline void AllInit()
{
    v[0]=v[1]=1,ls[1]=1;
    for(int i=2;i<N;i++)
    {
        if(!v[i]) p[++pc]=i,ls[i]=i;
        for(int j=1;j<=pc&&p[j]*i<N;j++) {v[i*p[j]]=1,ls[i*p[j]]=p[j];if(i%p[j]==0) break;}
    }
}
inline Hash geths(int l,int r) {return has[r]-bas[r-l+1]*has[l-1];}
inline int getmn(int l,int r)//最小循环节
{
    int len=r-l+1;tp=0;
    while(len!=1) st[++tp]=ls[len],len/=ls[len];
    len=r-l+1;for(int i=1;i<=tp;i++)
    {
        int nxt=len/st[i];
        if(geths(l,r-nxt)==geths(l+nxt,r)) len=nxt;
    }
    return len;
}
inline void InitHash()
{
    bas[0]=(Hash){1ull,1ull},has[0]=(Hash){0ull,0ull};
    for(int i=1;i<=n;i++) bas[i]=bas[i-1]*B,has[i]=has[i-1]*B+a[i];
}
inline void InitF()
{
    int now=0,bit=0;memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)
    {
        if(bit&(1<<(a[i]-'a'))) now--;else now++;
        bit^=(1<<(a[i]-'a')),f[i][now]=1;
    }
    for(int i=1,j=0;i<=n;i++) f[i][j]+=f[i-1][j];
    for(int i=1;i<=n;i++) for(int j=1;j<26;j++) f[i][j]+=f[i-1][j]+f[i][j-1]-f[i-1][j-1];
}
inline void ChaiFen(int now,int ggg,long long &x,int hzlim,int tims)
{
    if(now==qwqt+1) return(void)(x+=f[tims*ggg-1][hzlim]);//,printf("F %d %d\n",tims*ggg-1,hzlim)
    for(int i=0;i<=qaq[now];i++) ChaiFen(now+1,ggg,x,hzlim,tims),ggg*=qwq[now];
}
inline void solve()
{
    scanf("%s",a+1),n=strlen(a+1),InitHash(),InitF();
    int bit=0,now=0;long long res=0;
    for(int i=n;i>2;i--)
    {
        if(bit&(1<<(a[i]-'a'))) now--;else now++;
        bit^=(1<<(a[i]-'a'));int nown=i-1,nowlen=getmn(1,nown);
        tp=0;int bf=nown/nowlen;
        while(bf!=1) st[++tp]=ls[bf],bf/=ls[bf];
        sort(st+1,st+tp+1),qwqt=0;
        for(int j=1;j<=tp;j++) if(st[j]!=st[j-1]) qwq[++qwqt]=st[j],qaq[qwqt]=1;else qaq[qwqt]++;
//      for(int j=1;j<=qwqt;j++) printf("<%d,%d>%c",qwq[j],qaq[j],j==qwqt?'\n':' ');
        ChaiFen(1,1,res,now,nowlen);
//      printf("%d : %lld\n",i,res);
    }
    printf("%lld\n",res);
}
int main()
{
    freopen("string.in","r",stdin);
    freopen("string.out","w",stdout);
    AllInit();
    for(read(Q);Q--;) solve();
    fclose(stdin);
    fclose(stdout);
    return 0;
}

Solution2（84pts？

首先，这个出现次数为奇数这个条件很烦人，所以我们观察一下它有没有特殊性质。
首先，我们思考一下，一个串 XX 它不会影响出现次数为奇数的个数。
所以，我们发现 XXXC=S 和 XC=S 的把 X 拆分成 A+B 的方案数是一样呢的。
那么我们可以奇偶分开讨论，把上面的那个 \times log26 或 +26 去掉了。
复杂度 O(N\ln N)

Solution3（100pts？

鸣谢神仙 \color{black}\text{h}\color{red}\text{ehezhou}。
首先我们暴力枚举 X 的长度（X=A+B
然后对于每个长度，我们二分它 i 能取到的最大值。
因为长度越长这个字符串越不可能循环，所以具有单调性。
上面的东西是 \sum_{i=1}^{N}\log\left(\frac{N}{i}\right) 的。
据神仙 \color{black}\text{h}\color{red}\text{ehezhou} 说是 O(N) 的。
我们获得了每个 X 所能取到的最大 i 的长度。
同时，当 X 固定时，当 i\in\{1,3,5...\} 或 i\in\{2,4,6...\} 时，把 X 拆成 A 和 B 的方案数是一样的，所以我们可以 O(1) 统计贡献。
然后枚举 X，在 X 改变时只需要计算增加的那个 X 的贡献就好了。
复杂度均摊 O(N\log 26)。

upd: 感谢神仙 \color{black}\text{h}\color{red}\text{ehezhou} 指出，在统计 X 时必须要 \log26，所以复杂度还是 O(N\log 26) 的，已改正。
upd: 艹，神仙 \color{black}\text{h}\color{red}\text{ehezhou} 要加强 T2 和 T4，把 T2 字符集开成 O(n)，T4 用复杂度为 nk\log^2 的多项式。

完结撒花，反正笔者只会 solution1，还不知道有没有打挂