题目
题解

Solution

如果 $base$base是偶数，那么 $a.........aaa(\>64$a.........aaa(>64个 $a)$a)与 $ba.......aa(a$ba.......aa(a的数量为前面那么串 $a$a的数量 $-1)$−1)，这两个串长度相同， $hash$hash值相同，显然串是不同的，这样就卡掉了。
如果 $base$base是奇数，就比较麻烦了。
看 $vfk$vfk的做法吧：
如果 $base$base是奇数的话，现在只考虑 $a$a、 $b$b两个字母。
$a\mid b$a∣b表示 $a$a能整除 $b$b。（ $orz$orz具体数学）
设数学上的函数 $not\left(S\right)$not(S)表示把字符串 $S$S中每个位置的 ${\prime }^{}{a}^{\prime }$′a′变成 ${\prime }^{}{b}^{\prime }$′b′，把 ${\prime }^{}{b}^{\prime }$′b′变成 ${\prime }^{}{a}^{\prime }$′a′后形成的字符串。
$strA.strB$strA.strB代表字符串串联。
$\mid str\mid$∣str∣表示字符串 $str$str的长度。
设字符串序列 $orzstr\left[i\right]$orzstr[i]， $orzstr\left[1\right]=\mathrm{\"}a\mathrm{\"},orzstr\left[i\right]=orzstr[i-1].not\left(orzstr\right[i-1\left]\right)$orzstr[1]="a",orzstr[i]=orzstr[i−1].not(orzstr[i−1])
那么 $\mid orzstr\left[i\right]\mid =\mid orzstr[i-1]\mid \ast 2$∣orzstr[i]∣=∣orzstr[i−1]∣∗2。显然这是等比数列，得到： $\mid orzstr\left[i\right]\mid =\mid orzstr\left[1\right]\mid .2^{i-1}=2^{i-1}$∣orzstr[i]∣=∣orzstr[1]∣.2i−1=2i−1
设 $hash\left(str\right)$hash(str)为 $str$str的哈希值。
则：
$hash\left(orzstr\right[i\left]\right)=hash\left(orzstr\right[i-1\left]\right)\ast bas{e}^{\mid }not\left(orzstr\right[i-1\left]\right)\mid +hash\left(not\right(orzstr[i-1]\left)\right)$hash(orzstr[i])=hash(orzstr[i−1])∗base∣not(orzstr[i−1])∣+hash(not(orzstr[i−1]))
$=hash\left(orzstr\right[i-1\left]\right)\ast bas{e}^{2^{i-2}}+hash\left(not\right(orzstr[i-1]\left)\right)$=hash(orzstr[i−1])∗base2i−2+hash(not(orzstr[i−1]))
$hash\left(not\right(orzstr\left[i\right]\left)\right)=hash\left(not\right(orzstr[i-1]\left)\right)\ast bas{e}^{2^{i-2}}+hash\left(orzstr\right[i-1\left]\right)$hash(not(orzstr[i]))=hash(not(orzstr[i−1]))∗base2i−2+hash(orzstr[i−1])
两式相减：
$hash\left(orzstr\right[i\left]\right)-hash\left(not\right(orzstr\left[i\right]\left)\right)$hash(orzstr[i])−hash(not(orzstr[i]))
$=\left(hash\right(orzstr[i-1])\ast bas{e}^{2^{i-2}}+hash(not\left(orzstr\right[i-1\left]\right)\left)\right)-\left(hash\right(not\left(orzstr\right[i-1\left]\right))\ast bas{e}^{2^{i-2}}+hash(orzstr[i-1]\left)\right)$=(hash(orzstr[i−1])∗base2i−2+hash(not(orzstr[i−1])))−(hash(not(orzstr[i−1]))∗base2i−2+hash(orzstr[i−1]))
$=\left(hash\right(orzstr[i-1])-hash(not\left(orzstr\right[i-1\left]\right)\left)\right)\ast (bas{e}^{2^{i-2}}-1)$=(hash(orzstr[i−1])−hash(not(orzstr[i−1])))∗(base2i−2−1)
这让我们发现， $hash\left(orzstr\right[i\left]\right)-hash\left(not\right(orzstr\left[i\right]\left)\right)$hash(orzstr[i])−hash(not(orzstr[i]))似乎是个神奇的东西。而我们的目的实际上是要找两个字符串 $strA,strB$strA,strB使得
$hash\left(strA\right)=hash\left(strB\right)\left(mod\right(2^{64}\left)\right)$hash(strA)=hash(strB)(mod(264))
相当与
$2^{64}\mid \left[hash\right(strA)-hash(strB\left)\right]$264∣[hash(strA)−hash(strB)]
设数列 $f\left[i\right]$f[i]， $f\left[i\right]=hash\left(orzstr\right[i\left]\right)-hash\left(not\right(orzstr\left[i\right]\left)\right)$f[i]=hash(orzstr[i])−hash(not(orzstr[i]))
这样就有：
$f\left[i\right]=f[i-1]\ast (bas{e}^{2^{i-2}}-1)$f[i]=f[i−1]∗(base2i−2−1)
还是有点不爽啊……我们再设数列 $g\left[i\right]$g[i]， $g\left[i\right]=bas{e}^{2^{i-1}}-1$g[i]=base2i−1−1
于是能写成：
$f\left[i\right]=f[i-1]\ast g[i-1]$f[i]=f[i−1]∗g[i−1]
则 $f\left[i\right]=f\left[1\right]\ast g\left[1\right]\ast g\left[2\right]\ast ...\ast g[i-1]$f[i]=f[1]∗g[1]∗g[2]∗...∗g[i−1]
然后发现一个神奇的事情？
$base$base是奇数，则 $base$base的任意正整数次方也一定是奇数。所以对于任意的 $i$i必有 $g\left[i\right]$g[i]为偶数，所以 $2^{i-1}\mid f\left[i\right]$2i−1∣f[i]
问题是不是结束了呢……发现没有……这样的话我们要使 $2^{64}\mid f\left[i\right]$264∣f[i]，至少得让 $i=65$i=65……然后发现 $\mid orzstr\left[65\right]\mid$∣orzstr[65]∣是个天文数字。
发现我们刚才那样分析太坑爹了……
$i\>1$i>1时有：
$g\left[i\right]=bas{e}^{2^{i-1}}-1=(bas{e}^{2^{i-2}}-1)\ast (bas{e}^{2^{i-2}}+1)=g[i-1]\ast$g[i]=base2i−1−1=(base2i−2−1)∗(base2i−2+1)=g[i−1]∗一个偶数
而 $g\left[1\right]$g[1]显然是偶数吧……
那么 $4\mid g\left[2\right]$4∣g[2]， $8\mid g\left[3\right]...$8∣g[3]...
也就是说 $2^i\mid g\left[i\right]$2i∣g[i]
所以 $f\left[i\right]$f[i]实际上有：
$\left(2^1\right)\ast \left(2^2\right)\ast \left(2^3\right)\ast ...\ast \left(2^{i-1}\right)\mid f\left[i\right]$(21)∗(22)∗(23)∗...∗(2i−1)∣f[i]
$2^{i\ast (i-1)/2}\mid f\left[i\right]$2i∗(i−1)/2∣f[i]
当 $i$i取 $12$12时，就有 $66$66个 $2$2了哟！
这就是卡 $base$base为奇数时的方法。 $orzstr\left[12\right]$orzstr[12]和 $not\left(orzstr\right[12\left]\right)$not(orzstr[12])即为所求。

而读入中 $base$base既有奇数又有偶数，直接在奇数构造的字符串后面加 $64$64个 $a$a就可以了。

Code

#include<cstdio>
#include<cstring>
int i,now,j;
char s[1<<12];
int main(){
	puts("2113 1024");
	putchar(s[now=1]+97);
	for (i=0;i<11;i++,now<<=1)
		for (j=0;j<now;j++) putchar((s[now+j]=s[j]^1)+97);
	for (i=0;i<65;i++) putchar('a');
}