/*问题描述 如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字,那么我们就说这个数是K好数。 求L位K进制数中K好数的数目。例如K = 4,L = 2的时候,所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大,请你输出它对1000000007取模后的值。
输入格式 输入包含两个正整数,K和L。
输出格式 输出一个整数,表示答案对1000000007取模后的值。 样例输入 4 2 样例输出 7 数据规模与约定 对于30%的数据,KL <= 106;
对于50%的数据,K <= 16, L <= 10;
对于100%的数据,1 <= K,L <= 100。 思路:用动态规划;若求 K=4 进制 L=1 位则 有 0,1,2,3 。共4种,当L>=2时 第一位不能为0 所以 计算第一位时 把 a[1][0]=0;就是说可以 20 不可 02 可以 200,300 a[i][j]表示 以 j(0,1,2,3.。.。K-1)数 为第i位上的数字 存储的是 这种情况下的K好数 j 0 1 2 3.。。。K-1 i 1 0 1 1 1.。。。 1 2 2 2 1 2.。。。 3 5 4 3 6.。。。 。 。 。 L */
代码语言:javascript复制#include <stdio.h>
int abs(int a)
{if(a>=0)return a;
else return -a;
}
int main()
{long int k,l,m,i,j;
long int sum=0;
long int a[105][105]={0};
scanf("%ld%ld",&k,&l);
if(l>=2)
{ for(i=0;i<k;i )// 当L==1时 所有进制内的数都可以 所以每个数都是 1个K好数
a[1][i]=1;
a[1][0]=0;//第一位不能为0
for(i=2;i<=l;i )
for(j=0;j<k;j )
for(m=0;m<k;m )
{if(abs(j-m)!=1)
a[i][j] =a[i-1][m];//a[i][j]表示第i位填 j 数字a[i-1][m]表示j可与高位那些 m 数结合
if(a[i][j]>1000000007)a[i][j]%=1000000007;//a[i-1][m]表示 以 m 数做低位时的 K好数数目
} //a[i][j]表示 以 j 数做低位时的 K好数数目
}
for(i=0;i<k;i )
{sum =a[l][i];
if(sum>1000000007)sum%=1000000007;
}
printf("%ldn",sum);
return 0;
}