LG7114 扭曲做法

· · 题解

2020 年 12 月 5 日……学习字符串……30min……折戟沉沙……以前的我！（大雾）

昨天躺床上无聊想出来这题的一个巨大扭曲做法，丢上来分享一下。

首先如果你考虑枚举 C 那你一开始就走偏了，我们枚举 AB……诶我偏不，咱就枚举 C 试一下？

枚举 C 就相当于枚举了 (AB)^k，可能的 AB 都是这个串的整循环节。根据 border 理论那一套（这里就不给证明了），m 是 border 代表 n-m 是周期，而一个整循环串的最小周期必然是最小整周期。那么可以 kmp 求出每个前缀的最小整周期。又有弱周期定理（WPL），若 a 和 b 都是周期且 a+b\le n 则 \gcd(a,b) 是周期。那么可以推知所有周期都是这个最小周期的倍数，否则导出更小的周期。

那么设最小循环节长度为 x，考虑若有一个合法的 A，x(i-1)\le|A|<xi，那么合法的 AB 个数即为 k 的倍数中不小于 i 的个数。而发现对于一个 i，这样合法的 A 的个数只与 i 的奇偶性有关，那么可以对 i 的两种奇偶性分别树状数组 O(n\log|\Sigma|) 算出这样合法的 A 的个数，严格 O(n) 也是可以的其他题解说过这个事情我就不讨论了。

那么考虑对两种 i 的奇偶性分别计算所有 A 对应的合法 AB 的总个数。考虑 k 的每个因数 d，若 d 是偶数则 d 被计算了 \dfrac12d 次，否则若 i 是奇数则是 \dfrac12d+\dfrac12，若 i 是偶数则是 \dfrac12d-\dfrac12 次。那么发现我们只需要计算每个数的约数个数，约数和，奇约数个数。前两者容易线性筛，后者其实就是 d(n)-[2|n]d(\dfrac12n)，d 这里代表约数个数函数。

最后在 1 是奇数且 |A|=x(i-1) 时 A 是空串需要特判一下，特判的式子跟上面差不多不写出来了。然后你发现这题就做完了，复杂度还是 O(n\log|\Sigma|) 或者 O(n)。

线性筛太折磨了写了个调和级数筛日过去了……

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll readint(){
    ll x=0;
    bool f=0;
    char c=getchar();
    while(!isdigit(c)&&c!='-') c=getchar();
    if(c=='-'){
        f=1;
        c=getchar();
    }
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return f?-x:x;
}
const int maxn=(1<<20)+5;
int d0[maxn],dd[maxn];
ll d1[maxn];
int n;
char s[maxn];
int nxt[maxn];
int cnt[26];
struct qr{
    int x;
    ll k;
};
vector<qr> q[maxn];
inline int lowbit(int x){
    return x&-x;
}
int c[27];
void modify(int x,int k){
    while(x<=26){
        c[x]+=k;
        x+=lowbit(x);
    }
}
int query(int x){
    int s=0;
    while(x){
        s+=c[x];
        x-=lowbit(x);
    }
    return s;
}
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    for(int i=1;i<maxn;i++) for(int j=1;i*j<maxn;j++){
        d0[i*j]++;
        d1[i*j]+=i;
    }
    for(int i=1;i<maxn;i++) dd[i]=d0[i]-(i%2==0?d0[i/2]:0);
    int T=readint();
    while(T--){
        scanf("%s",s+1);
        n=strlen(s+1);
        int u=0;
        for(int i=2;i<=n;i++){
            while(u&&s[u+1]!=s[i]) u=nxt[u];
            if(s[u+1]==s[i]) u++;
            nxt[i]=u;
        }
        int cnt2=0;
        for(int i=1;i<=n;i++) vector<qr>().swap(q[i]);
        ll ans=0;
        memset(cnt,0,sizeof(cnt));
        for(int i=n-1;i>0;i--){
            cnt[s[i+1]-'a']++;
            cnt2+=cnt[s[i+1]-'a']%2==1?1:-1;
            int x=i%(i-nxt[i])==0?i-nxt[i]:i;
            q[x-1].push_back({cnt2,(d1[i/x]+dd[i/x])/2});
            if(x!=i){
                q[x-1].push_back({cnt2,(dd[i/x]-d1[i/x])/2});
                q[x*2-1].push_back({cnt2,(d1[i/x]-dd[i/x])/2});
                ans+=(d1[i/x]-dd[i/x])/2-d0[i/x]+dd[i/x];
            }
        }
        memset(cnt,0,sizeof(cnt));
        memset(c,0,sizeof(c));
        cnt2=0;
        for(int i=1;i<n;i++){
            cnt[s[i]-'a']++;
            cnt2+=cnt[s[i]-'a']%2==1?1:-1;
            modify(cnt2+1,1);
            for(qr x:q[i]) ans+=1ll*query(x.x+1)*x.k;
        }
        printf("%lld\n",ans);
    }
    #ifdef LOCAL
    fprintf(stderr,"%d\n",(int)clock());
    #endif
    return 0;
}

我感觉这个做法巨大扭曲，不知道为什么混进来一点数论内容。直觉上整循环次数的约数应该有更优美的性质，有没有好一点的做法把这玩意去掉啊。

有 没 有 老 哥 教 教 我 啊

感觉是第一万次说这句话了，蒋队这样真正的强者都是自己搞清楚两个牛逼做法的联系的。