业绩统计网站开发,校园网站建设与应用,交易猫钓鱼网站制作教学,网站优化公司哪家服务好问题描述
如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字#xff0c;那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K 4#xff0c;L 2的时候#xff0c;所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大#xff0c;请你输…问题描述
如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K 4L 2的时候所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大请你输出它对1000000007取模后的值。
输入格式
输入包含两个正整数K和L。
输出格式
输出一个整数表示答案对1000000007取模后的值。
思路
解决这道题需要明确以下几点
1. 相邻的两位不相邻 那就是两位相减不为 1 。例如一个四进制数第一位是 2 那么第二位不能是 1 或 3 可以是 0 或 2 四好数就是所有以1、2、3开头的每个相邻位的数字之差不是 1 的数。
2. 三位 K 好数是在 两位 K 好数的基础上得到的这里体会一下动态规划的特点依据子问题求解原问题。如以 1 开头的三位 K 好数就是不以 0 或 2 开头的两位 K 好数的和。
现在定义一个二维数组 i 表示位数 j 表示进制注意循环的时候 i 是从 1 到 l ,然后我们对二维数组中的每一个位置赋值数组中每个数表示的是以 i 开头的 j 进制好数有几个。
当位数为 1 时都只有一种这里我也不太理解即 nums[1][j] 1 ;
对于其他情况我们把上一行中不和当前 j 相差 1 的nums[i-1][j]加起来。
最后我们要把最后一行从第二列开始相加得到的就是K好数的个数以四进制为例因为0不能做开头所以是把以1、2、3开头的情况加起来。注意每一次加完都要模除要不然提交之后会错一半。
满分代码
#include stdio.hint main(void){int k,l; //k进制l位 scanf(%d %d,k,l);int i,j;int nums[120][120];for(i 1; i l; i) {for(j 0; j k; j){if(i 1)nums[i][j] 1; else{int z;for(z 0; z k; z){if((z - j) ! 1 (j - z) ! 1){nums[i][j] nums[i-1][z]; nums[i][j] % 1000000007; } }}}}int result0;for(j 1; j k; j){result nums[l][j];result % 1000000007;}printf(%d,result);return 0;
}
