問題描述
如果一個自然數(shù)N的K進(jìn)制表示中任意的相鄰的兩位都不是相鄰的數(shù)字霍弹，那么我們就說這個數(shù)是K好數(shù)。求L位K進(jìn)制數(shù)中K好數(shù)的數(shù)目娃弓。例如K = 4典格，L = 2的時候，所有K好數(shù)為11台丛、13耍缴、20、22挽霉、30防嗡、31、33 共7個侠坎。由于這個數(shù)目很大蚁趁，請你輸出它對1000000007取模后的值。
輸入格式
輸入包含兩個正整數(shù)实胸，K和L荣德。
輸出格式
輸出一個整數(shù)闷煤，表示答案對1000000007取模后的值。
樣例輸入
4 2
樣例輸出
7
數(shù)據(jù)規(guī)模與約定
對于30%的數(shù)據(jù)涮瞻，KL <= 106鲤拿；
對于50%的數(shù)據(jù)，K <= 16署咽， L <= 10近顷；
對于100%的數(shù)據(jù)，1 <= K,L <= 100宁否。
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
int main() {
int k, l;
long long dp[105][105];
int i, j, x;
memset(dp, 0, sizeof(dp));
scanf("%d%d", &k, &l);
for (i = 0; i < k; i++) {
dp[1][i] = 1;
}
for (i = 2; i <= l; i++) { // i代表數(shù)字有幾位
for (j = 0; j < k; j++) { // j代表數(shù)字j放在首位情況
for(x = 0; x < k; x++) {
if (x != j + 1 && x != j - 1) { // 不能有相鄰的數(shù)字
dp[i][j] += dp[i-1][x];
dp[i][j] %= mod;
}
}
}
}
long long ans = 0;
for (int i = 1; i < k; i++) { // 0 不能作為一個數(shù)的開頭
ans += dp[l][i];
ans %= mod;
}
printf("%lld\n", ans);
return 0;
}
