10
9
260649
1928206
26

考虑这样一个图g，节点为0、1、2、3、4、5、6、7、8、9。若|i-j|<=m,g[i][j]=1;当n大于1时，矩阵的n-1次幂中的每个元素都是对应n个节点的一条路径，每个元素的值是这个路径的走法个数。（考虑矩阵的乘法的性质。）这道题就迎刃而解了。注意n==1时，要特殊处理，以及数是没有前导零的。

#include<stdio.h>
#include<string.h>
const int mod=2008512;
int abs(int a){return a>0?a:-a;}
struct Matrix
{
       int a[10][10];
       Matrix operator *(Matrix &l)
       {
              Matrix temp;
              memset(temp.a,0,sizeof(temp.a));
              for(int i=0;i<10;i++)
                  for(int j=0;j<10;j++)
                     for(int k=0;k<10;k++)
                          temp.a[i][j]=(temp.a[i][j]+(int)(((a[i][k]%mod)*(long long)(l.a[j][k]))%mod))%mod;
              return temp;
       }
}M;
Matrix pow(Matrix &t,int k)
{
       Matrix temp;
       if(k==1) return t;
       temp=t*t;
       if(k&1) return pow(temp,k/2)*t;
       return pow(temp,k/2);
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
          if(n==1)
          {
                  puts("10");
                  continue;
          }
          for(int i=0;i<10;i++)
              for(int j=0;j<10;j++)
                   if(abs(i-j)<=m) M.a[i][j]=1;
                   else M.a[i][j]=0;
          Matrix temp=pow(M,n-1);
          int ans=0;
          for(int i=1;i<10;i++)
              for(int j=0;j<10;j++)
                  ans=(ans+temp.a[i][j])%mod;
          printf("%d\n",ans);
    }
}