簡(jiǎn)單的組合計(jì)數(shù)，算是DP吧。很簡(jiǎn)單的，分“上一位數(shù)是0”和“上一位數(shù)不是0”討論即可。同時(shí)注意到第1位不能是0。
以下是我的代碼：
#include<iostream>
using namespace std;
long n,k;
long dp(long i,long j)
{
if(i==1) return (k-1)*dp(i+1,1);
if(i==n)
{
if(j) return k;
else return (k-1);
}
if(j) return (k-1)*dp(i+1,1)+dp(i+1,0);
else return (k-1)*dp(i+1,1);
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
cin>>n>>k;
cout<<dp(1,1)<<endl;
return 0;
}