题解 P7114 【字符串匹配（洛谷民间数据）】
Azazеl
·
·
题解
闲话：考场上想到了 \texttt{100pts} 的思路，然后自己想多了加了个不必要的优化然后 WA 到样例过不了无奈改暴力。（在T2上用了正解的时间，得到了暴力<可能都没有>的分数）
题意
---
#### 题解
$~~~~$首先，我们枚举 $AB$ 的长度，然后我们可以通过 $\texttt{Hash}$ 在 $\Theta(\sum_{i=2}^{len-1} \dfrac{len}{i})$ 的时间复杂度内算出每次重复了多少次。而且这个东西非常大概率跑不满。
$~~~~$ 然后我们假设 $AB$ 重复了 $k$ 次，那么可以有 $0\backsim(k-1)$ 次 $AB$ 的重复放在后面的 $C$ 字符串里，而且我们发现 $AB$ 重复奇数次和偶数次对于 $C$ 的奇数次出现的字符数的贡献是相同的，而这个次数我们可以 $\mathcal{O(n)}$ 预处理后每次 $\mathcal{O(1)}$ 得到。
$~~~~$ 最后我们对于某一个重复奇数次的字符数量，我们可以用维护 $\leq$ 某个出现次数的 $AB$ 划分方案，那么这显然是一个动态前缀和，用树状数组，那么这部分的时间复杂度是 $\mathcal{O(\log 26)}$ ，每次动态更新时由于只多了一个字符，所以也只用更新一个 $\mathcal{O(\log 26)}$ 的时间复杂度。
$~~~~$ 以下是笔者的废话。
$~~~~$ 到这里这道题已经做完了，然后我考场上认为上面一个一个跳太低效了，而且数据范围给出的是 $|S|$ 在某个 $2$ 的幂以内，但却没有用到 $\mathcal{O(\log n)}$ （~~更主要的原因是我不会算第一个式子~~）所以我想到 倍增/二分出重复次数，那么对于一个某个字符串 $S$ ，设其 $\texttt{HASH}$ 值为 $h$ ，$base^{|S|}=p$ ，则其重复 $k$ 次的 $\texttt{HASH}$ 值应为 $\sum_{i=0}^{k-1} h\times p^i$ 然后一波等比数列求和可以算出来。事实上这是没有问题的，但我们要考虑到 $\texttt{Hash}$ 是由自然溢出/取模的，只是平时都不太容易溢出/取模次数不同步，但我们对大数作乘方运算后，它容易溢出不同步，然后因为精度原因 WA 掉。
$~~~~$ ~~然后我就改成 $len^2$ 暴力亲手送掉1= QAQ~~
#### 代码
```cpp
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define ll long long
#define ull unsigned long long
using namespace std;
const ull base=13331;
int cnt[1500000],t[30];
char s[1500000];
ull Hash[1500000],p[1500000];
ll len;
ll tr[30];
ull Get_Hash(ll l,ll r)
{
return Hash[r]-Hash[l-1]*p[r-l+1];
}
inline ll lowbit(ll x){return x&(-x);}
void clearTr(){memset(tr,0,sizeof(tr));}
void add(ll x,ll val){for(;x<=26;x+=lowbit(x))tr[x]+=val;}
ll query(ll x){ll ret=0;for(;x;x-=lowbit(x)) ret+=tr[x];return ret;}
int main() {
// freopen("data25.in","r",stdin);
// freopen("data25.out","w",stdout);
ll T;
scanf("%lld",&T);
while(T--)
{
memset(Hash,0,sizeof(Hash));
memset(cnt,0,sizeof(cnt));
clearTr();
for(ll i=0;i<=26;i++) t[i]=0;
scanf("%s",s+1);
len=strlen(s+1);
p[0]=1;
for(ll i=1;i<=len;i++)
{
Hash[i]=Hash[i-1]*base+s[i]-'a'+1;
p[i]=p[i-1]*base;
}
for(ll i=0;i<=26;i++) t[i]=0;
for(ll i=len;i>=1;i--)
{
t[s[i]-'a']++;
if(t[s[i]-'a']&1) cnt[i]=cnt[i+1]+1;
else cnt[i]=cnt[i+1]-1;
}
for(ll i=0;i<=26;i++) t[i]=0;
t[s[1]-'a']++;
add(2ll,1ll);//The position that can let the odd number of letters <= a number
ll ans=0,last=1;
for(ll i=2;i<len;i++)//The length of AB
{
ll now=1;
ull tmp=Get_Hash(1,i);
ll Sta=i+1,End=2*i;
while(1)
{
if(Get_Hash(Sta,End)!=tmp||End>=len) break;
else Sta+=i,End+=i,now++;
}
// if(End>len) now--;
// if(now==0) now=1;
ll K=now-1;
if(K&1)
{
ans+=(1+(K-1)/2)*query(cnt[i*now+1]+1);
ans+=(K+1)/2*query(cnt[i*(now-1)+1]+1);
}
else
{
ans+=(K/2+1)*query(cnt[i*now+1]+1);
ans+=K/2*query(cnt[i*(now-1)+1]+1);
}
t[s[i]-'a']++;
if(t[s[i]-'a']&1) last++;
else last--;
add(last+1,1);
}
printf("%lld\n",ans);
}
return 0;
}
```