哭~这么好的一个又快值域又大的哈希这么容易被卡QAQ
下面的讨论的哈希方式哈希都是rk哈希

构造两个不同的串使得他们在对unsigned long long自然溢出时哈希值相同。

我们只考虑base为奇数的情况。(如果有人敢拿偶数当base...还写自然溢出...不攻自破)

设字符串序列{s[i]},s[1]="a",s[i]=s[i−1]+not(s[i−1])\{s[i]\},s[1]="a",s[i]=s[i-1]+not(s[i-1])
其中not(s)not(s)表示ss中的'aa'变成'bb','bb'变成'aa',++表示字符串拼接。设t[i]=not(s[i])t[i]=not(s[i])

推一波式子
hsh[s[i]]=hsh[s[i−1]]∗base2i−2+hsh[t[i−1]]hsh[s[i]]=hsh[s[i-1]]*base^{2^{i-2}}+hsh[t[i-1]]
hsh[t[i]]=hsh[t[i−1]]∗base2i−2+hsh[s[i−1]]hsh[t[i]]=hsh[t[i-1]]*base^{2^{i-2}}+hsh[s[i-1]]
则

hsh[s[i]]−hsh[t[i]]=(hsh[s[i−1]]−hsh[t[i−1]])∗(base2i−2−1)hsh[s[i]]-hsh[t[i]]=(hsh[s[i-1]]-hsh[t[i-1]])*(base^{2^{i-2}}-1)

我们只要让hsh[s[i]]−hsh[t[i]]hsh[s[i]]-hsh[t[i]]是2642^{64}的倍数就成功了,因为这部分差全部溢出,哈希值就相同了。

设g[i]=base2i−1−1g[i]=base^{2^{i-1}}-1。因为base是奇数,显然g[1]g[1]是偶数。
i>1i>1时g[i]=(base2i−2−1)(base2i−2+1)=g[i−1](base2i−2+1)g[i]=(base^{2^{i-2}}-1)(base^{2^{i-2}}+1)=g[i-1](base^{2^{i-2}}+1)

则g[i]g[i]至少比g[i−1]g[i-1]多一个因子22
于是
hsh[s[i]]−hsh[t[i]]=(hsh[s[i−1]]−hsh[t[i−1]])∗g[i−1]hsh[s[i]]-hsh[t[i]]=(hsh[s[i-1]]-hsh[t[i-1]])*g[i-1]
hsh[s[i]]−hsh[t[i]]=(hsh[s[1]]−hsh[t[1]])∗g[1]∗g[2]∗...∗g[i−1]hsh[s[i]]-hsh[t[i]]=(hsh[s[1]]-hsh[t[1]])*g[1]*g[2]*...*g[i-1]
当i取12时就有66个2了!
于是只要像上面那样构造就好啦,撒花233

#include<bits/stdc++.h>
using namespace std;
const int N=2050;
char s[N];int n=1;
int main(){
    s[0]='a';
    for(int i=1;i<12;i++,n<<=1)
        for(int j=0;j<n;j++)s[n+j]=s[j]^'a'?'a':'b';
    printf("%d\n%s\n",n,s);
    for(int i=0;i<n;i++)putchar(s[i]^'a'?'a':'b');
    return 0;
}