自动搬运

查看原文

来自洛谷，原作者为

	_sys goodbye, OI

搬运于2025-08-24 21:57:07，当前版本为作者最后更新于2019-10-24 22:17:23，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

本题需要我们了解一个关于 border 的性质。

定理：

一个字符串的所有 border 排序后，至少存在一种将序列划分为若干子序列的方案，使得所有子序列均为等差数列，且子序列的个数为 $O(\log|s|)$。

证明：

一个显然的结论：$s[0..k - 1]$ 为 $s$ 的 border $\rightleftharpoons$ $|s| - k$ 为 $s$ 的周期。

另一个显然的结论：若 $p$ , $q$ 为 $s$ 的周期，则 $\gcd(p, q)$ 也为 $s$ 的周期。

以上两个结论可以套定义得到。

考虑两个 $|s|$ 的 border : $A$，$B$，其中 $B$ 为最长的 border ( $s$ 本身除外)，$|A| \geq \frac{|s|}{2}$ 。

令 $p=|s| - |A|$，$q=|s| - |B|$。

若这样的两个 $border$ 存在，则 $p$ , $q$ , $\gcd(p,q)$ 均为 $s$ 的周期，所以 $s[0..|s| - \gcd(p, q)]$ 为 $s$ 的 border，又因为 $B$ 为最长的 border，所以 $\gcd(p,q)$ = $q$。

因此 $q|p$ 。又因为 $k \times q$ 也是 $|s|$ 的周期，所以 $s[0..|s| - k \times q - 1]$ 都是 $s$ 的 border。因此所有长度大于等于字符串一半的 border 构成一个等差数列。

考虑两个 $|s|$ 的 border : $A$，$B$ ($|A| < |B|$)。

则 $A$ 也为 $B$ 的 border。

所以我们可以把 border 分成两个集合：第一个集合的 border 长度大于等于 $\frac{|s|}{2}$，第二部分为其他。第一部分构成了一个等差数列，第二部分所有字符串为其中最长的字符串的 border，可以递归处理，至多 $\log |s|$ 层。定理得证。

得到了这个定理，我们回到题目。

我们可以将题意转化为：$\sum_{i=1}^{cnt}a_ix_i$ 在 $[0,w-n]$ 中能取到的值的个数，其中 $cnt$ 为 $|s|$ 的周期个数，$a$ 为周期长度。

由此我们想到了同余最短路。

注意，$\min\{a_i\}*cnt$ 是 $O(n^2)$ 的，构造方法为 $aaa\ldots aabaaa\ldots aa$ 。其中 $b$ 处在字符串较中间的位置。

但是由于 border 拥有特殊的性质，我们可以进行优化。

我们把不同的等差数列分开处理。

首先，对于一个等差数列 $x,x + d,x + 2d, \ldots x + l\times d$，我们在$\mod x$ 下跑同余最短路。其中对于 $0 \leq y < x$ 的 $y$ 向 $(y + d) \mod x$ 连边，会形成 $\gcd(x, d)$ 个环。每个环可以分开处理。

但我们此时发现，把等差数列分开处理的坏处就是此时没有源点，如果用环上任何一点去优化另外一点，需要 $\Omega(n^2)$ ，这样复杂度很劣。

但是我们又可以发现，环中 $dis$ 最小的一点是绝不会被更新的，且相邻两点之间权值相同，都为 $d$。这两条性质，可以让我们从 $dis$ 最小点出发，使用单调队列计算。

我们在单调队列里放入离现在处理点距离小于等于 $l$ 的点，以 $dis_i - pos_i * d$ 作为比较方式（因为环上 $a$ 点到 $b$ 点的代价是 $-pos_a * d + pos_b * d$)。这样我们就能处理环上的转移。

还有一个问题，是 $dis$ 数组在不同模数之间的转换。若原先的模数为 $las$，现在的模数为 $now$，很显然 $dis_i$ 可以更新 $dis'_{dis_i \mod now}$。但 $dis_i$ 的含义是 $dis_i + k * las$ ($k \geq 0$) 可以被访问。所以我们在$\mod now$ 意义下再用 $x$ 更新$(x + las)\mod now$ 跑一边同余最短路即可。

