矩阵快速幂好题。

题意

给一个字符串 $s_1$，让你求长度为 $n$ 的字符串 $s_2$ 的方案数，须满足 $s_1$ 里相邻的两个字母不在 $s_2$ 中相邻。

样例解释：通过 $s_1$ 得出 $\texttt{a}$ 和 $\texttt{b}$ 不能相邻，也就是不能在 $s_2$ 中出现子串 $\texttt{ab}$。并且长度是 $2$ 所以除去 $\texttt{ab}$ 唯一的不可行方案所以答案是 $26 \times 26-1=675$。

思路

我们可以通过 $s_1$ 求出哪些字母是不能相邻的，如果 $x$ 和 $y$ 不能相邻，记作 $f_{x,y}=1$。则有 $f_{{s_1}_i,{s_1}_{i+1}}=1(i<|s_1|)$。

很容易想到正难则反求不合法方案的想法，但这个方法是行不通的。注意到求的是方案数，考虑动态规划。

令 $dp[i][j]$ 表示 $s_2$ 当前处理到第 $i$ 个字符并且第 $i$ 个字符为 $j$ 的方案数。可以很容易想到如果 $f_{j,k}=0$，那么 $dp[i-1][k]$ 是对 $dp[i][j]$ 有贡献的，那么可以列出转移方程：

$$dp[i][j]=\sum_{k=\texttt{a}}^{\texttt{z}} dp[i-1][k] \times (1-f_{j,k})$$

按照这个转移方程可以得到一个 $30$ 分的代码：

:::error[30pts RE]

#include<bits/stdc++.h>
using namespace std;
const int MOD=1000000000+7;
int n;
string s1;
char c[30][30];
int dp[100005][30];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>s1;
    for(int i=0;i<s1.size()-1;i++)
    {
        c[(int)s1[i]-'a'][(int)s1[i+1]-'a']=1;
    }
    for(int i='a';i<='z';i++)
    {
        dp[1][i-'a']=1;
    }
    for(int i=2;i<=n;i++)
    {
        for(int j='a';j<='z';j++)
        {
            for(int k='a';k<='z';k++)
            {
                dp[i][j-'a']+=dp[i-1][k-'a']*(1-c[j-'a'][k-'a']);
                dp[i][j-'a']%=MOD;
            }
        }
    }
    int ans=0;
    for(int i='a';i<='z';i++)
    {
        ans+=dp[n][i-'a'];
        ans%=MOD;
    }
    cout<<ans;
    return 0;
}

:::

---

注意到 $n\le 10^{15}$，考虑矩阵快速幂。

我们令初始矩阵 $A=[1,1,\dots,1]$。一行二十六列，表示 $\texttt{a} \sim \texttt{z}$ 二十六个字母。因为有一些字母组合是禁止出现的，那么我们设计出转移矩阵 $C$，$26 \times 26$ 的规模表示每一个字母组合，如果 $C_{i,j}=1$ 那么 $ij$ 的组合是合法的。所以最终答案就是：

$$A \times C^{n-1} \bmod 998244353$$

::::success[AC 代码]

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9 + 7;
int n;
string s1;
struct Mat
{
    int row, col;
    int m[30][30];
};
Mat dp, c;
Mat mul(Mat &a, Mat &b)
{
    Mat res;
    memset(res.m, 0, sizeof(res.m));
    res.row = a.row;
    res.col = b.col;
    for (int i = 1; i <= a.row; i++)
        for (int k = 1; k <= a.col; k++)
            for (int j = 1; j <= b.col; j++)
                res.m[i][j] = (res.m[i][j] + a.m[i][k] * b.m[k][j]) % MOD;
    return res;
}
Mat _pow(Mat a, int b)
{
    Mat res;
    memset(res.m, 0, sizeof(res.m));
    res.row = res.col = a.row;
    for (int i = 1; i <= a.row; i++)
        res.m[i][i] = 1;
    while (b)
    {
        if (b & 1)
            res = mul(res, a);
        a = mul(a, a);
        b = b >> 1;
    }
    return res;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>s1;
    dp.row=1;
    dp.col=26;
    for(int i=1;i<=26;i++)
    {
        dp.m[1][i]=1;
    }
    c.row=c.col=26;
    for(int i=1;i<=26;i++)
    {
        for(int j=1;j<=26;j++)
        {
            c.m[i][j]=1;
        }
    }
    for(int i=1;i<s1.size();i++)
    {
        c.m[s1[i-1]-'a'+1][s1[i]-'a'+1]=0;
    }
    c=_pow(c,n-1);
    dp=mul(dp,c);
    int ans=0;
    for(int i='a';i<='z';i++)
    {
        ans+=dp.m[1][i-'a'+1];
        ans%=MOD;
    }
    cout<<ans;
    return 0;
}

