自动搬运

查看原文

来自洛谷，原作者为

	Fading AFO

搬运于2025-08-24 22:09:43，当前版本为作者最后更新于2019-05-04 20:35:31，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

有点思维含量的题啊。

虽然作为省选题太套路了。

很显然是$dp$

设$f[i][j]$表示长度为$i$,末位为字符$j$的方案数

很显然的转移式

但是$n$很大，怎么办呢？

发现是否可以转移的情况是固定的

可以考虑使用矩阵来判断是否可以转移。

如果字符串$ij$不为$s1$的子串，那么矩阵$X$中$X[i][j]=1$，否则$X[i][j]=0$。

$X$大小为$26$。

一次转移就是做一次矩阵乘法

$\begin{bmatrix}f[1] & f[2] & ... &f[26]\end{bmatrix}\times X$

为什么呢？

因为$f[i][j]+=f[i-1][k]\ (kj\ \text{不为s1的子串})$

也就是$f[i][j]+=f[i-1][k]\times X[k][j]$

就是

正好是矩阵的形式。

由于初始条件下$f[1]=f[2]=...=1$，所以我们只要求出$X^{n-1}$矩阵中所有数的和就好了。矩阵快速幂做到时间复杂度$O(26^3log_2n)$

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define ljc 1000000007
using namespace std;
long long n,m,pr,nf,x;
char s[1000001];
struct matrix{
    long long x[27][27];long long sz;	
    inline void clear(){
        for (int i=1;i<=26;i++){
            for (int j=1;j<=26;j++){
                x[i][j]=0;
            }
        }
    }
}a,one;
inline matrix mul(matrix a,matrix b){
    matrix c;
    c.clear();c.sz=a.sz;
    for (int i=1;i<=26;i++){
        for (int j=1;j<=26;j++){
            for (int k=1;k<=26;k++){
                c.x[i][j]=(c.x[i][j]%ljc+a.x[i][k]%ljc*b.x[k][j]%ljc)%ljc;
            }
        }
    }
    return c;
}
inline matrix fast_pow(matrix a,long long b){
    matrix t=one;
    while (b){
        if (b&1LL) t=mul(t,a);
        a=mul(a,a);b/=2LL;
    }
    return t;
}
inline void init_one(){
    one.sz=a.sz;
    for (int i=1;i<=26;i++){
        one.x[i][i]=1;
    }
}
int main(){
    scanf("%lld",&n);
    init_one();
    for (int i=1;i<=26;i++){
    	for (int j=1;j<=26;j++){
    		a.x[i][j]=1;
		}
	}
	scanf("%s",s+1);
	int len=strlen(s+1);
	for (int i=2;i<=len;i++){
		a.x[s[i-1]-'a'+1][s[i]-'a'+1]=0;
	}
    a=fast_pow(a,n-1);
    long long ans=0;
	for (int i=1;i<=26;i++){
    	for (int j=1;j<=26;j++){
    		ans=(ans+a.x[i][j])%ljc;
		}
	}
	cout<<ans;
}