模拟了半天，没模拟出来...撑不住了看题解

汗了，看来确实要克服把每道题当模拟题做的缺点，多想想...

//edited by Eddy
//from BUAA SoftWare College
//any question:oeddyo@gmail.com

#include <iostream>
#include <cmath>
using namespace std;


int main()
{
    int N,K;
    cin>>N>>K;
    int f[30];
    f[0]=K-1;
    f[1]=K*(K-1);
    int i;
    for(i=2;i<N;i++)
    {
        f[i]=(K-1)*(f[i-1]+f[i-2]);
    }
    cout<<f[N-1];

return 0;
}

精华就在f[i]=(K-1)*(f[i-1]+f[i-2])这行
f[0]=K-1是自然，因为一位的时候0是不算的。
f[1]=K*(K-1)，可以这样想，当f[1]取K进制中某个除0以外的值的时候，后面的那位数字自己不断变化,这个时候后面的那位数是可以取0的
从第3位开始，第N位的时候就相当于第N位随便变（除0以外），先考虑后N-1位（第N-1位不能为0）。然后还有N-1位为0，后N-2位随便变。加起来乘以K-1，即第N位随便变的即可