P2106 Sam数

· · 题解

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

首先此题是一道数位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;
}

神犇轻喷