P11404 [RMI 2020] 蝶变 / Brperm 题解

孩子们，调了一晚上结果数据锅了，不保证

i+2^k\le N

/ll

考虑字符串哈希的式子：

f(B)=\sum_{i=0}^{n-1}s_iB^i

可以把它当成生成函数来理解，那么

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)

了。

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

CPP

#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];
}

P11404 [RMI 2020] 蝶变 / Brperm 题解

文章操作

相关推荐

评论

P11404 [RMI 2020] 蝶变 / Brperm 题解