样例不过求条
查看原帖
样例不过求条
931664
sieve楼主2025/7/31 16:44
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int kN = 20;

int f[kN][2][2][2][2][10][10], n, pl;
string l, r;

signed main() {
  cin.tie(0)->sync_with_stdio(false);
  cin >> l >> r;
  n = r.size(), pl = n - l.size();
  l = string(pl, '0') + l;
  f[0][0][0][0][0][0][0] = 1;
  for (int i = 0; i < n; i++) { // 枚举位
    for (int x = 0; x < 2; x++) { // 0表示之前的数字与下界全部相同
      for (int y = 0; y < 2; y++) { // 0表示之前的数字与上界全部相同
        for (int s = 0; s < 2; s++) { // 1表示同时出现了4和8
          for (int c = 0; c < 2; c++) { // 1表示出现了连续三个相同的数
            for (int q = 1; q <= 9; q++) { // 上一个数字
              for (int j = 1; j <= 9; j++) { // 当前数字
                for (int k = x ? 1 : max(1, l[i] - '0'); k <= (y ? 9 : max(1, r[i] - '0')); k++) { // 下一个数字
                  int nx = x || k > l[i] - '0', ny = y || k < r[i] - '0'; // 下一个状态的x和y
                  int ns = s || ((q == 4 && j == 8) || (q == 4 && k == 8) || (j == 4 && k == 8) || (q == 8 && j == 4) || (q == 8 && k == 4) || (j == 8 && k == 4)); // 下一个状态的s
                  int nc = c || (q == j && j == k); // 下一个状态的c
                  f[i + 1][nx][ny][ns][nc][j][k] += f[i][x][y][s][c][q][j] * (!s && c); // 转移
                }
              }
            }
          }
        }
      }
    }
  }
  cout << accumulate(f[n][0][0][0][0][0], f[n + 1][0][0][0][0][0], 0ll); // 求和(f[n][0][0][0][0][0][0]到f[n][1][1][1][1][9][9])
  return 0;
}

2025/7/31 16:44
加载中...