"蔚来杯"2022牛客暑期多校训练营9 G Magic Spells

原题链接

一开始manacher + 单哈希wa，样例通过率97%，应该是卡了一手int_64自然溢出
换成manacher + 双哈希过了

#include<bits/stdc++.h>
using namespace std;

#define fr first
#define se second
#define et0 exit(0);
#define rep(i, a, b) for(int i = (int)(a); i <= (int)(b); i ++)
#define rrep(i, a, b) for(int i = (int)(a); i >= (int)(b); i --)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef unsigned long long ULL;
typedef pair<ULL, ULL> PUU;


const int INF = 0X3f3f3f3f, N = 700000 + 10, MOD1 = 1e9 + 7, MOD2 = 998244353, P = 131;
const double eps = 1e-7, pi = acos(-1);

int K = 0, n, len, cnt, hw[N];

ULL p1[N], p2[N], h1[N], h2[N];

char s[N], str[N];

map<PUU, int> st;

PUU query(int l, int r) {
	PUU Hash;
	Hash.fr = (h1[r] - h1[l - 1] * p1[r - l + 1] % MOD1 + MOD1) % MOD1;
	Hash.se = (h2[r] - h2[l - 1] * p2[r - l + 1] % MOD2 + MOD2) % MOD2;
	return Hash;
}

void Init() {
	p1[0] = p2[0] = 1;
	rep (i, 1, N - 1) p1[i] = p1[i - 1] * P % MOD1;
	rep (i, 1, N - 1) p2[i] = p2[i - 1] * P % MOD2;
}

void manacher() {
	K++;
	PUU hash_u;
	cnt = 2;
	str[0] = '&', str[1] = '*';
	rep (i, 0, len - 1) str[cnt++] = s[i], str[cnt++] = '*';
	str[cnt++] = '$';
	
	rep (i, 1, cnt - 1) h1[i] = (h1[i - 1] * P % MOD1 + str[i]) % MOD1;
	rep (i, 1, cnt - 1) h2[i] = (h2[i - 1] * P % MOD2 + str[i]) % MOD2;
	
	int mid = 0, maxright = 0;
	
	rep (i, 1, cnt - 2) {
		if (i < maxright) hw[i] = min(hw[mid * 2 - i], maxright - i + 1);
		else hw[i] = 1;
		hash_u = query(i, i + hw[i] - 1);
		if (str[i + hw[i] - 1] != '*' && st[hash_u] == K - 1) {
			st[hash_u]++;
		}
		while (str[i - hw[i]] == str[i + hw[i]]) {
			hw[i]++;
			hash_u = query(i, i + hw[i] - 1);
			if (str[i + hw[i] - 1] != '*' && st[hash_u] == K - 1) {
				st[hash_u]++;
			}
		}
		if (maxright < i + hw[i] - 1) maxright = i + hw[i] - 1, mid = i;
	}
}

void work() {
	Init();
	
	cin >> n;
	rep (i, 1, n) {
		scanf("%s", s);
		len = strlen(s);
		manacher();
	}
	
	int res = 0;
	for(auto cur : st) if (cur.se == n) res++;
	cout << res << endl;
}

signed main() {
	int test = 1;
	//	cin >> test;
	
	while (test--) {
		work();
	}
	
	return 0;
}