2022.9.8 11:39 solution
很简单的一道矩阵加速 dp，我们发现转移式非常好推，令 \(f_{o,i}\) 表示第 \(i\) 对核苷酸为 \(o\) 的方案数，那么不难得到：
\[f_{o,i}=\sum_{p=1}^{m} f_{o,i-1}\times [(p,o) \notin K]
\]
其中 \(K\) 表示题目中描述的不能存在的相邻核苷酸组成的集合。
关注到 \(n\le10^{15}\)，显然想到矩阵快速幂，我们假设此时 \(m=3\)，\(K=\{(1,2),(2,3),(3,1)\}\) 那么矩阵怎么建呢？
\[\begin{vmatrix}1&1&0\\ 0&1&1\\ 1&0&1\end{vmatrix}\times \begin{vmatrix}f_{1,i-1}\\ f_{2,i-1}\\ f_{3,i-1}\end{vmatrix}=\begin{vmatrix}f_{1,i}\\ f_{2,i}\\ f_{3,i}\end{vmatrix}
\]
然后用相似的方法构建矩阵即可，复杂度 \(O(m^3\log n)\)。
\(Code\)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll n;
int m;
struct Matrix{
int a[52][52];
Matrix(){memset(a,0,sizeof(a));}
void build(){
int k;cin>>k;
for(int i=1;i<=k;i++){
char u,v;
cin>>u>>v;
if('a'<=u&&u<='z')u-='a';
else u=u-'A'+26;
if('a'<=v&&v<='z')v-='a';
else v=v-'A'+26;
a[v][u]=1;
}
for(int i=0;i<m;i++)
for(int j=0;j<m;j++)
a[i][j]^=1;
return;
}
Matrix operator *(const Matrix &w)const{
Matrix ans;
for(int i=0;i<m;i++)
for(int j=0;j<m;j++)
for(int k=0;k<m;k++)
ans.a[i][j]=(ans.a[i][j]+1ll*a[i][k]*w.a[k][j]%mod)%mod;
return ans;
}
}a,ans;
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
a.build();for(int i=0;i<m;i++)ans.a[i][0]=1;
for(n--;n;n>>=1,a=a*a)if(n&1)ans=a*ans;
int ANS=0;
for(int i=0;i<m;i++)ANS=(ANS+ans.a[i][0])%mod;
cout<<ANS;
return 0;
}