如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大，请你输出它对1000000007取模后的值。
输入格式输入包含两个正整数，K和L。
输出格式 输出一个整数，表示答案对1000000007取模后的值。 数据规模与约定对于30%的数据，KL <= 106；
对于50%的数据，K <= 16， L <= 10；
对于100%的数据，1 <= K,L <= 100。
本题可想成一个K行，L列的矩阵，一个自然数就是每列选一个数。即后一列中的某个数和前一列的数不相邻的总组合数。可用动态规划处理。注意的是最高位不能为0。即矩阵的[0][0]需特殊处理下。
#include<stdio.h> #include<math.h> int main(void) { int K,L,i,j,q; long long num=0; scanf("%d",&K); //K进制 scanf("%d",&L); //L位 long long a[L][K]; for(i=0;i<L;i++) { for(j=0;j<K;j++) { a[i][j]=0; } } for(i=1;i<K;i++) { a[0][i]=1; } for(i=1;i<L;i++) { for(j=0;j<K;j++) { for(q=0;q<K;q++) { if(abs(j-q)!=1) { a[i][j]+=a[i-1][q]; a[i][j]%=1000000007; } } } } for(i=0;i<K;i++) { num+=a[L-1][i]; num%=1000000007; } printf("%I64d",num); return 0; }
