第一次解出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%的数据，K^L <= 10⁶；

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

对于100%的数据，1 <= K,L <= 100。

 

用dp解题

#include
       
        #include
        
         using namespace std;#define M 1000000007//save[i][j]表示i位以j开头的K好数的个数 long long save[102][102] = {
     0};int K, L;void init() {    memset(save, 0, sizeof(save));} //dp 不考虑首位不为零的情况 long long dp(int l) {    for(int i = 0; i < K; i++) {        if(l < 2){
     break;}        if(l == 2) {            for(int j = 0; j < K; j++) {                if(j == 0 || j == K - 1) save[2][j] = K - 1;                else save[2][j] = K - 2;                }            return 0;        }        // 计算 save[i][j]         for(int k = 0; k < K; k++) {            if(k != i -1 && k != i + 1 && k >=0 && k < K) {  //除去相邻越界                 if(save[l - 1][k] != 0)                    save[l][i] += save[l - 1][k];                else {                    dp(l - 1);                    save[l][i] += save[l - 1][k];                }            }            save[l][i] %= M;     //防止数据过大溢出         }    }}int main() {    init();    cin >> K >> L;    if(K <= 2) {cout << 0 << endl; return 0;}    long long sum = 0;    dp(L);    for(int i = 1; i < K; i++) {        sum += save[L][i];    }    //cout << sum << endl;    cout << sum % M << endl;    return 0;   }
        
       

评测详情

评测点序号	评测结果	得分	CPU使用	内存使用	下载评测数据
1	正确	10.00	0ms	0.984MB
2	正确	10.00	0ms	0.988MB
3	正确	10.00	0ms	0.988MB
4	正确	10.00	0ms	0.988MB
5	正确	10.00	0ms	0.988MB
6	正确	10.00	15ms	0.984MB
7	正确	10.00	0ms	0.984MB
8	正确	10.00	15ms	0.988MB
9	正确	10.00	15ms	0.984MB
10	正确	10.00	15ms	0.984MB