2020 Multi-University Training Contest 8 hdu6863 Isomorphic Strings(哈希/kmp 循环同构 因数分布/约数分布)

题目

a、b循环同构是指两个串的最小表示法相同，

也可以理解成把a变为原来的两倍aa后，其中按照a的长度尺取，能够找到b

样例数T<=1e3，每次给一个长度为n(n<=5e6)的小写字母串，

问是否存在一个n的因数k(k>1)，把长为n的串从头到尾，

每n/k个就分离出一个串，分出s1,...,sk共k个串后，这k个串是循环同构的

若存在输出Yes，否则输出No

保证sumn<=2e7

思路来源

官方题解

题解

粘一发官方题解，大力莽n的约数，约数的个数分布，有一张经典的图

本题中，n<=5e6的时候，max{d(n)}=384，可以用枚举倍数O(nlogn)现打表

首先，预处理前缀哈希值，这样[l,r]就能通过[1,l-1]和[1,r]算

然后，肯定要大力莽n的因数，设字符串长度为k，k<n且k为n的约数

第一段有k种解读方法，把这k个哈希值插到桶里，

后面的(n/k-1)段，只需O(1)检查这个值在不在桶里，

对于每个k，复杂度是O(k+n/k)的，所以总的复杂度是O(n的约数和)的，大概在2e7级别

但考虑到单哈希不一定能行，本题标程采用了三哈希，再乘个3

心得

网友乱搞kmp，O(n*n的约数)都搞过去了，虽然复杂度不大对

然而，感觉自己哈希姿势水平明显不如网友，

单哈希被卡，手写双哈希暴力找还T了，

实际上，可以采用这种第X次哈希，就把桶里的值都赋值为X的方式，

就做到O(1)了，还不用初始化，华师这波板子i了i了

代码

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
namespace RA{
    int rnd(int p){return 1ll*rand()*rand()%p;}
    int rnd(int L,int R){return rnd(R-L+1)+L;}
}
const int N=5e6+5,K=3,M=1e7+5;
const ll bs=29;
int t,n,c;
int hs[K][N],pw[K][N],tong[M];
char s[N];
int mod[K] = {
    //1000003,
    //1000037,
    2000039,
    5000011,
    7000061
};
void init(){
    for(int k=0;k<K;++k){
        pw[k][0]=1;
        for(int i=1;i<N;++i){
            pw[k][i]=pw[k][i-1]*bs%mod[k];
        }
    }
}
int Hs(int k,int l,int r){//第k个模数[l,r]的值
    return (hs[k][r]-1ll*hs[k][l-1]*pw[k][r-l+1]%mod[k]+mod[k])%mod[k];
}
bool check(int k,int d){
    ++c;//第c次检验
    int now=Hs(k,1,d);
    tong[now]=c;
    for(int i=1;i<d;++i){//把循环节都插入桶里标记
        int v=(s[i]-'a'+1);
        now=((now-1ll*v*pw[k][d-1]%mod[k]+mod[k])%mod[k]*bs%mod[k]+v)%mod[k];//将第i个字母从开头去掉 并在末尾添加
        tong[now]=c;
    }
    for(int i=1;i+d-1<=n;i+=d){//O(1)检验每个位置
        now=Hs(k,i,i+d-1);
        if(tong[now]!=c){
            return 0;
        }
    }
    return 1;
}
bool solve(){
    scanf("%d%s",&n,s+1);
    for(int k=0;k<K;++k){
        for(int i=1;i<=n;++i){
            int v=s[i]-'a'+1;
            hs[k][i]=(hs[k][i-1]*bs+v)%mod[k];
        }
    }
    for(int d=1;d<n;++d){
        if(n%d)continue;
        bool ok=1;
        for(int k=0;k<K;++k){
            if(!check(k,d)){
                ok=0;
                break;
            }
        }
        //printf("d:%d\n",d);
        if(ok){
            return 1;
        }
    }
    return 0;
}
int main(){
    init();
    scanf("%d",&t);
    while(t--){
        puts(solve()?"Yes":"No");
    }
    return 0;
}