CF222E Decoding Genome

最近，对火星的一次秘密研究拉开帷幕，在这次探寻中，科学家们发现了火星上的DNA。

他们发现，火星DNA包含 (n) 个核苷酸，且由 (m) 种不同核苷酸构成（编号为 (1)~(m)）。

他们还发现出于某些特殊的原因，存在 (k) 对核苷酸，一对这样的核苷酸不会连续出现在火星DNA中。

例如存在一对这样的核苷酸 (1,2) ，则核苷酸2不能紧连着核苷酸1（即DNA中不会连续出现 1,2）；但是可以连续出现 2,1

科学家们想知道有多少种不同的火星DNA（如果两个DNA存在一个位置，使得两个DNA的该位置的核苷酸不同，则认为这两个DNA不同）。

直接dp好写，设(f_{i,j})表示确定了前(i)个长度的核苷酸，其中第(i)个的核苷酸的种类是(j)的方案数，于是有如下转移方程：

(mp_{i,j})表示(i)后面可不可以是(j)。

然后发现这个东西可以直接矩阵加速优化，最后的答案数组就是：

其中(f_{1,i}=1)。

Code

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