【2024NOIP模拟赛73】字符串 做题记录

给定一个长 $n$ 的字符串 $s$ 和两个权值数组 $a,b$。

定义 $g_i=\sum\limits_{j=1}^i [s_{[1,i-j+1]}=s_{[j,i]}]\times a_j\times b_i$。

定义 $ans_i=\sum\limits_{j=1}^i g_j$，你需要求出 $ans_{[1,n]}$。

强制在线，$s_i=(s'_i+ans_{i-1})\oplus 31$。

$1\le n\le 10^6$，$1\le a_i,b_i\le 10^3$。

讲一下等差数列做法。

只需要每次算出 $i$ 的所有 border 的左端点的 $a$ 的和即可。

找等差数列是简单的，对于一个长度为 $n$ 的串 $S$，假设 $S_{[1,n]}$ 也是其 border。

设 $f_i$ 为 $S_{[1,i]}$ 的 border，$d=n-f_n$，则 $S_{[1,n]},S_{[1+d,n]},S_{[1+2d,n]}\dots S_{[1+ld,n]}$ 都是 $S$ 的 border，其中 $l=\lfloor\frac{n}{d}\rfloor-1$。这样就能找到 $S_{[1,n]}$ 所在的等差数列，递归寻找 $S_{[n-f_{n-ld}+1,n]}$ 所在的等差数列即可，这样每次长度至少减半。

赛时太困了，并没有想到怎么维护等差数列的和。实际上，对于 $l\not=0$ 的情况，有 $f_{n}=f_{n-d}+d$，即 border 可以同时往里缩一个周期，那么不妨开一个哈希表 $g_{j,d}$ 维护 $j$，公差为 $d$ 的在 $[1,i]$ 中的等差数列的和，即 $a_{j}+a_{j+d}+a_{j+2d}+\dots$。这样每次找到一个等差数列的时候前面 $l-1$ 项一定都算好了，只需要另外开一个长度哈希表判断第 $l$ 项有没有算即可。

时间复杂度 $O(n\log n)$，哈希表用 map 会变成 $O(n\log ^2 n)$。

代码如下：

#include <iostream>
#include <cstdio>
#include <map>

using namespace std;

template<typename T>
inline void read(T &x)
{
	x=0;
	T w=1;
	char c=getchar();
	while(c<'0'||c>'9') w=(c=='-'?-w:w),c=getchar();
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	x*=w;
}

typedef long long ll;

const int S=1000005;

int n,t,a[S],b[S],s[S];
int f[S];
map<int,int> sm[S],le[S];

int main()
{
	freopen("str.in","r",stdin);
	freopen("str.out","w",stdout);
	read(n),read(t);
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<=n;i++) read(b[i]);
	for(int i=1;i<=n;i++) read(s[i]);
	f[1]=0;
	ll ans=b[1]*a[1];
	printf("%lld\n",ans);
	for(int i=2,j=0;i<=n;i++)
	{
		s[i]=(s[i]+t*ans)&31;
		
		while(j!=0&&s[j+1]!=s[i]) j=f[j];
		if(s[j+1]==s[i]) j++;
		f[i]=j;
		
		int len=i,sma=0;
		while(len>0)
		{
			int k=f[len];
			int d=len-k,l=len/d-1;
			int p=i-len+1; // p,p+d,p+2d,...,p+ld
			// printf(">> %d %d: %d %d %d\n",i,len,p,d,l);
			if(le[p].count(d)==0) sm[p][d]=a[p];
			if(le[p][d]<l)
			{
				sm[p][d]+=a[p+l*d];
				le[p][d]=l;
			}				
			sma+=sm[p][d];
			len=f[len-l*d];
		}
		ans+=1ll*sma*b[i];
		printf("%lld\n",ans);
	}
	return 0;
}