题目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

#include <iostream>
using namespace std;

const int m = (1 << 10);
long long f[41][10][m];//f[k][i][j]表示k位数且最高位是i同时j中那些非零的位上数字已经出现过的总步差数个数

int main(void)
{
  for (int i = 0; i <= 9; ++i)//赋初值
    f[1][i][1 << i] = 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[k][i][j | p] += f[k - 1][i - 1][j];
        if (i <= 8)
          f[k][i][j | p] += f[k - 1][i + 1][j];
      }
    }
  }
  long long nS = 0;
  for (int k = 10; k <= 40; ++k)
  {
    for (int i = 1; i <= 9; ++i)
      nS += f[k][i][m - 1];
  }
  cout << nS << endl;
  return 0;
}