简单的递推 f[i][0]表示i位的数合法的以0开头的数量（形如011也算3位，001不合法），f[i][1]表示i位的数合法的以非0开头的数量。
初始f[1][0]=1，f[1][1]=k-1;
f[i][0]=f[i-1][1];
f[i][1]=(f[i-1][1]+f[i-1][0])*(k-1);
要开INT64
#include<stdio.h>
__int64 f[20][2];
__int64 a,b;
long n,k,i;
int main()
{
scanf("%d %d",&n,&k);
f[1][0]=1;f[1][1]=k-1;
for (i=2;i<=n;i++)
{
f[i][0]=f[i-1][1];
a=f[i-1][1]+f[i-1][0];b=k-1;
f[i][1]=a*b;
}
printf("%I64d",f[n][1]);
}
posted on 2011-06-27 17:30
梦转千寻 阅读(44)
评论(0) 编辑 收藏 引用