20221020
easy
规律
显而易见，我们一定需要去找出构造出\(t\)字符串的操作的规律。每次操作都会添加两个字符，为了方便区分这两个字符，我们将每次加入在后面的字符\(a\),记作\(\overline{a}\)。特别地，我们将加入第一个字符的前面的字符加上上划线。接下来所使用的数字表示其为第几个被插入的字符。
\(\overline 1 1\) （\(t\)为空，加入第一个字符）
\(\overline1 2 \overline2 1\)（无法交换，直接加入第二个字符）
\(\overline1 3\overline22\overline31\)（交换\(2\overline2\)，再加入第三个字符）
\(\overline14\overline23\overline32\overline41\)（交换\(3\overline2\)和\(2\overline3\)，再加入第四个字符）
诶，你似乎发现加了上划线的字符按要求操作后，两两之间永远相隔一个字符，而且是后加入的字符的位置永远在先加入的后面。为什么呢？
相邻同类中两两之间永远间隔一个字符
因为构造\(t\)字符串首先有一个交换操作。这个操作将不是首个或最后一个字符的字符两个两个地交换，实质上就是将划线部分（除开首位）整体向左移动了一位，导致开始和结尾两个部分不再满足两两之间永远相隔一个字符的规律，而之后又分别将一个字符加入第二位和倒数第二位，使得开始与结尾两个部分再次满足这个规律。
后加入字符的位置永远在先加入字符之后（对于划线部分）
由上述:
交换的实质是将划线部分整体向左移一位，可知交换时不会改变同类的相对位置。
我们将每次加入在后面的字符\(a\),记作\(\overline{a}\)，保证我们永远将倒数第二位加入的数作为上划线部分，而最后一位永远都不是划线部分，因为首尾不进行交换操作。这样就保证后加入的字符永远处于同类的最后一个位置。
对于非划线部分，同样可以得出相似结论。
综合上述内容
划线部分就是\(\overline1\)_\(\overline2\)_\(\overline3\)_\(\overline4\)_\(\overline5…\)
非划线部分就是\(…5\)_\(4\)_\(3\)_\(2\)_\(1\)
最后得到的就是\(\overline1 5\overline2 4\overline3 3\overline4 2\overline5 1\)
所以它一定是回文的。
并且划线部分的正序一定与非划线部分的倒序相同。
快速获取答案
hash值
可以发现上文所说的划线部分其实就是奇数位，非划线部分就是偶数位。那么我们来考虑如何分别对奇偶位快速求出它们的hash值。假设一次操作前奇偶位的hash值分别是\(h1和h2\)，考虑进行一次操作后会分别对奇偶位的hash值产生什么影响。
首先考虑奇数位，比如:\(\overline12\overline21\)到\(\overline13\overline22\overline31\)其实就相当于将上一次的奇数位全部向左移动了两位（实质上就是交换时将奇数位向左移动了一位，又在末尾添加了一个字符，相当于移动了两位），再在倒数第二位添加的一个新字符。
所以奇数位新的hash值就是\(h1\times B\times B+(s[i]-‘a’)\times B\)。
再考虑偶数位，比如:\(\overline12\overline21\)到\(\overline13\overline22\overline31\)其实就相当于将上一次的偶数位不动（实质上就是交换时偶数位全部向右移动一位，又在末尾添加的一个字符，相当于又向左移动了一位，等于没动），再加上添加在第二位上的新字符。
所以偶数位新的hash值就是\(h2+(s[i]-‘a’)\times (len-2)\)（\(len\)为整个字符串的长度）
每次操作后偶回文前缀hash值之和
通过样例1的解释可以发现，统计\(ans\)数组的时候可能会与某些之前已经统计过的相重复。这显然是一个可以优化的地方，如果重复了，直接将已经算出来的拿来用就好。可以发现如果一个之前构造出来的\(a\)串是现在构造出来的\(t\)串的偶回文前缀时，那\(t\)串计算\(ans\)数组时必然要再算一次\(a\)串的答案，这时我们就可以直接将\(a\)串已经算出来的\(ans\)数组拿来用。那我们怎么确定两个串之间的“利用关系”呢？
确定”利用关系”
若\(a\)串为”\(1221\)“，\(t\)串为”\(1524334251\)“,因为\(a\)串是\(t\)串的偶回文前缀，所以\(t\)串其实为”\(1221331221\)“，也就是说\(t\)串中的\(4，5\)与\(a\)串中的\(1,2\)相同，换言之\(4,5\)与\(1,2\)匹配。如果还没有点想法，那我们就把所有奇数位提出来，\(a\)的就是\(12\)，\(t\)的就是\(12345\)，\(4\)与\(1\)，\(5\)与\(2\)匹配，这是神魔？这不就是\(KMP\)吗！那我们就可以用\(kmp\)的\(nex\)数组来确认它们的”利用关系了”。\(ans[i]=ans[nex[i]]+h1[i]+h2[i]\)
点击查看代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define fo(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
template<typename T>inline void in(T &x){
x=0;int f=0;char c=getchar();
for(;!isdigit(c);c=getchar())f|=(c=='-');
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
x=f?~x+1:x;
}
template<typename T>inline void out(T x){
if(x<0)x=~x+1,putchar('-');
if(x>9)out(x/10);
putchar(x%10^48);
}
const int N=5000005,B=131;
char s[N];
int n,k,nex[N];
unsigned long long ans[N],h2x[N],eans,h1[N],h2[N];
int main(){
scanf("%s",s+1);
n=strlen(s+1);
in(k);
h2x[1]=1;
h1[1]=(s[1]-'a')*B;
h2[1]=s[1]-'a';
ans[1]=h1[1]+h2[1];
nex[1]=0,nex[0]=-1;
eans^=ans[1];
if(1%k==0)out(eans),putchar('\n'),eans=0;
for(int i=2,j=0;i<=n;++i){
s[i]=(ans[i-1]%26+(s[i]-'a'))%26+'a';
while(j>=0&&s[i]!=s[j+1])j=nex[j];
nex[i]=++j;
h2x[i]=h2x[i-1]*B*B;
h1[i]=h1[i-1]*B*B+(s[i]-'a')*B;
h2[i]=h2[i-1]+(s[i]-'a')*h2x[i];
ans[i]=ans[nex[i]]+h1[i]+h2[i];
eans^=ans[i];
if(i%k==0)out(eans),putchar('\n'),eans=0;
}
return 0;
}
原文地址：http://www.cnblogs.com/thanktothelights/p/16808780.html
