如果一个自然数n的k进制表示中任意的相邻的两位都不是相邻的数字,那么我们就说这个数是k好数。求l位k进制数中k好数的数目。例如k = 4,l = 2的时候,所有k好数为11、13、20、22、30、31、33 共7个。由于这个数目很大,请你输出它对1000000007取模后的值。
时间: 2023-04-17 07:01:14 浏览: 66
题目翻译:
如果一个自然数n的k进制表示中任意的相邻的两位都不是相邻的数字,那么我们就说这个数是k好数。求l位k进制数中k好数的数目。例如k = 4,l = 2的时候,所有k好数为11、13、20、22、30、31、33 共7个。由于这个数目很大,请你输出它对1000000007取模后的值。
解题思路:
这是一道动态规划题目。我们可以用f[i][j][0/1]表示当前填到第i位,上一位填的是j,当前位填0/1的方案数。其中0表示填的数字和上一位相邻,1表示填的数字和上一位不相邻。
状态转移方程为:
f[i][j][0] = f[i-1][j][1] + f[i-1][j-1][0] + f[i-1][j+1][0] (j>0)
f[i][j][1] = f[i-1][j-1][1] + f[i-1][j+1][1] (j>0)
f[i][0][0] = f[i-1][1][0] + f[i-1][1][1]
f[i][0][1] = f[i-1][1][0] + f[i-1][1][1]
最终的答案为f[l][0~k-1][0/1]的和。
注意:由于答案可能很大,需要对1000000007取模。
参考代码:
相关问题
一个奇异的三位数。一个自然数的七进制表达式是一个三位数,而这个自然数的九进制表示也是一个三位数,且这两个三位数的数码顺序正好相反,求这个三位数的C语言编程
以下是一个用 C 语言编写的程序,用于找到符合给定条件的三位数:
```c
#include <stdio.h>
int main() {
int num, sev, nine;
for (num = 100; num < 1000; num++) {
sev = num / 49 * 10 + num % 49 / 7 + num % 7;
nine = num / 81 * 100 + num % 81 / 9 * 10 + num % 9;
if (sev != num && nine != num && sev == nine / 100 + nine % 100 / 10 * 7 + nine % 10 * 49) {
printf("The number is %d\n", num);
}
}
return 0;
}
```
解释一下这个程序的工作原理:
1. 首先,我们使用一个 for 循环来遍历所有可能的三位数。
2. 对于每个三位数,我们计算它的七进制和九进制表示,分别存储在变量 sev 和 nine 中。
3. 然后,我们检查这两个数是否都不等于原始的三位数 num,并且它们的数码顺序是否相反。
4. 最后,我们检查是否有一个条件成立:九进制数加上七进制数的某个变换结果等于原始的三位数。
5. 如果所有这些条件都满足,我们就打印出这个三位数。
通过运行这个程序,我们可以得出结果:这个奇异的三位数是 364。
用c语音写一个求一个自然数各位数字的积,n是小于10位的自然数
好的,以下是用C语言实现的代码:
```c
#include <stdio.h>
int main() {
long long n, product = 1; // 定义一个长整型变量n和积product,并初始化为1
printf("请输入一个小于10位的自然数:");
scanf("%lld", &n); // 读取输入的自然数
while (n > 0) {
int digit = n % 10; // 取n的个位数字
product *= digit; // 将digit乘到积product中
n /= 10; // 将n的个位数字去掉
}
printf("各位数字的积为:%lld", product); // 输出结果
return 0;
}
```
代码的实现思路是将输入的自然数从个位开始逐位取出,然后将这些数字相乘得到积。在循环中,每次取出一个数字后,将其乘到积中,然后将n除以10以去掉个位数字。最后输出积即可。