T2 [TJOI2019] 甲苯先生的字符串
矩阵乘法优化 DP，所以一般来说这种 DP 都不怎么难。
30pts 的 DP 是裸的：设 \(f_{i,j}\) 为前 \(i\) 位、最后一位是 \(j\) 的方案数，则有转移方程：
\[f_{i,j}=\sum_{k=0}^{25}f_{i-1,k}\land k\ne j \]想要矩阵优化，我们想到构造答案矩阵：
\[\mathit{ans}=\underbrace{\begin{bmatrix}1&1&1&\cdots&1\end{bmatrix}}_{\text{26个1}} \]构造转移矩阵：
\[\mathit{base}=\begin{bmatrix}1&1&1&\cdots&1\\1&1&1&\cdots&1\\1&1&1&\cdots&1\\\vdots&\vdots&\vdots&\ddots&\vdots\\1&1&1&\cdots&1\end{bmatrix} \]然后把不能相邻的位置点成 \(0\)。最终答案就是 \(\mathit{ans}\times\mathit{base}^{n-1}\) 之后 \(\sum\mathit{ans}_{0,i}\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MAXN=1e5+5,MOD=1e9+7;
int n;
string s1;
void add(int&x,int y){
x=x+y>=MOD?x+y-MOD:x+y;
}
struct Matrix{
int mx[26][26];
Matrix(int x=0){
memset(mx,0,sizeof(mx));
if(x)for(int i=0;i<26;++i)mx[i][i]=x;
}
int*operator[](const int&x){
return mx[x];
}
Matrix operator*(const Matrix&b)const{
Matrix res;
for(int i=0;i<26;++i)
for(int k=0;k<26;++k)
for(int j=0;j<26;++j)
add(res[i][j],mx[i][k]*b.mx[k][j]%MOD);
return res;
}
}ans,base;
void print(Matrix x){
for(int i=0;i<26;++i,cout<<'\n')
for(int j=0;j<26;++j)
cout<<x[i][j]<<' ';
}
Matrix power(Matrix a,int b){
Matrix res=Matrix(1);
for(;b;a=a*a,b>>=1)if(b&1)res=res*a;
return res;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>s1;
for(int i=0;i<26;++i){
ans[0][i]=1;
for(int j=0;j<26;++j)base[i][j]=1;
}
for(int i=1;s1[i];++i)base[s1[i-1]-'a'][s1[i]-'a']=0;
ans=ans*power(base,n-1);
int res=0;
for(int i=0;i<26;++i)add(res,ans[0][i]);
cout<<res<<'\n';
return 0;
}