注意到这个过程类似于单个等差数列的处理过程。同样可以把环分开处理。不过由于没有 $l$ 的限制，不需要用到单调队列。

时间复杂度：$O(Tn\log n)$ 。

代码：

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

const int Maxn = 500005;
int now, ct, fail[Maxn], Q[2 * Maxn], seq[Maxn], border[Maxn], pos[Maxn];
long long f[Maxn], res[Maxn], sta[Maxn], ans, w;
string str;
void get_fail(void)
{
	int siz = str.size();
	fail[0] = fail[1] = 0;
	for (int i = 1; i < siz; i++)
	{
		int tmp = fail[i];
		while (tmp && str[tmp] != str[i]) tmp = fail[tmp];
		fail[i + 1] = str[tmp] == str[i] ? tmp + 1 : 0;
	}
	int now = fail[siz];
	while (now)
	{
		border[++ct] = siz - now;
		now = fail[now];
	}
	border[++ct] = siz;
}
void change_mod(int mod)
{
	int cnt = __gcd(mod, now);
	for (int i = 0; i < now; i++)
		res[i] = f[i];
	for (int i = 0; i < mod; i++)
		f[i] = 0x3f3f3f3f3f3f3f3fLL;
	for (int i = 0, tmp; i < now; i++)
		tmp = res[i] % mod, f[tmp] = min(f[tmp], res[i]);
	for (int i = 0; i < cnt; i++)
	{
		int top = 0;
		Q[++top] = i;
		int tmp = (i + now) % mod;
		while (tmp != Q[1])
			Q[++top] = tmp, tmp = (tmp + now) % mod;
		for (int j = top + 1; j <= 2 * top; j++)
			Q[j] = Q[j - top];
		top <<= 1;
		for (int j = 2; j <= top; j++)
			f[Q[j]] = min(f[Q[j]], f[Q[j - 1]] + now);
	}
	now = mod;
}
void work(int first, int diff, int siz)
{
	int cnt = __gcd(diff, first);
	change_mod(first);
	if (diff < 0) return ;
	for (int i = 0; i < cnt; i++)
	{
		int top = 0;
		Q[++top] = i;
		int tmp = (i + diff) % first;
		while (tmp != Q[1])
			Q[++top] = tmp, tmp = (tmp + diff) % first;
		int mini_pos = 1;
		for (int j = 1; j <= top; j++)
			if (f[Q[j]] < f[Q[mini_pos]]) mini_pos = j;
		int tmp_cnt = 0;
		for (int j = mini_pos; j <= top; j++)
			seq[++tmp_cnt] = Q[j];
		for (int j = 1; j < mini_pos; j++)
			seq[++tmp_cnt] = Q[j];
		int head = 1, tail = 1;
		pos[1] = 1, sta[1] = f[seq[1]] - diff;
		for (int j = 2; j <= top; j++)
		{
			while (head <= tail && pos[head] + siz < j) head++;
			if (head <= tail) f[seq[j]] = min(f[seq[j]], sta[head] + j * (long long) diff + first);
			while (head <= tail && sta[tail] >= f[seq[j]] - j * (long long) diff) tail--;
			sta[++tail] = f[seq[j]] - j * (long long) diff, pos[tail] = j;
		}
	}
}
int T, n;
int main()
{
	scanf("%d", &T);
	while (T--)
	{
		ans = ct = 0;
		scanf("%d%lld", &n, &w), w -= n;
		memset(f, 0x3f, sizeof(long long[n]));
		f[0] = 0;
		now = n;
		cin >> str;
		get_fail();
		for (int i = 1, j = 1; i <= ct; i = j)
		{
			while (border[j + 1] - border[j] == border[i + 1] - border[i]) j++;
			work(border[i], border[i + 1] - border[i], j - i - 1);
		}
		for (int i = 0; i < now; i++)
			if (f[i] <= w) ans += (w - f[i]) / now + 1;
		printf("%lld\n", ans);
	}
	return 0;
}