蓝桥杯K好数(dp)

问题描述
如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。
求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有K好数为11、13、20、22、30、31、33
共7个。由于这个数目很大，请你输出它对1000000007取模后的值。

输入格式
输入包含两个正整数，K和L。

输出格式
输出一个整数，表示答案对1000000007取模后的值。
样例输入
4 2
样例输出
7
数据规模与约定
对于30%的数据，KL <= 106；

对于50%的数据，K <= 16， L <= 10；

对于100%的数据，1 <= K,L <= 100。
思路：用动态规划；若求 K=4 进制 L=1 位则 有 0,1,2,3 。共4种,当L>=2时 第一位不能为0
所以 计算第一位时 把 a[1][0]=0;就是说可以 20 不可 02 可以 200,300
a[i][j]表示 以 j（0,1,2,3.。.。K-1）数 为第i位上的数字 存储的是 这种情况下的K好数
\j 0 1 2 3.。。。K-1
i
1 0 1 1 1.。。。 1
2 2 2 1 2.。。。
3 5 4 3 6.。。。
。
。
。
L

#include <stdio.h>
int abs(int a)
{if(a>=0)return a;
  else return -a;
}
int main()
{long int k,l,m,i,j;
long int sum=0;
long int a[105][105]={0}; 
scanf("%ld%ld",&k,&l);
if(l>=2)
{  for(i=0;i<k;i++)// 当L==1时 所有进制内的数都可以 所以每个数都是 1个K好数 
    a[1][i]=1;
    a[1][0]=0;//第一位不能为0 

    for(i=2;i<=l;i++)
      for(j=0;j<k;j++)
       for(m=0;m<k;m++)
       {if(abs(j-m)!=1)
          a[i][j]+=a[i-1][m];//a[i][j]表示第i位填 j 数字a[i-1][m]表示j可与高位那些 m 数结合 
          if(a[i][j]>1000000007)a[i][j]%=1000000007;//a[i-1][m]表示 以 m 数做低位时的 K好数数目 
       }      //a[i][j]表示 以 j 数做低位时的 K好数数目 

    }
    for(i=0;i<k;i++)
       {sum+=a[l][i];
       if(sum>1000000007)sum%=1000000007;
       }

    printf("%ld\n",sum);

return 0;
}