给定一个字符串 ，假设其 border 集合为 ，则每次你可以在 后面接上一个长度为 的字符串，其中 。问在总长度 的情况下有多少种可能的本质不同的长度。
。
题解
Update：这个做法已经被 lyx 老师 Hack。
border 的贡献是若干端等差数列，不妨设其中一段为 ，其中 ，考虑其产生的贡献整理后可以理解为三种：
- 长度为 的贡献，可以选择 次；
- 长度为 的贡献，可以选择 次；
- 长度为 的贡献，可以选择 次。
考虑前两种贡献，就是朴素的同余最短路问题。考虑先计算出他们的 dis 数组，再转移上第三类贡献。
对于每一种等差数列分开处理，分模 的余数讨论，容易发现可以直接用单调队列维护下转移。
同余最短路跑 spfa 是线性的，可以直接用（。
时间复杂度 。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int T, n, fl, mod;
char s[N];
long long w, ans, t[N], dis[2][N];
vector<int> key;
struct atom {
int b, k, l;
};
vector<atom> res;
int nod;
struct node {
int pre, nxt, i;
long long x;
} e[N << 1];
inline void init() { nod = 0; }
struct myset {
int lim, hed, til;
inline void reset(int l) { hed = til = 0, lim = l; }
inline void pop_front() {
if (hed == til) hed = til = 0;
else {
e[e[til].pre].nxt = 0;
til = e[til].pre;
}
}
inline void pop_back() {
if (hed == til) hed = til = 0;
else {
e[e[hed].nxt].pre = 0;
hed = e[hed].nxt;
}
}
inline void push_back(int i, long long x) {
e[++nod].i = i, e[nod].x = x;
if (!hed) {
hed = til = nod;
e[nod].pre = e[nod].nxt = 0;
} else {
e[nod].nxt = hed, e[hed].pre = nod;
hed = nod;
}
}
inline void insert(int i, long long x) {
while (hed && e[hed].x > x) pop_back();
push_back(i, x);
while (e[til].i < i - lim) pop_front();
}
inline long long query() { return e[til].x; }
};
myset st[N];
namespace h {
const int b = 131131, p1 = 998244353, p2 = 1e9 + 7;
int f[N], g[N], pf[N], pg[N];
vector<int> vet;
inline int query(int l, int r, int *a, int *pa, int p) {
int res = (a[r] - (long long)a[l - 1] * pa[r - l + 1]) % p;
return res < 0 ? res + p : res;
}
void solve(int n) {
pf[0] = pg[0] = 1, vet.clear(), res.clear();
for (int i = 1; i <= n; i++) {
pf[i] = (long long)pf[i - 1] * b % p1;
pg[i] = (long long)pg[i - 1] * b % p2;
f[i] = ((long long)f[i - 1] * b + s[i] - 'a') % p1;
g[i] = ((long long)g[i - 1] * b + s[i] - 'a') % p2;
}
for (int i = n - 1; i >= 1; i--)
if (query(1, i, f, pf, p1) == query(n - i + 1, n, f, pf, p1) && query(1, i, g, pg, p2) == query(n - i + 1, n, g, pg, p2)) vet.push_back(n - i);
vet.push_back(n);
int first = vet[0], delta = 0, cnt = 0;
for (int i = 1; i < vet.size(); i++)
if (!delta) {
delta = vet[i] - vet[i - 1], cnt = 1;
} else {
if (vet[i] - vet[i - 1] == delta) ++cnt;
else {
res.push_back((atom){first, delta, cnt});
first = vet[i], delta = 0, cnt = 0;
}
}
res.push_back((atom){first, delta, cnt});
}
} // namespace h
void spfa(vector<int> &key, long long *dis) {
static int l, r, q[N << 3];
static bool inq[N];
mod = *max_element(key.begin(), key.end());
memset(dis, 63, mod << 3);
q[l = r = 1] = dis[0] = 0;
while (l <= r) {
int u = q[l++];
inq[u] = 0;
for (int w : key) {
int c = (u + w) / mod;
int v = u + w - c * mod;
if (dis[u] + c < dis[v]) {
dis[v] = dis[u] + c;
if (!inq[v]) inq[v] = 1, q[++r] = v;
}
}
}
}
void trans(long long *f, long long *g, const atom &it) {
if (!it.l) {
for (int i = 0; i < mod; i++) {
g[i] = min(f[i], f[(i - it.b + mod) % mod]);
}
return;
}
memset(t, 63, mod << 3), init();
for (int i = 0; i < it.k; i++) st[i].reset(it.l);
for (int i = -mod; i < mod; i++) {
auto &st = ::st[(i + mod) % it.k];
st.insert((i + mod) / it.k, i < 0 ? f[i + mod] + 1 : f[i]);
if (i >= 0) t[i] = st.query();
}
for (int i = 0; i < mod; i++) {
g[i] = min(f[i], i < it.b ? t[i - it.b + mod] + 1 : t[i - it.b]);
}
}
int main() {
for (cin >> T; T--; ans = 0, key.clear()) {
scanf("%d%lld%s", &n, &w, s + 1);
if (w < n) {
puts("0");
continue;
}
h::solve(n);
for (auto x : res) {
key.push_back(x.b);
if (x.l) key.push_back(x.b + x.k * x.l);
}
spfa(key, dis[fl]);
for (auto x : res) {
trans(dis[fl], dis[fl ^ 1], x);
fl ^= 1;
}
for (int i = 0; i < mod; i++)
if (dis[fl][i] != 4557430888798830399) {
ans += max(0ll, (w - n - i) / mod + 1 - dis[fl][i]);
}
printf("%lld\n", ans);
}
}