[TJOI2019] 甲苯先生的字符串题解

laoshan-plus / 2024-10-15 / 原文

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;
}