学步园

小记： 上午盯着看了， 由于没注意看题目类型，所以不晓得是用动态规划，于是作死的从各方面想， 先是从数论方面，然后找规律，最后证实都不可行，期间 真的是很想很想 直接百度一下看看别人的思想， 但是想想，觉得这类题 就是一种分界线， 不能靠别人。 于是 再整理好思绪 认真分析， 然后 思路立马就出来了。。唉~ 天意啊， 以后认认真真做题， 坚决不搜题解，只在 代码有问题， 想和别人交流思想的情况下，再去搜题解，那样的效果最好。

思路：L位K进制，都是100 的数量级， 暴力肯定直接pass， 规律，寻不到（寻得到的 都是大神）. 认真分析，对于每一位数， 如果不是最高位，那么都可以用0到k-1这k个数来填充这一位，对于填充的每一位，我们假定已经知道如果这一位填充它的话，那么好数会有f[i][j] 个（i表示第i位，j表示填的数），那么 我们将0-k-1这k个数的f[i][j]的值 全部相加起来最后得到的肯定是我们所要的答案（对于最高位为0，我们会另行判断，这里是假设），于是这里满足了dp的最优化原理，而对于第i位的数字，它的求值是无后效性的，因为结果只是相加，所以dp的无后效性也满足了，那么就可以用dp来做。

然后现在就是状态转移方程，f[i][j] = ∑f[i-1][r] （r != j±1 ，0<=r < k, i > 1）初始化f[1][j] = 1 (0<= j < k);

状态方程对最高位要特殊处理，因为最高位不能为0.

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAX_ = 101;
const int M = 1000000007;

int f[MAX_][MAX_];

int main() {
    int l, k;
    long long ans, n;

    while(cin >> k>> l) {
        if(l == 1){
            cout<<k-1<<endl;
            continue;
        }
        memset(f,0,sizeof(f));
        for(int j = 0; j < k; ++j) {
            f[1][j] = 1;
        }
        for(int i = 2; i < l; ++i) {
            for(int j = 0; j < k; ++j) {
                int cnt = 0;
                for(int r = 0; r < k; ++r) {
                    if(r == j + 1 ||r == j - 1)continue;
                    cnt = (cnt + f[i-1][r]) % M;
                }
                f[i][j] = cnt;
            }
        }
        int sum = 0;
        for(int j = 1; j < k; ++j) {
            int cnt = 0;
            for(int r = 0; r < k; ++r) {
                if(r == j + 1 ||r == j - 1)continue;
                cnt = (cnt + f[l-1][r]) % M;
            }
            sum = (sum + cnt)%M;
        }
        cout<< sum <<endl;
    }
    return 0;
}