結果

問題 No.260 世界のなんとか3
ユーザー pekempeypekempey
提出日時 2019-12-24 09:37:43
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,145 bytes
コンパイル時間 2,901 ms
コンパイル使用メモリ 217,436 KB
実行使用メモリ 5,476 KB
最終ジャッジ日時 2024-09-21 14:35:28
合計ジャッジ時間 8,191 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 AC 2 ms
5,376 KB
testcase_28 RE -
testcase_29 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct node {
  int k;
  int ch[10];
};

vector<node> nodes(2);

int create() {
  int res = nodes.size();
  nodes.emplace_back();
  return res;
}

int complement(int x) {
  if (x == 0) return 1;
  if (x == 1) return 0;
  static map<int, int> memo;
  if (memo.count(x)) return memo[x];
  int res = create();
  for (int i = 0; i < 10; i++) {
    nodes[res].ch[i] = complement(nodes[x].ch[i]);
  }
  return memo[x] = res;
}

int cup(int x, int y) {
  if (x == 1 || y == 1) return 1;
  if (x == 0) return y;
  if (y == 0) return x;
  static map<pair<int, int>, int> memo;
  if (memo.count({x, y})) return memo[{x, y}];
  int res = create();
  for (int i = 0; i < 10; i++) {
    nodes[res].ch[i] = cup(nodes[x].ch[i], nodes[y].ch[i]);
  }
  return memo[{x, y}] = res;
}

int cap(int x, int y) {
  if (x == 0 || y == 0) return 0;
  if (x == 1) return y;
  if (y == 1) return x;
  static map<pair<int, int>, int> memo;
  if (memo.count({x, y})) return memo[{x, y}];
  int res = create();
  for (int i = 0; i < 10; i++) {
    nodes[res].ch[i] = cap(nodes[x].ch[i], nodes[y].ch[i]);
  }
  return memo[{x, y}] = res;
}

constexpr int MOD = 1000000007;

class mint {
  int n;
  public:
  mint(int n_ = 0) : n(n_) {}
  explicit operator int() { return n; }
  friend mint operator-(mint a) { return -a.n + MOD * (a.n != 0); }
  friend mint operator+(mint a, mint b) { int x = a.n + b.n; return x - (x >= MOD) * MOD; }
  friend mint operator-(mint a, mint b) { int x = a.n - b.n; return x + (x < 0) * MOD; }
  friend mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
  friend mint &operator+=(mint &a, mint b) { return a = a + b; }
  friend mint &operator-=(mint &a, mint b) { return a = a - b; }
  friend mint &operator*=(mint &a, mint b) { return a = a * b; }
  friend bool operator==(mint a, mint b) { return a.n == b.n; }
  friend bool operator!=(mint a, mint b) { return a.n != b.n; }
  friend istream &operator>>(istream &i, mint &a) { return i >> a.n; }
  friend ostream &operator<<(ostream &o, mint a) { return o << a.n; }
};

mint count(int x) {
  if (x == 0) return 0;
  if (x == 1) return 1;
  static map<int, mint> memo;
  if (memo.count(x)) return memo[x];
  mint res = 0;
  for (int i = 0; i < 10; i++) {
    res += count(nodes[x].ch[i]);
  }
  return memo[x] = res;
}

// -------------------------

int LE(string &s, int k = 0, int lt = 0) {
  if (k == s.size()) return 1;
  static map<tuple<int, int>, int> memo;
  if (memo.count({k, lt})) return memo[{k, lt}];
  int res = create();
  for (int i = 0; i < 10; i++) {
    if (lt == 1 || i <= s[k] - '0') {
      nodes[res].ch[i] = LE(s, k + 1, lt || (i < s[k] - '0'));
    }
  }
  return memo[{k, lt}] = res;
}

int GE(string &s, int k = 0, int gt = 0) {
  if (k == s.size()) return 1;
  static map<tuple<int, int>, int> memo;
  if (memo.count({k, gt})) return memo[{k, gt}];
  int res = create();
  for (int i = 0; i < 10; i++) {
    if (gt == 1 || i >= s[k] - '0') {
      nodes[res].ch[i] = GE(s, k + 1, gt || (i > s[k] - '0'));
    }
  }
  return memo[{k, gt}] = res;
}

int MULT(int n, int m, int k = 0, int md = 0) {
  if (k == n) return md == 0;
  static map<tuple<int, int, int, int>, int> memo;
  if (memo.count({n, m, k, md})) return memo[{n, m, k, md}];
  int res = create();
  for (int i = 0; i < 10; i++) {
    nodes[res].ch[i] = MULT(n, m, k + 1, (md * 10 + i) % m);
  }
  return memo[{n, m, k, md}] = res;
}

int HAS(int n, int m, int k = 0) {
  if (k == n) return 0;
  static map<tuple<int, int, int>, int> memo;
  if (memo.count({n, m, k})) return memo[{n, m, k}];
  int res = create();
  for (int i = 0; i < 10; i++) {
    if (i == m) {
      nodes[res].ch[i] = 1;
    } else {
      nodes[res].ch[i] = HAS(n, m, k + 1);
    }
  }
  return memo[{n, m, k}] = res;
}

int main() {
  string A, B; cin >> A >> B;
  if (A.size() < B.size()) A = string(B.size() - A.size(), '0') + A;
  int n = A.size();
  int range = cap(GE(A), LE(B));
  int aho = cup(HAS(n, 3), MULT(n, 3));
  int seisyun = MULT(n, 8);
  int ans = cap(range, cap(aho, complement(seisyun)));
  cout << count(ans) << endl;
}
0