题目178：步差数

欧拉计划

Step Numbers

Consider 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 10⁴⁰ are there?

题目：

考虑 45656 这个数字。

可以发现 45656 相邻位上的两个数字都只相差 1。

我们就把相邻位只相差 1 的数叫做步差数。

而一个 pandigital 数字指的是十进制的 0-9 都至少出现一次的数字。


小于 10⁴⁰ 的 pandigital 步差数有多少个？

guosl

应用状态压缩的递推
答案：126461847755

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. const int m = (1 << 10);
   
5. long long f[41][10][m];//f[k][i][j]表示k位数且最高位是i同时j中那些非零的位上数字已经出现过的总步差数个数
   
6. 
   
7. int main(void)
   
8. {
   
9.   for (int i = 0; i <= 9; ++i)//赋初值
   
10.     f[1][i][1 << i] = 1;
    
11.   for (int k = 2; k <= 40; ++k)//按位向大数递推
    
12.   {
    
13.     for (int i = 0; i <= 9; ++i)//枚举第i位的数字
    
14.     {
    
15.       int p = 1 << i;
    
16.       for (int j = 1; j < m; ++j)//枚举已经用过的数字
    
17.       {
    
18.         if (i >= 1)
    
19.           f[k][i][j | p] += f[k - 1][i - 1][j];
    
20.         if (i <= 8)
    
21.           f[k][i][j | p] += f[k - 1][i + 1][j];
    
22.       }
    
23.     }
    
24.   }
    
25.   long long nS = 0;
    
26.   for (int k = 10; k <= 40; ++k)
    
27.   {
    
28.     for (int i = 1; i <= 9; ++i)
    
29.       nS += f[k][i][m - 1];
    
30.   }
    
31.   cout << nS << endl;
    
32.   return 0;
    
33. }
    

复制代码