::::

题意

给一个字符串s1，让你求长度为n的字符串s2的方案数，须满足s1里相邻的两个字母不在s2中相邻。

从样例中我们也可以知道相邻的两个字母顺序要不变，所以不用再减其他顺序。

分析

第一步

看到方案数是要所有情况减掉不合法方案数，我们能想到用DP。

我们可以用dp[i][j]来表示s2当前处理到第i个字符并且第i个字符为j的方案数。

我们再用v[j][k]=0来表示j和k两个数字代表字符不能相邻，所以我们可以得到转移方程：

$$dp[i][j]=\sum^{26}_{k=1}dp[i-1][k]*v[j][k]$$

然后我们观察到30%的数据是n<=100000，我们就有了拿30分的心理准备......

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll P=1e9+7;
ll n,ans=0,dp[100010][30];char s[100010];
bool v[30][30];
int main()
{
	scanf("%lld",&n);
	scanf("%s",s+1);
	memset(v,1,sizeof v);
	for(ll i=0;i<=26;i++)dp[1][i]=1;
	for(ll i=1;i<strlen(s+1);i++)v[s[i]-'a'][s[i+1]-'a']=0;
	for(ll i=1;i<=n;i++)for(ll j=0;j<26;j++)for(ll k=0;k<26;k++)
	{
		if(v[k][j])dp[i][j]=(dp[i][j]+dp[i-1][k])%P;
	}
	for(ll i=0;i<=26;i++)ans=(ans+dp[n][i])%P;
	printf("%lld\n",ans);
	return 0;
}

第二步

为什么我们前面的方法只能有30分呢？原因很简单，n<=1e15，我们的二维DP根本存不下。

那题目就是要求我们用方法来优化朴素DP，那我们就要用上矩阵乘法来优化DP。

又因为n<=1e15，所以还要用到快速幂来辅助优化，防止超时。

第三步

方法思路有了，我们就考虑如何实现。

首先初始矩阵和最开始的DP一样，就是A={1,1...1,1}，一行，26个小写字母就是26列。

我们再来一个矩阵C来转移，用它来表示哪些相邻字母组合是合法的，如$C_{i,j}=1$代表i和j两个数字代表的字母是可以相邻的，所以是26*26的一个矩阵，又因为每种相邻的情况在长度为n的字符串s2中可以出现n-1次，所以答案为：

$A*C^{n-1}\%(1e9+7)$

第四步

然后就是AC的事了...

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll P=1e9+7;
ll n,ans=0;string s1;
struct Mat{ll row,col,m[30][30];}dp,c;
Mat mul(Mat &a,Mat &b)
{
    Mat res;
    memset(res.m,0,sizeof res.m);
    res.row=a.row;res.col=b.col;
    for(ll i=1;i<=a.row;i++)for(ll k=1;k<=a.col;k++)for(ll j=1;j<=b.col;j++)
        res.m[i][j]=(res.m[i][j]+a.m[i][k]*b.m[k][j])%P;
    return res;
}
Mat qpow(Mat a,ll b)
{
    Mat res;
    memset(res.m,0,sizeof res.m);
    res.row=res.col=a.row;
    for(ll i=1;i<=a.row;i++)res.m[i][i]=1;
    for(;b;b>>=1,a=mul(a,a))if(b&1)res=mul(res,a);
    return res;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>s1;
    dp.row=1;dp.col=26;
    for(ll i=1;i<=26;i++)dp.m[1][i]=1;
    c.row=c.col=26;
    for(ll i=1;i<=26;i++)for(ll j=1;j<=26;j++)c.m[i][j]=1;
    for(ll i=1;i<s1.size();i++)c.m[s1[i-1]-'a'+1][s1[i]-'a'+1]=0;
    c=qpow(c,n-1);dp=mul(dp,c);
    for(int i=1;i<=26;i++)ans=(ans+dp.m[1][i])%P;
    cout<<ans<<'\n';
    return 0;
}

