前言

今天zty带来的是P1117 [NOI2016] 优秀的拆分，大家给个赞呗，zty放寒假的更新呢是会多起来的大概一天三四个吧,zty最近在冲榜大家多加支持
先 赞 后 看 养 成 习 惯

先 赞 后 看 养 成 习 惯
演示用编译器及其标准
Dev C++ 6.7.5 Red panda C++14

正文

P1117 [NOI2016] 优秀的拆分

题目描述

如果一个字符串可以被拆分为 $\text{AABB}$ 的形式，其中 $\text{A}$ 和 $\text{B}$ 是任意非空字符串，则我们称该字符串的这种拆分是优秀的。
例如，对于字符串 $ \texttt{aabaabaa} $ ，如果令 $\text{A}=\text{aab}$，$\text{B}=\text{a}$，我们就找到了这个字符串拆分成 $\text{AABB}$ 的一种方式。

一个字符串可能没有优秀的拆分，也可能存在不止一种优秀的拆分。
比如我们令 $\text{A}=\text{a}$，$\text{B}=\text{baa}$，也可以用 $\text{AABB}$ 表示出上述字符串；但是，字符串 $\text{abaabaa}$ 就没有优秀的拆分。

现在给出一个长度为 $n$ 的字符串 $S$，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。这里的子串是指字符串中连续的一段。

以下事项需要注意：

1. 出现在不同位置的相同子串，我们认为是不同的子串，它们的优秀拆分均会被记入答案。
2. 在一个拆分中，允许出现 $\text{A}=\text{B}$。例如 $\text{cccc}$ 存在拆分 $\text{A}=\text{B}=\text{c}$。
3. 字符串本身也是它的一个子串。

输入格式

每个输入文件包含多组数据。

输入文件的第一行只有一个整数 $T$，表示数据的组数。

接下来 $T$ 行，每行包含一个仅由英文小写字母构成的字符串 $S$，意义如题所述。

输出格式

输出 $T$ 行，每行包含一个整数，表示字符串 $S$ 所有子串的所有拆分中，总共有多少个是优秀的拆分。

输入输出样例 #1

输入 #1

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

输出 #1

3
5
4
7

说明/提示

样例解释

我们用 $S[i,j]$ 表示字符串 $S$ 第 $i$ 个字符到第 $j$ 个字符的子串（从 $1$ 开始计数）。

第一组数据中，共有三个子串存在优秀的拆分：
$S[1,4]=\text{aabb}$，优秀的拆分为 $\text{A}=\text{a}$，$\text{B}=\text{b}$；
$S[3,6]=\text{bbbb}$，优秀的拆分为 $\text{A}=\text{b}$，$\text{B}=\text{b}$；
$S[1,6]=\text{aabbbb}$，优秀的拆分为 $\text{A}=\text{a}$，$\text{B}=\text{bb}$。
而剩下的子串不存在优秀的拆分，所以第一组数据的答案是 $3$。

第二组数据中，有两类，总共四个子串存在优秀的拆分：
对于子串 $S[1,4]=S[2,5]=S[3,6]=\text{cccc}$，它们优秀的拆分相同，均为 $\text{A}=\text{c}$，$\text{B}=\text{c}$，但由于这些子串位置不同，因此要计算三次；
对于子串 $S[1,6]=\text{cccccc}$，它优秀的拆分有两种：$\text{A}=\text{c}$，$\text{B}=\text{cc}$ 和 $\text{A}=\text{cc}$，$\text{B}=\text{c}$，它们是相同子串的不同拆分，也都要计入答案。
所以第二组数据的答案是 $3+2=5$。

第三组数据中，$S[1,8]$ 和 $S[4,11]$ 各有两种优秀的拆分，其中 $S[1,8]$ 是问题描述中的例子，所以答案是 $2+2=4$。

第四组数据中，$S[1,4]$，$S[6,11]$，$S[7,12]$，$S[2,11]$，$S[1,8]$ 各有一种优秀的拆分，$S[3,14]$ 有两种优秀的拆分，所以答案是 $5+2=7$。

数据范围

对于全部的测试点，保证 $1\le T\le 10$。以下对数据的限制均是对于单组输入数据而言的，也就是说同一个测试点下的 $T$ 组数据均满足限制条件。

我们假定 $n$ 为字符串 $S$ 的长度，每个测试点的详细数据范围见下表：

