「牛客挑战赛31 E | Nowcoder 880E」密涅瓦的谜题

好久没更了 = =

现在看到什么题都感觉一脸不可做，水平太低了

题意

给出仅包含小写字母的长度为 $n$ 的字符串 $s$

每次取出 $s$ 的一个子串 $t_i$（可以为空），执行 $m$ 次，顺次拼接成一个大字符串 $t=t_1 t_2\dots t_m$，求可以得到多少种本质不同的 $t$

$q$ 次询问，每次给出一个 $m$

$n,q\le 10^5, m\le 10^{10}$

做法

考虑 $t$ 的一种唯一分解的方式（不会算重），每次取 $t$ 最长的是 $s$ 子串的前缀，作为这次选取的子串。由于更短的前缀也必然是一个子串，这种做法显然存在解且唯一的

一组 $t_1 t_2 \dots t_m$ 合法当且仅当 $\forall 1\le i<m$ 有 $t_i$ 加上 $t_{i+1}$ 的第一个字符后不是 $s$ 的子串

令 $f_{i,j}$ 表示考虑了最后 $i$ 次选取的子串，当前的第一个字符是 $j$ 的方案数，只要保证新选取的子串加上 $j$ 后不是 $s$ 的子串即可转移

特殊的，$j$ 可以为空字符，即第 $m-i+1$ 次选取的是空串

$$f_{i,j}=\sum_k A_{k,j} \times f_{i-1,k}$$

其中 $A$ 是系数矩阵，可以在 SAM 上 dp 得到

令 $\sigma$ 表示字符集大小，复杂度 $\mathcal O(n \sigma)$

答案为

$$
\begin{bmatrix}
0 & \cdots & 0 & 1
\end{bmatrix}
A^m
\begin{bmatrix}
1 & \cdots & 1 & 1
\end{bmatrix}
^{\rm T}
$$

考虑对 $m$ 分块

答案转化为

$$
\begin{bmatrix}
0 & \cdots & 0 & 1
\end{bmatrix}
A^{\left\lfloor \frac{m}{S} \right\rfloor \times S}
\times
A^{m \bmod S}
\begin{bmatrix}
1 & \cdots & 1 & 1
\end{bmatrix}
^{\rm T}
$$

左侧只有 $\mathcal O(\frac{m}{S})$ 种取值，右侧只有 $\mathcal O(S)$ 种取值。

在 $S=\sqrt m$ 时取得总复杂度最小值 $\mathcal O(\sqrt m \sigma^2 + (n+q) \sigma)$

代码

#include<cstdio>
#include<algorithm>
#include<cctype>
#include<string.h>
#include<cmath>
#include<vector>

using namespace std;
#define ll long long

inline char read() {
	static const int IN_LEN = 1000000;
	static char buf[IN_LEN], *s, *t;
	return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
	static bool iosig;
	static char c;
	for (iosig=false, c=read(); !isdigit(c); c=read()) {
		if (c == '-') iosig=true;
		if (c == -1) return;
	}
	for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
	if (iosig) x=-x;
}
const int OUT_LEN = 10000000;
char obuf[OUT_LEN], *ooh=obuf;
inline void print(char c) {
	if (ooh==obuf+OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh=obuf;
	*ooh++=c;
}
template<class T>
inline void print(T x) {
	static int buf[30], cnt;
	if (x==0) print('0');
	else {
		if (x<0) print('-'), x=-x;
		for (cnt=0; x; x/=10) buf[++cnt]=x%10+48;
		while(cnt) print((char)buf[cnt--]);
	}
}
inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }

const int N = 100005, C = 26, K = C+1, P = 1000000007;
ll m;
int n, q, last, cnt, b[N], a[N<<1], fa[N<<1], len[N<<1], l[N][K], r[N][K], ch[N<<1][C], f[N<<1][K];
char s[N];
struct matrix{
	int a[K][K];
	inline matrix operator *(const matrix &r)const{
		matrix ans;
		memset(ans.a, 0, sizeof a);
		for(int i=0; i<K; ++i) for(int k=0; k<K; ++k) for(int j=0; j<K; ++j)
			ans.a[i][j]=(ans.a[i][j]+(ll)a[i][k]*r.a[k][j])%P;
		return ans;
	}
} A, B;
void extend(int c){
	int p=last, np=++cnt;
	last=cnt, len[np]=len[p]+1;
	while(p && !ch[p][c]) ch[p][c]=np, p=fa[p];
	if(!p) fa[np]=1;
	else{
		int q=ch[p][c];
		if(len[q]==len[p]+1) fa[np]=q;
		else{
			int nq=++cnt;
			len[nq]=len[p]+1, memcpy(ch[nq], ch[q], C<<2);
			fa[nq]=fa[q], fa[q]=fa[np]=nq;
			while(ch[p][c]==q) ch[p][c]=nq, p=fa[p];
		}
	}
}
inline matrix Pow(matrix x, int y){
	matrix ans;
	memset(ans.a, 0, sizeof ans);
	for(int i=0; i<K; ++i) ans.a[i][i]=1;
	for(; y; y>>=1, x=x*x) if(y&1) ans=ans*x;
	return ans;
}
int main() {
	last=cnt=1;
	while(islower(s[++n]=read())) extend(s[n]-'a');
	--n;
	for(int i=1; i<=cnt; ++i) ++b[len[i]];
	for(int i=1; i<=n; ++i) b[i]+=b[i-1];
	for(int i=1; i<=cnt; ++i) a[b[len[i]]--]=i;
	for(int i=cnt; i; --i){
		int u=a[i];
		f[u][C]=1;
		for(int x=0; x<C; ++x) if(ch[u][x]) for(int j=0; j<=C; ++j)
			(f[u][j]+=f[ch[u][x]][j])%=P;
		else ++f[u][x];
	}
	A.a[C][C]=1;
	for(int i=0; i<C; ++i) if(ch[1][i]) for(int j=0; j<=C; ++j)
		A.a[j][i]=f[ch[1][i]][j];
	B=Pow(A, 100000);
	l[0][C]=1;
	for(int i=0; i<=C; ++i) r[0][i]=1;
	for(int i=1; i<=100000; ++i)
		for(int j=0; j<K; ++j) for(int k=0; k<K; ++k)
			l[i][j]=(l[i][j]+(ll)l[i-1][k]*B.a[k][j])%P,
			r[i][j]=(r[i][j]+(ll)r[i-1][k]*A.a[j][k])%P;
	read(q);
	while(q--){
		read(m);
		int x=m/100000, y=m%100000, ans=0;
		for(int i=0; i<K; ++i) ans=(ans+(ll)l[x][i]*r[y][i])%P;
		print(ans), print('\n');
	}
	return flush(), 0;
}