泪雨 Namid[A]me

宝宝泪雨。只需要哈希和 manacher。

发现

f

值上界在

O(\log n)

，下文直接用

\log n

代替

k

。

考察一个子串

[l,r]

的

f

值，发现直接哈希判断回文就做到

O(\log n)

了。

一个对答案有贡献的串首先本身得是回文串，所以考虑 manacher，统计

g_{i,j}

表示回文中心为

i

的回文串中

f

值为

j

的串的个数，发现我擦这不是我们 P12977 泪雨 Namid[A]me 吗，具体而言，普通 manacher 求出

d_i

表示中心为

i

的最长回文半径时，

d

的转移中会从当前回文段的对称位置

l+r-i

转移

d_i \gets \min(r-i,d_{l+r-i})

，我们同理用这个维护

g_{i,j}

，转移

g_{i,j}\gets g_{l+r-i,j}

，然后

d_i

变长的时候在

g_i

对应位置加一，但是发现无法去除

d_{l+r-i}

在

r-i

段以外的贡献，于是我们暴力收缩到

r-i

去除贡献即可，能证明复杂度依然是

O(n)

，但是要求多个回文中心取到同一个右端点时，回文段左端点取最大的。具体证明可见泪雨题解区。统计完

g

后，

f

值为

k

的串个数即为

\sum g_{*,k}

。时间复杂度

O(n\log n)

。

CPP

#include <bits/stdc++.h>
#define LL long long
#define ull unsigned long long
#define uint unsigned int
using namespace std;
const int N = 2e5 + 10;
const int M = 40;
int n, m, lim = 30;
int res[N][M], D[N]; LL Ans[M];

const ull MOD = 1e9 + 123;
const ull P = 233;
char S[N], T[N]; ull hsh1[N], hsh2[N], pw[N];
ull get1(int l, int r) { 
    return (hsh1[r] + MOD - hsh1[l - 1] * pw[r - l + 1] % MOD) % MOD; 
}
ull get2(int l, int r) { 
    return (hsh2[l] + MOD - hsh2[r + 1] * pw[r - l + 1] % MOD) % MOD; 
}
bool palind(int l, int r) { return get1(l, r) == get2(l, r); }
int _calc(int l, int r) {
	int cnt = 0; for (; l < r && palind(l, r); ++ cnt, r = (l + r) / 2);
	return cnt + (l == r);
}
int calc(int l, int r) { return (T[l] == '#' ? 0 : _calc(l / 2, r / 2)); }

int main() {
	freopen(".in", "r", stdin); freopen(".out", "w", stdout);
	ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
	cin >> n >> m >> (S + 1); pw[0] = 1;
	for (int i = 1; i <= n; i ++) pw[i] = pw[i - 1] * P % MOD;
	for (int i = 1; i <= n; i ++) hsh1[i] = (hsh1[i - 1] * P + S[i]) % MOD;
	for (int i = n; i >= 1; i --) hsh2[i] = (hsh2[i + 1] * P + S[i]) % MOD;
	T[1] = '#'; for (int i = 1; i <= n; i ++) T[i * 2] = S[i], T[i * 2 + 1] = '#';
	int tot = n * 2 + 1;
	for (int i = 1, l = 1, r = 0; i <= tot; i ++) {
		if (i <= r) {
			int p = l + r - i; D[i] = min(D[p], r - i);
			while (i - D[i] - 1 >= 1 && i + D[i] + 1 <= tot 
                   && T[i - D[i] - 1] == T[i + D[i] + 1])
				++ D[i];
			for (int j = 0; j <= lim; j ++) res[i][j] = res[l + r - i][j];
			for (int j = D[p]; j > r - i; j --) res[i][calc(p - j, p + j)] --;
			for (int j = r - i + 1; j <= D[i]; j ++) res[i][calc(i - j, i + j)] ++;
		} else {
			res[i][1] = (T[i] != '#');
			while (i - D[i] - 1 >= 1 && i + D[i] + 1 <= tot 
					&& T[i - D[i] - 1] == T[i + D[i] + 1])
				++ D[i], res[i][calc(i - D[i], i + D[i])] ++;
		}
		if (i + D[i] >= r) r = i + D[i], l = i - D[i];
		for (int j = 0; j <= lim; j ++) Ans[j] += res[i][j];
	}
	for (int i = 1; i <= m; i ++) cout << Ans[i] << " \n"[i == m];
	return 0;
}

文章操作

相关推荐

评论

泪雨 Namid[A]me