测试点编号	$n\le$	特殊性质
$1\sim 2$	$300$	$S$ 中所有字符相同
$3\sim 4$	$2000$	$S$ 中所有字符相同
$5\sim 6$	$10$
$7\sim 8$	$20$
$9\sim 10$	$30$
$11\sim 12$	$50$
$13\sim 14$	$100$
$15$	$200$
$16$	$300$
$17$	$500$
$18$	$1000$
$19$	$2000$
$20$	$30000$

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define LL long long
const int CN = 3e4 + 10;
const int P = 191011109;
const int B = 39;
int pB[CN];
int read() {
	int s = 0, ne = 1;
	char c = getchar();
	for (; c < '0' || c > '9'; c = getchar()) if (c == '-') ne = -1;
	for (; c >= '0' && c <= '9'; c = getchar()) s = (s << 1) + (s << 3) + c - '0';
	return s * ne;
}
int add(int x, int y) {
	return x + y >= P ? x + y - P : x + y;
}
int ha[CN];
int get(int l, int r) {
	return add(ha[r], P - (1ll * ha[l - 1] * pB[r - l + 1] % P));
}
int T, n;
char ch[CN];
int LCP(int l1, int r1, int l2, int r2) {
	if (ch[l1] != ch[l2]) return 0;
	int l = 1, r = min(r1 - l1 + 1, r2 - l2 + 1);
	while (l < r) {
		int mid = (l + r + 1) >> 1;
		if (get(l1, l1 + mid - 1) == get(l2, l2 + mid - 1)) l = mid;
		else r = mid - 1;
	}
	return l;
}
int LCS(int l1, int r1, int l2, int r2) {
	if (ch[r1] != ch[r2]) return 0;
	int l = 1, r = min(r1 - l1 + 1, r2 - l2 + 1);
	while (l < r) {
		int mid = (l + r + 1) >> 1;
		if (get(r1 - mid + 1, r1) == get(r2 - mid + 1, r2)) l = mid;
		else r = mid - 1;
	}
	return l;
}
bool le(int l1, int r1, int l2, int r2) {
	if (l1 == l2) return r1 < r2;
	int l = LCP(l1, r1, l2, r2);
	if (l1 + l > r1 || l2 + l > r2) return r1 - l1 < r2 - l2;
	return ch[l1 + l] < ch[l2 + l];
}
class PAIR {
	public:
		int l, r, p;
		bool operator < (const PAIR &o) const {
			return l ^ o.l ? l < o.l : (r ^ o.r ? p < o.p : r < o.r);
		}
		bool operator == (const PAIR &o) const {
			return l == o.l && r == o.r;
		}
} ;
PAIR mp(int a, int b, int c) {
	PAIR o;
	o.l = a, o.r = b, o.p = c;
	return o;
}
vector<PAIR> runs;
int stk[CN], ed[CN], top;
void lyndon() {
	top = 0;
	for (int i = n; i; i--) {
		stk[++top] = i;
		while (top > 1 && le(i, stk[top], stk[top] + 1, stk[top - 1])) top--;
		ed[i] = stk[top];
	}
	for (int i = 1; i <= n; i++) {
		int j = ed[i], lcs = LCS(1, i - 1, 1, j), lcp = LCP(i, n, j + 1, n), l, r;
		l = i - lcs, r = j + lcp;
		if ((r - l + 1) / (j - i + 1) > 1) runs.pb(mp(l, r, j - i + 1));
	}
}
int f[CN], g[CN];
int main() {
	// freopen("_in.in", "r", stdin);
	n = 3e4, pB[0] = 1;
	for (int i = 1; i <= n; i++) pB[i] = 1ll * pB[i - 1] * B % P;
	T = read();
	while (T--) {
		scanf("%s", ch + 1), n = strlen(ch + 1);
		for (int i = 1; i <= n; i++) ha[i] = add(1ll * B * ha[i - 1] % P, ch[i] - 'a');
		runs.clear();
		lyndon();
		for (int i = 1; i <= n; i++) ch[i] = 'a' + 'z' - ch[i];
		lyndon();
		sort(runs.begin(), runs.end());
		int len = unique(runs.begin(), runs.end()) - runs.begin();
		for (int i = 0; i < len; i++) {
			int l = runs[i].l, r = runs[i].r, p = runs[i].p;
			for (int L = p + p; L <= r - l + 1; L += p + p) {
				g[l]++, g[r - L + 2]--;
				f[l + L - 1]++, f[r + 1]--;
			}
		}
		for (int i = 1; i <= n; i++) f[i] += f[i - 1], g[i] += g[i - 1];
		LL ans = 0;
		for (int i = 1; i < n; i++) ans += 1ll * f[i] * g[i + 1];
		printf("%lld\n", ans);
		for (int i = 0; i <= n + 1; i++) f[i] = g[i] = 0;
	}
	return 0;
}

后记

作者：zty郑桐羽呀
联系方式：（不挂了，有事私信）
兄弟们给个赞呗
先 赞 后 看 养 成 习 惯