还是内置函数好用

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 26
const int P=1e9+7;
struct nd
{
	int a[N][N];
	nd()
	{
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++)a[i][j]=(i==j);
	}
	void set(int num)
	{
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++)a[i][j]=num;
	}
	void friend operator*=(nd &n1,nd n2)
	{
		nd no;no.set(0);
		for(int i=0;i<N;i++)for(int j=0;j<N;j++)for(int k=0;k<N;k++)
			no.a[i][j]=(no.a[i][j]+n1.a[i][k]*n2.a[k][j])%P;
		n1=no;return;
	}
	void friend pow(nd &A,int m)
	{
		nd res;
		for(;m;m>>=1,A*=A)if(m&1)res*=A;
		A=res;
	}
};
signed main()
{
	int n;string s1;cin>>n>>s1;
	nd dp;dp.set(1);int l=s1.length();
	for(int i=1;i<l;i++)dp.a[s1[i-1]-'a'][s1[i]-'a']=0;
	pow(dp,n-1);int ans=0;
	for(int i=0;i<N;i++)for(int j=0;j<N;j++)
		ans=(ans+dp.a[i][j])%P;
	cout<<ans;return 0;
}

由于本蒟蒻很少使用矩阵乘法，赛事未能作出此题，但是骗了$35$分，哈哈哈哈。

题目大意

给定一个长度为$l$字符串$s1$，构造一个长度为$n$的字符串$s2$使得任意$i$($1\leq i\leq l-1$)，$s2$中任意一个满足$s2_j=s1_i$的$j$都有$s1_{j+1}\not =s1_{i+1}$，求满足条件的$s2$的数量。

思路（30分）

这其实是很标准的DP，定义$f_{i,j}$为$s2$中第$i$个字符为$j$的方案数，转移方程如下（$v_{i,j}$表示$i$和$j$是否可以相邻）

$$f_{i,j}=\sum^{25}_{k=0}{f_{i-1,k}\times v_{k,j}}$$

这个其实可以另外滚动优化，但是我没有去写。

30分代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10,P=1e9+7;
vector<int>G[26];
char s[N];
int n,f[N][26];
bool v[26][26];
int qpow(int a,int b)
{
	int res=1;
	for(;b;b>>=1,a=a*a%P)if(b&1)res=res*a%P;
	return res;
}
signed main()
{
	scanf("%lld%s",&n,s+1);
	int l=strlen(s+1);
	for(int i=1;i<l;i++)v[s[i]-'a'][s[i+1]-'a']=1;
	if(n<=100000)
	{
		for(int i=0;i<26;i++)for(int j=0;j<26;j++)if(!v[i][j])G[j].push_back(i);
		for(int i=0;i<26;i++)f[1][i]=1;
		for(int i=2;i<=n;i++)for(int j=0;j<26;j++)
		{
			for(int k:G[j])
			{
				f[i][j]=(f[i][j]+f[i-1][k])%P;
			}
		}
		int ans=0;
		for(int i=0;i<26;i++)ans=(ans+f[n][i])%P;
		printf("%lld\n",ans);
		return 0;
	}
	if(l<2){printf("%lld\n",qpow(26,n)%P);return 0;}
	
	puts("0");
	return 0;
}

特判之后其余情况输出$0$可以多拿$5$分。

正解思路

