自动搬运

查看原文

来自洛谷，原作者为

	fairytale 不要忘记我们的歌

搬运于2025-08-24 23:07:03，当前版本为作者最后更新于2025-02-02 14:16:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

孩子们，调了一晚上结果数据锅了，不保证 $i+2^k\le N$ /ll

考虑字符串哈希的式子：

可以把它当成生成函数来理解，那么 $f(B^2)$ 相当于把字符串中每个字符后面插了一个空格。

然后考虑题目中的变换，现在要求区间 $[l,l+2^k)$ 变换后的哈希值，记为 $f(x)$，假设 $[l,l+2^{k-1}),[l+2^{k-1},l+2^k)$ 是变换好的，它们变换后的哈希值分别记为 $f_0(x),f_1(x)$，那么可以得出 $f(B)=f_0(B^2)+Bf_1(B^2)$。

暴力做就是 $\mathcal O(n\log^2n)$ 的。

然后没有人规定过字符串哈希的 $B$ 必须是固定的对吧。所以我们在 $[i,i+2^k)$ 使用 $B^{2^{19-k}}$ 当底数就可以做到 $\mathcal O(n\log n)$ 了。

随便写写就最优解了？？？

#define maxn 501000
const int P=1000000007;
int pw[20];
int f[20][maxn];
int g[maxn];
bitset<maxn>ok[20];
int n;
void init(int N, const char s[]) {
	n=N;
	vector<int>p(26);
	rep(i,0,25)p[i]=i;
	shuffle(p.begin(),p.end(),rnd);
	rep(j,0,19)ok[j].set();
	pw[19]=20071230;
	per(i,18,0)pw[i]=1ll*pw[i+1]*pw[i+1]%P;
	rep(i,0,N-1)f[0][i]=p[s[i]-'a'];
	rep(j,1,19) {
		int B=pw[j];
		for(int i=0; i+(1<<j)-1<=N-1; ++i) {
			f[j][i]=f[j-1][i]+1ll*f[j-1][i+(1<<(j-1))]*B%P;
			if(f[j][i]>=P)f[j][i]-=P;
		}
		g[N-1]=p[s[N-1]-'a'];
		per(i,N-2,0)g[i]=(1ll*g[i+1]*B%P+p[s[i]-'a'])%P;
		for(int i=0; i+(1<<j)-1<=N-1; ++i) {
			ok[j][i]=(f[j][i]==(g[i]-1ll*g[i+(1<<j)]*pw[0]%P+P)%P);
		}
	}
}
int query(int i, int k) {
	if(i+(1<<k)>n)return 0;
	return ok[k][i];
}