「牛客挑战赛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;
}