模擬了半天，沒(méi)模擬出來(lái)...撐不住了看題解

汗了，看來(lái)確實(shí)要克服把每道題當(dāng)模擬題做的缺點(diǎn)，多想想...

//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是自然，因?yàn)橐晃坏臅r(shí)候0是不算的。
f[1]=K*(K-1)，可以這樣想，當(dāng)f[1]取K進(jìn)制中某個(gè)除0以外的值的時(shí)候，后面的那位數(shù)字自己不斷變化,這個(gè)時(shí)候后面的那位數(shù)是可以取0的
從第3位開(kāi)始，第N位的時(shí)候就相當(dāng)于第N位隨便變（除0以外），先考慮后N-1位（第N-1位不能為0）。然后還有N-1位為0，后N-2位隨便變。加起來(lái)乘以K-1，即第N位隨便變的即可