题目178：步差数
Step NumbersConsider the number 45656.
It can be seen that each pair of consecutive digits of 45656 has a difference of one.
A number for which every pair of consecutive digits has a difference of one is called a step number.
A pandigital number contains every decimal digit from 0 to 9 at least once.
How many pandigital step numbers less than 1040 are there?
题目：
考虑 45656 这个数字。
可以发现 45656 相邻位上的两个数字都只相差 1。
我们就把相邻位只相差 1 的数叫做步差数。
而一个 pandigital 数字指的是十进制的 0-9 都至少出现一次的数字。
小于 1040 的 pandigital 步差数有多少个？
本帖最后由 guosl 于 2022-11-22 08:47 编辑
应用状态压缩的递推
答案：126461847755
#include <iostream>
using namespace std;
const int m = (1 << 10);
long long f;//f表示k位数且最高位是i同时j中那些非零的位上数字已经出现过的总步差数个数
int main(void)
{
for (int i = 0; i <= 9; ++i)//赋初值
f = 1;
for (int k = 2; k <= 40; ++k)//按位向大数递推
{
for (int i = 0; i <= 9; ++i)//枚举第i位的数字
{
int p = 1 << i;
for (int j = 1; j < m; ++j)//枚举已经用过的数字
{
if (i >= 1)
f += f;
if (i <= 8)
f += f;
}
}
}
long long nS = 0;
for (int k = 10; k <= 40; ++k)
{
for (int i = 1; i <= 9; ++i)
nS += f;
}
cout << nS << endl;
return 0;
}
页:
[1]