K好数

时间限制：1.0s   内存限制：256.0MB         锦囊1 使用动态规划。 锦囊2 用F[i][j]表示长为i，最后一位数字是j的K好数的个数，则F[i][j]=\sum F[i-1][k]，其中|j-k|!=1。 问题描述

如果一个自然数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。

代码如下：

import java.math.BigInteger;   import java.util.Scanner;   public class Main {       public static void main(String[] args) {           Scanner input=new Scanner(System.in);           int k=input.nextInt();     //k进制           int l=input.nextInt();     //l位           input.close();           int[] a=new int[l];           BigInteger t=new BigInteger("0");           for (int i = 0; i < Math.pow(k, l)-1; i++) {               a[0]++;               for (int j = 0; j < a.length-1; j++) {                   if(a[j]==k)                   {                       a[j]=0;                       a[j+1]++;                   }                   else{                       break;                   }               }                      if(a[0]!=0&&getK(a)==1)               {                   t=t.add(BigInteger.ONE);               }           }           System.out.println(t.mod(new BigInteger("1000000007")).toString());       }       public static int getK(int[] a){           for (int i = 0; i < a.length-1; i++) {               if(a[i]-a[i+1]==1||a[i]-a[i+1]==-1){                   return 0;               }           }           return 1;       }   }