結果

問題 No.260 世界のなんとか3
コンテスト
ユーザー pekempey
提出日時 2019-12-24 10:20:53
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 4,252 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,330 ms
コンパイル使用メモリ 213,052 KB
実行使用メモリ 117,504 KB
最終ジャッジ日時 2024-09-21 15:37:05
合計ジャッジ時間 42,086 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 8 MLE * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

node nodes[1000000];
int ptr = 2;

int create() {
  return ptr++;
}

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;
  pair<int, int> key(x, y);
  if (memo.count(key)) return memo[key];
  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[key] = 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;
  pair<int, int> key(x, y);
  if (memo.count(key)) return memo[key];
  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[key] = 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;
  tuple<int, int> key(k, lt);
  if (memo.count(key)) return memo[key];
  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[key] = res;
}

int GE(string &s, int k = 0, int gt = 0) {
  if (k == s.size()) return 1;
  static map<tuple<int, int>, int> memo;
  tuple<int, int> key(k, gt);
  if (memo.count(key)) return memo[key];
  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[key] = 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;
  tuple<int, int, int, int> key(n, m, k, md);
  if (memo.count(key)) return memo[key];
  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[key] = res;
}

int HAS(int n, int m, int k = 0) {
  if (k == n) return 0;
  static map<tuple<int, int, int>, int> memo;
  tuple<int, int, int> key(n, m, k);
  if (memo.count(key)) return memo[key];
  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[key] = 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 le = LE(B);
  int ge = GE(A);
  int range = cap(ge, le);
  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