Rockdu's Blog

题目描述

小Z最近发现了一种非常有趣的数，他将这种数称之为 Sam 数。Sam 数具有以下特征：相邻两位的数字之差不超过 2。小Z还将 Sam 数按位数进行了分类，他将一个 k 位 Sam 数称之为 k 阶 Sam 数。但不幸的是小Z发现他数不清第 k 阶的 Sam 数一共有多少个，这个时候机智的他想到了向你求助。

输入输出格式

第一行为一个整数 k，含义见题面。

一行一个整数 ans，表示 k 阶的 Sam 数的个数。

由于第 k 阶 Sam 数非常多，你只需要输出 ans mod 1000000007。

输入输出样例

4

867

说明

【数据规模和约定】

对于 30%的数据，1 ≤ k ≤ 10^6。

对于 60%的数据，1 ≤ k ≤ 10^12。

对于 100%的数据，1 ≤ k ≤ 10^18。

这道题很容易可以想到数位dp：dp[i][j]表示dp到第i个， 以j为末尾的情况有多少种。但是1e18的范围心态很爆炸！

以前看到10^18的数据范围想都不想直接数学方法。但是自从上次hdu5434企图用轮廓线找规律被集训队大佬嘲讽了一波之后，蒟蒻就永远记住了矩阵快速幂这种操作（如果不会矩阵快速幂可以先百度矩阵快速幂求斐波那契数列第n项）。大概意思是如果dp的每一次转移都相同，那么我们可以用矩阵快速幂无压力dp（例如hdu5434）。这道题也是类似，我们可以发现每一次dp[i - 1][j] 到 dp[i][j]的状态转移都是相同的。这样我们只要通过转移构造转移矩阵，然后对转移矩阵进行快速幂就可以了。下面是代码：

#include<cstdio>
#include<cstring>
#include<cmath>
#define LL long long
using namespace std;
LL n, ans;
const int p = 1000000007;
struct Matrix {
    LL DT[130][130];
    int n, m;
    Matrix(int nn, int nm) {
        memset(DT, 0, sizeof(DT));
        n = nn, m = nm;
    }
    void Std(int x) {
        n = m = x;
        for(register int i = 0; i < x; ++i)
            DT[i][i] = 1;
    }
    Matrix operator *(const Matrix &a) {
        Matrix ans(n, a.m);
        for(register int i = 0; i < n; ++i)
            for(register int j = 0; j < a.m; ++j)
                for(register int k = 0; k < m; ++k)
                    (ans.DT[i][j] += (DT[i][k] * a.DT[k][j]) % p) %= p;
        return ans;
    }
}trans(10, 10), st(1, 10);
Matrix fpow(Matrix a, LL b) {
    Matrix ans(a.n, a.n);
    ans.Std(a.n);
    while(b) {
        if(b & 1) ans = ans * a;
        a = a * a, b >>= 1;
    }
    return ans;
}
int main() {
    scanf("%lld", &n);
    if(n == 1) {
        printf("10");
        return 0;
    }
    for(register int i = 1; i < 10; ++i)
        st.DT[0][i] = 1;
    for(register int i = 0; i < 10; ++i)
        for(register int j = 0; j < 10; ++j)
            if(abs(i - j) <= 2) ++trans.DT[i][j];
    trans = st * fpow(trans, n - 1);
    for(register int i = 0; i < 10; ++i) 
        (ans += trans.DT[0][i] % p) %= p;
    printf("%lld", ans);
    return 0;
}