题解

贝西有一部带有九个按钮的新手机，布局如下：
123
456
789
贝西正试图匆忙输入给定的****，因此她决定
通过用一只
蹄子同时按下多个按钮来节省时间。具体来说，贝西的蹄子可能会按一个数字，共享一条边
的两个数字（总共十二个可能的对），或形成一个正方形的
四个数字（1245、2356、4578 或 5689）。
例如，如果 Bessie 尝试键入的****123659874，她
可能会尝试通过以下方式节省时间

同时按 1 和 2。
按 3。
同时按 6、5、9 和 8。
同时按 7 和 4。
不幸的是，贝茜大大高估了她执行这项
任务的技能——如果贝茜的蹄子同时按下多个按钮，那么所有
数字都将以任意顺序输入。因此，如果 Bessie 尝试
上述按压顺序，她最终可能会输入123596847或213659874
（或许多其他可能性之一）。
给定 Bessie 键入的一系列数字，计算她可能尝试键入模数的****
数量
1
0
9
+
7
10
9
+7.
注意：此问题的时间限制为 4 秒，是默认值的两倍。
输入格式
第一行包含
�
T (
1
≤
�
≤
10
1≤T≤10），要解决的独立测试
用例的数量。
下一个
�
T每行都包含一个由数字 1 到 9 组成的非空字符串。
保证这些字符串的总长度不超过
1
0
5
10
5
.

输出格式
对于每个测试用例，Bessie 可能尝试
键入模数的****数量
1
0
9
+
7
10
9
+7.

输入输出样例
输入#1

复制
5
1478
4455
5968
31313211
123659874
输出#1

复制
5
2
24
3
255
说明/提示
对于第一种情况，Bessie 可能尝试键入以下五个
****中的任何一个：
1478 1487 4178

4187
1748
例如，如果 Bessie 尝试键入
4187，她可能会尝试同时按 1 和 4，然后尝试同时按
7 和 8。
对于第三种情况，当数字形成一个正方形时，Bessie 可能一直在
尝试键入输入序列的任何排列。

~~有亿点长~~

```cpp
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

using pi = pair<int, int>;
#define mp make_pair
#define f first
#define s second

using vi = vector<int>;
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define sor(x) sort(all(x))
#define pb push_back
#define bk back()

const int MOD = 1e9 + 7;

template <class T> void remDup(vector<T> &v) {
  sort(all(v));
  v.erase(unique(all(v)), end(v));
}

struct mi {
  int v;
  explicit operator int() const { return v; }
  mi() : v(0) {}
  mi(ll _v) : v(int(_v % MOD)) { v += (v < 0) * MOD; }
};
mi &operator+=(mi &a, mi b) {
  if ((a.v += b.v) >= MOD)
    a.v -= MOD;
  return a;
}
mi operator+(mi a, mi b) { return a += b; }

const int HASHMAX = 16 * 1000;
struct Table {
  mi vals[HASHMAX];
  bitset<HASHMAX> visited;
  vi keys;
  void addTo(int key, mi v) {
    if (visited[key] == 0) {
      visited[key] = 1;
      keys.pb(key);
    }
    vals[key] += v;
  }
  void reset() {
    for (const auto &u : keys) {
      vals[u] = 0;
      visited[u] = 0;
    }
    keys.clear();
  }
};

vector<vi> good_subs;
bool is_good_new_set[100005];

void genGoodSubs() {
  for (int i = 1; i <= 9; i++) {
    good_subs.pb({i});
  }
  for (int i = 1; i + 3 <= 9; i++) {
    good_subs.pb({i, i + 3});
  }

  for (int i = 1; i <= 2; i++) {
    for (int j = 0; j <= 6; j += 3) {
      int first_val = i + j;
      good_subs.pb({first_val, first_val + 1});
    }
  }

  for (int i = 1; i <= 2; i++) {
    for (int j = 0; j <= 3; j += 3) {
      vi v;
      for (int k = 0; k <= 1; k++) {
        for (int l = 0; l <= 3; l += 3) {
          v.pb(i + j + k + l);
        }
      }
      sor(v);
      good_subs.pb(v);
    }
  }

  for (auto u : good_subs) {
    int mask = 0;
    for (auto x : u) {
      mask += 1 << x;
    }
    is_good_new_set[mask] = 1;
  }
}

void solve() {
  string S_inp;
  cin >> S_inp;
  vi S{-100};
  for (auto u : S_inp) {
    S.pb(u - '0');
  }

  int N = sz(S) - 1;

  vector<vi> S_masks = vector<vi>(N + 1, vi(5));
  for (int i = 1; i <= N; i++) {
    for (int j = 0; j <= 4; j++) {
      for (int k = 0; k <= j; k++) {
        S_masks[i][j] |= (1 << S[i + k]);
      }
    }
  }

  Table *dp = new Table();
  Table *ndp = new Table();

  dp->addTo(1 + 111 * 16, mi(1));

  for (int i = 1; i <= N; i++) {
    vi cand_new_digs;
    for (int j = -3; j <= 3; j++) {
      if (i + j >= 1 && i + j <= N) {
        cand_new_digs.pb(S[i + j]);
      }
    }
    remDup(cand_new_digs);

    ndp->reset();
    for (auto u : dp->keys) {
      int bars = u % 16;
      int nums = u / 16;
      int max_bars = 0;
      for (int j = 0; j < 4; j++) {
        if ((bars >> j) & 1) {
          max_bars = j;
        }
      }
      mi ways = dp->vals[u];
      for (int new_dig : cand_new_digs) {
        array<int, 4> all_nums_arr{new_dig, nums % 10, (nums / 10) % 10,
                                   (nums / 100) % 10};
        int new_bars = 0;
        int bar_2_set = 0;
        for (int old_bar = 0; old_bar <= max_bars; old_bar++) {
          int bar_2_set_dig = all_nums_arr[old_bar];
          if ((bar_2_set >> bar_2_set_dig) & 1) {
            break;
          } else {
            bar_2_set |= 1 << bar_2_set_dig;
            if ((bars >> old_bar) & 1) {
              if ((bar_2_set & S_masks[i - old_bar][3]) == bar_2_set) {
                if (is_good_new_set[bar_2_set] &&
                    bar_2_set == S_masks[i - old_bar][old_bar]) {
                  new_bars |= 1;
                }
                if (old_bar < 3) {
                  new_bars |= 1 << (old_bar + 1);
                }
              }
            }
          }
        }
        if (new_bars == 0)
          continue;
        for (int j = 3; j; --j) {
          if (new_bars & (1 << j)) {
            break;
          }
          all_nums_arr[j - 1] = 0;
        }
        int new_nums =
            all_nums_arr[0] + 10 * all_nums_arr[1] + 100 * all_nums_arr[2];
        ndp->addTo(new_bars + 16 * new_nums, ways);
      }
    }

    swap(dp, ndp);
  }

  mi ans = 0;
  for (int u : dp->keys) {
    if (((u % 16) >> 0) & 1) {
      ans += dp->vals[u];
    }
  }

  cout << ans.v << "\n";
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  genGoodSubs();
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    solve();
  }
}

```