递归算法，简单易懂

#include<iostream>

using namespace std;

int n,k;

int judge(bool is_zero,int num)

{

    num++;

    if (num == n)

    {

    if (is_zero == true)

    return 1;

    else

    return k - 1;

    }

    if (is_zero == false)

    return (k-1) * judge(false, num) + (k-1) * judge(true, num);

    else

    return judge(false, num);

}

int main()

{

    cin >> n >> k;

    int sum = judge(false, 0);

    cout << sum;

    return 0;

}