求出N位的K进制数中不包含两个连续的0的数有几个。
例:
比如要算7位的。
1010230 算是一个。 1000198 不算，有3个连续的0了。 0001235 不算，这个是4位的。
input：
两个十进制整数N和K。
(2 <= K <= 10, 2 <= N)
(4 <= N+K <= 18) (1009)
(4 <= N+K <= 180) (1012)
(4 <= N+K <= 1800)(1013)
output：
N位的K进制数中不包含两个连续的0的数的个数，用十进制表示。
分析：
因为两个0不能挨在一起，所以对于长度为i的符合要求的k进制数的个数只跟长度为i-1的符合要求的k进制的数有关。
由此可得：
长度为i的符合要求且第一位为0的k进制数个数为长度为i-1符合要求的首位不为0的k进制数的个数。
长度为i的符合要求且第一位不为0的k进制数的个数为i-1符合要求的k进制数（无论首位是不是0）乘以k-1的积
最后输出长队为n，首位不为0的符合要求的k进制数即可。
【参考程序】：
/*#include<iostream>//1009 code
using namespace std;
int n,k,f[20];
int main()
{
scanf("%d%d",&n,&k);
f[0]=1;f[1]=k-1;
for (int i=2;i<=n;i++)
f[i]=(f[i-1]+f[i-2])*(k-1);
printf("%d\n",f[n]);
system("pause");
return 0;
}*/
#include<iostream>//1012 && 1013 code
using namespace std;
int a[510],b[510],c[510];
int n,k;
int main()
{
scanf("%d%d",&n,&k);
memset(c,0,sizeof(c));
a[1]=1;b[1]=k-1;c[0]=1;
for (int i=2;i<=n;i++)
{
for (int j=1;j<=c[0];j++)
c[j]=(k-1)*(a[j]+b[j]);
for (int j=1;j<=c[0];j++)
{
c[j+1]+=c[j]/100000;
c[j]%=100000;
}
while (c[c[0]+1])
{
c[0]++;
c[c[0]+1]+=c[c[0]]/100000;
c[c[0]]%=100000;
}
memcpy(a,b,sizeof(int)*510);
memcpy(b,c,sizeof(int)*510);
}
printf("%d",c[c[0]]);
for (int i=c[0]-1;i>=1;i--)
printf("%05d",c[i]);
printf("\n");
system("pause");
return 0;
}