题解 CF222E 【Decoding Genome】
eee_hoho
2020-11-16 20:34:59
直接dp好写，设$f_{i,j}$表示确定了前$i$个长度的核苷酸，其中第$i$个的核苷酸的种类是$j$的方案数，于是有如下转移方程：
$$f_{i,k}=\sum_{j=1}^mf_{i-1,j}[mp_{j,k}=1]$$
$mp_{i,j}$表示$i$后面可不可以是$j$。
然后发现这个东西可以直接矩阵加速优化，最后的答案数组就是：
$$f_{1}\times mp^{n-1}$$
其中$f_{1,i}=1$。
**Code**
``` cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
const int N = 3000;
const int p = 1e9 + 7;
using namespace std;
struct Matrix
{
int a[61][61];
}a,f,s,c;
long long n;
int m,k,id[N + 5],ans;
char ch[3];
Matrix operator *(Matrix a,Matrix b)
{
for (int i = 0;i <= 60;i++)
for (int j = 0;j <= 60;j++)
c.a[i][j] = 0;
for (int i = 0;i <= 60;i++)
for (int j = 0;j <= 60;j++)
for (int k = 0;k <= 60;k++)
c.a[i][j] += 1ll * a.a[i][k] * b.a[k][j] % p,c.a[i][j] %= p;
return c;
}
int main()
{
scanf("%lld%d%d",&n,&m,&k);
for (int i = 1;i <= 26;i++)
{
id['a' + i - 1] = i;
id['A' + i - 1] = i + 26;
}
for (int i = 1;i <= m;i++)
for (int j = 1;j <= m;j++)
a.a[i][j] = 1;
for (int i = 1;i <= k;i++)
{
scanf("%s",ch + 1);
a.a[id[ch[1]]][id[ch[2]]] = 0;
}
for (int i = 1;i <= m;i++)
f.a[0][i] = 1;
n--;
for (int i = 0;i <= 60;i++)
s.a[i][i] = 1;
while (n)
{
if (n & 1)
s = s * a;
a = a * a;
n >>= 1;
}
f = f * s;
for (int i = 1;i <= m;i++)
ans = (ans + f.a[0][i]) % p;
cout<<ans<<endl;
return 0;
}
```