P2106:Sam 数题解

这道题算是一道矩阵递推的模板题吧。不是很了解矩阵乘法或者是矩阵递推加速原理的可以移步这篇 Wiki：矩阵 – OI Wiki.我们很快可以推出一个 DP 方程出来，其中\(i\)代表位数，\(j\)代表第一位所填的数：

\[dp[i][j] = \sum^{j+2}_{k=j-2}dp[i-1][k]\]

然后，我们可以根据这个来推出一个递推矩阵：

\[\left[ \begin{array}{ccc}
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1\\
\end{array} \right]\]

初始矩阵是这样的：

\[\left[ \begin{array}{ccc}
0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\
\end{array} \right]\]

代码如下：

// P2106.cpp
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#define ll long long
using namespace std;
const ll mod = 1000000007;
struct matrix
{
    ll mat[10][10];
    matrix() { memset(mat, 0, sizeof(mat)); }
    matrix operator*(const matrix &ma) const
    {
        matrix empt;
        for (ll i = 0; i < 10; i++)
            for (ll j = 0; j < 10; j++)
                for (ll k = 0; k < 10; k++)
                    empt.mat[i][j] = (empt.mat[i][j] + mat[i][k] * ma.mat[k][j] % mod) % mod;
        return empt;
    }
    matrix operator^(const ll &num) const
    {
        ll tim = num;
        matrix pre = *(this);
        matrix tmp;
        for (ll i = 0; i < 10; i++)
            tmp.mat[i][i] = 1;
        while (tim)
        {
            if (tim & 1)
                tmp = tmp * pre;
            pre = pre * pre;
            tim >>= 1;
        }
        return tmp;
    }
} premat, Dmat;

int main()
{
    ll k;
    scanf("%lld", &k);
    if (k == 1)
    {
        printf("%lld", 10);
        return 0;
    }
    for (ll i = 1; i < 10; i++)
        premat.mat[0][i] = 1;
    for (ll i = 0; i < 10; i++)
        for (ll j = i - 2; j <= i + 2; j++)
        {
            if (j < 0)
                continue;
            if (j > 9)
                break;
            Dmat.mat[j][i] = 1;
        }
    Dmat = Dmat ^ (k - 1);
    premat = premat * Dmat;
    ll ans = 0;
    for (ll i = 0; i < 10; i++)
        ans += premat.mat[0][i], ans %= mod;
    printf("%lld", ans);
    return 0;
}