把刚才暴力的转移方程在观察一下。我们的$v$数组是用一个二维数组定义的，这是否有一点点像矩阵乘法 (别问我是如何想到的）？定义一个长宽均为$26$的矩阵$c$，其中$c_{i,j}$表示以$i$为开头，以$j$为结尾的字符串的合法方案数。转移时只需要将$c$乘上$v$即可，将这个操作重复执行$n-1$遍（用快速幂）即可。最终的答案即为$c$中每一位的和。

不会矩阵乘法的出门左转
不会快速幂的出门右转

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int P=1e9+7;
int n;
char s[110000];
struct node{int m[30][30];}f,c;
node operator *(node n1,node n2)//乘法 
{
	node res;
	memset(res.m,0,sizeof(res.m));
	for(int i=1;i<=26;i++)for(int k=1;k<=26;k++)for(int j=1;j<=26;j++)
		res.m[i][j]=(res.m[i][j]+n1.m[i][k]*n2.m[k][j])%P;
	return res;
}
node qpow(node a,int b)//矩阵快速幂 
{
	node res;
	memset(res.m,0,sizeof(res.m));
	for(int i=1;i<=26;i++)res.m[i][i]=1;//定义单位矩阵 
	for(;b;b>>=1,a=a*a)if(b&1)res=res*a;
	return res;
}
signed main()
{
	scanf("%lld%s",&n,s+1);
	for(int i=1;i<=26;i++)for(int j=1;j<=26;j++)c.m[i][j]=1;//初始化v 
	int l=strlen(s+1);
	for(int i=2;i<=l;i++)c.m[s[i-1]-'a'+1][s[i]-'a'+1]=0;
	c=qpow(c,n-1);//快速幂 
	int ans=0;
	for(int i=1;i<=26;i++)for(int j=1;j<=26;j++)ans=(ans+c.m[i][j])%P;//统计答案 
	printf("%lld\n",ans);
	return 0;//完结撒花 
}

后记

本蒟蒻打了一个$130$行的屎山，结果被$26^{10}$的常数复杂度卡死了，笑死。

题目大意非常好理解，现在来说说第一思路是什么以及怎么优化。

第一眼：DP 非常显而易见的思路，用一个数组dp[i][j]来表示s2中的第i位是j(a-z小写字母对应的j为1-26)有多少种方案。转移时对于每一个j，观察s1，若s1中不存在相邻的k与j就加上。

答案即为

$$(\sum_{j=1}^{26}dp[n][j])\%mod$$

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10,mod=1e9+7;
int p[N][27];
bool v[27][27];
signed main(){
	int n;char s[N];scanf("%lld%s",&n,s+1);
	memset(p,0,sizeof(p));
	int m=strlen(s+1);
	for(int i=1;i<=26;i++)p[1][i]=1;
	for(int i=1;i<m;i++)v[s[i]-96][s[i+1]-96]=1;
	for(int i=2;i<=n;i++){
		for(int j=1;j<=26;j++){
			for(int k=1;k<=26;k++)if(!v[k][j])p[i][j]=(p[i][j]+p[i-1][k])%mod;
		}
	}
	int ans=0;
	for(int i=1;i<=26;i++)ans=(ans+p[n][i])%mod;
	printf("%lld\n",ans);
	return 0;
}
//30分代码
//小提示：在主函数中加上:
//    if(n>100000)printf("0\n"),exit(0);
//可以多拿5分=)

第二眼：优化 很明显，此做法的时间复杂度为O($26^2$*n)，而n<=$10^{15}$，运行时间足以进行91场考试，故进行优化。

第三......眼？：矩阵快速幂 对于状态转移方程式：

$$dp[i][j]=\sum_{k=1}^{26}dp[i-1][k]*v[k][j]$$

观察到其计算方式与矩阵相同，又n<=$10^{15}$，故考虑矩阵乘法。

我们令初始矩阵 $dp=[1,1,1.....,1]$共26个，表示以二十六个小写字母为末尾有多少种字符串s2。因为s1中有一些字母组合是禁止出现的，那么可以设计出26*26大小的状态转移矩阵$c$，一行一列$(i,j)$表示i能不能与j相邻，能则为1，否则为0。故最后将此矩阵$c$与初始矩阵$dp$相乘$(n-1)$次，即得到最后的每个小写字母的结果$dp[1]-dp[26]$。

此过程可以用矩阵快速幂来加速，答案即为：

$$(\sum_{i=1}^{26}dp[i]*c^{n-1})\%mod$$

时间复杂度：O($26^2*log(n)$)。轻松AC (反正不是我)

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7,N=1e5+10;
int n;char s1[N];
struct mat{
    int r,c;
    int m[30][30];
}dp,c;//定义矩阵 
mat mul(mat &a,mat &b){//矩阵乘法 
    mat ans;memset(ans.m,0,sizeof(ans.m));
    ans.r=a.r;ans.c=b.c;
    for(int i=1;i<=a.r;i++)
        for(int k=1;k<=a.c;k++)
            for(int j=1;j<=b.c;j++)
                ans.m[i][j]=(ans.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
    return ans;
}
mat qpow(mat a,int b){//矩阵快速幂 
    mat ans;memset(ans.m,0,sizeof(ans.m));
    ans.r=ans.c=a.r;
    for(int i=1;i<=a.r;i++)ans.m[i][i]=1;
    for(;b;b/=2,a=mul(a,a))if(b&1)ans=mul(ans,a);
    return ans;
}
signed main(){
	scanf("%lld%s",&n,s1+1);
    dp.r=1;dp.c=26;
    for(int i=1;i<=26;i++)dp.m[1][i]=1;//设计初始矩阵 
    c.r=c.c=26;
    for(int i=1;i<=26;i++)for(int j=1;j<=26;j++)c.m[i][j]=1;
    for(int i=1;i<strlen(s1+1);i++)c.m[s1[i]-'a'+1][s1[i+1]-'a'+1]=0;//设计状态转移矩阵 
    c=qpow(c,n-1);
    dp=mul(dp,c);//计算dp*qpow(c,n-1) 
    int ans=0;
    for(int i='a';i<='z';i++)ans=(ans+dp.m[1][i-'a'+1])%mod;//计算答案 
    printf("%lld\n",ans);
    return 0;//完结撒花 
}

恭喜100分，点个赞再走吧！

首先,大多人都会想到 $dp$ ，这是显而易见的，经过滚动优化后的 $\color{red}{TLE}$ 代码:

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int p=1e9+7;
string s;
ll n,m,ans=0;
ll dp[26],cp[26];
bool G[26][26];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	memset(G,true,sizeof G);
	cin>>n>>s;
	m=s.size();
	for(int i=0;i<m;i++){
		if(i>0)G[s[i-1]-'a'][s[i]-'a']=false;
		if(i<m-1)G[s[i]-'a'][s[i+1]-'a']=false;
	}
	for(int i=0;i<26;i++)cp[i]=dp[i]=1;
	for(int i=2;i<=n;i++){
		for(int j=0;j<26;j++){
			dp[j]=0;
			for(int k=0;k<26;k++){
				if(G[k][j]){
					dp[j]=(cp[k]+dp[j])%p;
				}
			}
		}
		for(int j=0;j<26;j++)
			cp[j]=dp[j];
	}
	for(int i=0;i<26;i++)
		ans=(ans+dp[i])%p;
	cout<<ans;
    return 0;
}

因此我在某场比赛中这题获得了 $30$ 分的垃圾成绩 千万不能学我，要拿就拿100分 ;

看过这篇 $\LARGE{权威题解}$ 后，我恍然大悟。可以使用矩阵加速优化 $dp$ ！！！回顾之前的过程，要重复将每个字母加上所有符合情况的前面字母的方案数，转化一下，刚刚的过程就是用原来的 $dp$ 数组和原来表示两个字母是否相邻的表 $G$ 进行多次相乘，这不就可以用矩阵乘法吗！！！ 我太蠢了

温馨提示，不会矩阵乘法的 出门直走；

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int P=1e9+7;
int n,m;
string s;
struct node{//矩阵 
	int r,c,m[30][30];
	node operator *(const node&B){
		node C;
		memset(C.m,0,sizeof C.m);
		C.r=r;
		C.c=B.c;
		for(int i=1;i<=r;i++)
			for(int k=1;k<=c;k++)
				for(int j=1;j<=B.c;j++)
					C.m[i][j]=(C.m[i][j]+m[i][k] * B.m[k][j])%P;
		return C;
	}
}dp,c;
node qpow(node A,int b){//矩阵快速幂 
	node C;
	memset(C.m,0,sizeof C.m);
	C.r=C.c=A.r;
	for(int i=1;i<=A.r;i++)
		C.m[i][i]=1;
	for(;b;b>>=1,A=A*A)
		if(b&1)
			C=C*A;
	return C;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
	cin>>n>>s;
	m=s.size();
	//此乃初始化也 
	dp.r=1;
	c.r=c.c=dp.c=26;
	for(int i=1;i<=26;i++)
		dp.m[1][i]=1;
	for(int i=1;i<=26;i++)
		for(int j=1;j<=26;j++)
			c.m[i][j]=1;
	//将相邻字符进行标记 
	for(int i=1;i<m;i++)
		c.m[s[i-1]-'a'+1][s[i]-'a'+1]=0;
	//矩阵加速 
	c=qpow(c,n-1);
	dp=dp*c;
	//计算答案 
	int ans=0;
	for(char i='a';i<='z';i++)
		ans=(ans+dp.m[1][i-'a'+1])%P;
	cout<<ans;
	return 0;
}