自动搬运

查看原文

来自洛谷，原作者为

	ueettttuj 我爱学习

搬运于2025-08-24 21:34:03，当前版本为作者最后更新于2019-07-23 19:43:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

感觉其他大佬没多解释矩阵的构造，本蒟蒻来详细解释一下

首先此题是一道数位$DP$题，可以快速的推出方程

令$f(i,j)$ 表示第$i$位数为$j$时的方案数

因为相邻两数之差不超过$2$，故在第$i+1$位时可以选取的数为$j-2$~$j+2$

故可以推出方程$f(i+1,j)=\sum\limits_{m=j-2}^{j+2}{f(i,m)}$

方程展开为$f(i+1,j)=f(i,j-2)+f(i,j-1)+f(i,j)+f(i,j+1)+f(i,j+2)$

于是我们便可以$O(n)$推出答案

但是由于数据范围为$1 ≤ k ≤ 10^{18}$ $,$ 所以要用矩阵快速幂优化

根据递推式 $,$ 我们可以推出矩阵

1 1 1 0 0 0 0 0 0 0            f[i,0]         f[i,0]+f[i,1]+f[i,2]                         f[i+1,0]  
1 1 1 1 0 0 0 0 0 0            f[i,1]         f[i,0]+f[i,1]+f[i,2]+f[i,3]                  f[i+1,1]  
1 1 1 1 1 0 0 0 0 0            f[i,2]         f[i,0]+f[i,1]+f[i,2]+f[i,3]+f[i,4]           f[i+1,2]  
0 1 1 1 1 1 0 0 0 0            f[i,3]         f[i,1]+f[i,2]+f[i,3]+f[i,4]+f[i,5]           f[i+1,3]  
0 0 1 1 1 1 1 0 0 0      x     f[i,4]    =    f[i,2]+f[i,3]+f[i,4]+f[i,5]+f[i,6]     =     f[i+1,4]  
0 0 0 1 1 1 1 1 0 0            f[i,5]         f[i,3]+f[i,4]+f[i,5]+f[i,6]+f[i,7]           f[i+1,5]  
0 0 0 0 1 1 1 1 1 0            f[i,6]         f[i,4]+f[i,5]+f[i,6]+f[i,7]+f[i,8]           f[i+1,6]  
0 0 0 0 0 1 1 1 1 1            f[i,7]         f[i,5]+f[i,6]+f[i,7]+f[i,8]+f[i,9]           f[i+1,7]  
0 0 0 0 0 0 1 1 1 1            f[i,8]         f[i,6]+f[i,7]+f[i,8]+f[i,9]                  f[i+1,8]  
0 0 0 0 0 0 0 1 1 1            f[i,9]         f[i,7]+f[i,8]+f[i,9]                         f[i+1,9]  

令

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    

为$A$矩阵;

令

f[1,0]
f[1,1]
f[1,2]
f[1,3]
f[1,4]
f[1,5]
f[1,6]
f[1,7]
f[1,8]
f[1,9]

为$B$矩阵;

所以我们只用将$A$矩阵乘 $k-1$ 遍 , 再将 $A*B$ 就可以得出在第$k$位取 $0$ ~ $9$ 的方案数，再将其累加即可得到答案

注意点：

1. $B$ 中 $f(1,0)=0\ ,$ 因为要防止出现前导$0$

2. 当$k=1$ 时 ， 需特判输出$10$

下面放代码

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
long long k;
struct node{
    long long m[11][11];
};
node res,ans,realans;
node mul(node aa,node bb){
    node tmp;
    memset(tmp.m,0,sizeof(tmp.m));
    for(long long i=0;i<=9;i++){
        for(long long j=0;j<=9;j++){
            for(long long k=0;k<=9;k++){
                tmp.m[i][j]=(tmp.m[i][j]+aa.m[i][k]*bb.m[k][j])%mod;
            }
        }
    }
    return tmp;
}
int main(){
    scanf("%lld",&k);
    if(k==1){
        printf("10\n");
        return 0;
    }
    for(long long i=0;i<=9;i++){
        ans.m[i][i]=1;
    }
    for(long long i=0;i<=9;i++){
        for(long long j=max(0ll,i-2);j<=min(i+2,9ll);j++){
            res.m[i][j]=1;
        }
    }
    k--;
    while(k){
        if(k%2) ans=mul(ans,res);
        res=mul(res,res);
        k/=2;
    }
    long long anss=0;
    for(long long i=1;i<=9;i++)
        realans.m[i][0]=1;
    for(long long i=0;i<=9;i++){
    	for(long long j=0;j<=0;j++){
    		for(long long k=0;k<=9;k++){
    			anss=(anss+ans.m[i][k]*realans.m[k][j])%mod;
            }
        }
    }
    printf("%lld\n",anss);
    return 0;
}

神犇轻喷