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。

代码实现

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#define MAX 110

using namespace std;

const int a=1000000007;

long long use[MAX];

int luse[MAX];

long long sum;

int K,L;

void refreash();

int main()

{

    memset( use,0,sizeof(use) );

    fill( luse,luse + MAX,1);

    sum = 0;

    cin>>K>>L;

    for( int t = 1; t < L; t++ )

    {

        for( int i = 0; i < K; i++ )

        {

            for( int j = 0; j < K; j++ )

            {

                if( j != i-1 && j != i+1 )

                    use[j] += luse[i];

            }

        }

        refreash();

    }

    for( int i = 1; i < K; i++ )

        sum += luse[i]%a;

    cout<<sum%a<<endl;

    return 0;

}

void refreash()

{

    for( int i = 0; i < K; i++ )

    {

        luse[i]=use[i]%a;

        use[i]=0;

    }

    return ;

}