URAL_1009

    其实本质只有两类数，0和非0，所以可以用f[i][0]、f[i][1]表示递推到第i位时为0以及非0的情况种数进行dp。

#include
     
      #include
      
       #define MAXD 20int N, K;long long f[MAXD][2];void solve(){    int i, j, k;    f[1][1] = K - 1, f[1][0] = 0;    for(i = 2; i <= N; i ++)        f[i][0] = f[i - 1][1], f[i][1] = (K - 1) * (f[i - 1][0] + f[i - 1][1]);    printf("%lld\n", f[N][0] + f[N][1]);}int main(){    while(scanf("%d%d", &N, &K) == 2)    {        solve();    }    return 0;}