結果

問題 No.260 世界のなんとか3
コンテスト
ユーザー pekempey
提出日時 2019-12-20 10:15:33
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
MLE  
実行時間 -
コード長 4,710 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,447 ms
コンパイル使用メモリ 207,816 KB
実行使用メモリ 224,800 KB
最終ジャッジ日時 2024-07-07 23:32:03
合計ジャッジ時間 5,931 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other MLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define range(a) a.begin(), a.end()

struct node {
  int k;
  node *ch[10];
  node(int k_) : k(k_) {}
};

enum { ZERO = -1, ONE = -2 };
node zero(ZERO), one(ONE);

node *zdd_ge(string &s, int k = 0, int gt = 0) {
  static map<pair<int, int>, node *> memo;
  if (k == s.size()) return &one;
  if (memo.count({k, gt})) return memo[{k, gt}];
  node *res = new node(k);
  for (int i = 0; i < 10; i++) {
    if (gt == 0) {
      if (i >= s[k] - '0') {
        res->ch[i] = zdd_ge(s, k + 1, i > s[k] - '0');
      } else {
        res->ch[i] = &zero;
      }
    } else {
      res->ch[i] = zdd_ge(s, k + 1, true);
    }
  }
  return memo[{k, gt}] = res;
}

node *zdd_le(string &s, int k = 0, int lt = 0) {
  static map<pair<int, int>, node *> memo;
  if (k == s.size()) return &one;
  if (memo.count({k, lt})) return memo[{k, lt}];
  node *res = new node(k);
  for (int i = 0; i < 10; i++) {
    if (lt == 0) {
      if (i <= s[k] - '0') {
        res->ch[i] = zdd_le(s, k + 1, i < s[k] - '0');
      } else {
        res->ch[i] = &zero;
      }
    } else {
      res->ch[i] = zdd_le(s, k + 1, true);
    }
  }
  return memo[{k, lt}] = res;
}

node *zdd_multiple(int n, int m, int k = 0, int md = 0) {
  static map<tuple<int, int, int, int>, node *> memo;
  if (k == n) return md == 0 ? &one : &zero;
  if (memo.count({n, m, k, md})) return memo[{n, m, k, md}];
  node *res = new node(k);
  for (int i = 0; i < 10; i++) {
    res->ch[i] = zdd_multiple(n, m, k + 1, (md * 10 + i) % m);
  }
  return memo[{n, m, k, md}] = res;
}

node *zdd_three(int n, int k = 0, int has = 0) {
  static map<pair<int, int>, node *> memo;
  if (k == n) return has ? &one : &zero;
  if (memo.count({k, has})) return memo[{k, has}];
  node *res = new node(k);
  for (int i = 0; i < 10; i++) {
    res->ch[i] = zdd_three(n, k + 1, has || i == 3);
  }
  return memo[{k, has}] = res;
}

node *complement(node *x) {
  if (x == &zero) return &one;
  if (x == &one) return &zero;
  static map<node *, node *> memo;
  if (memo.count(x)) return memo[x];
  node *res = new node(x->k);
  for (int i = 0; i < 10; i++) {
    res->ch[i] = complement(x->ch[i]);
  }
  return memo[x] = res;
}

node *cup(node *x, node *y) {
  if (x == &zero && y == &zero) return &zero;
  if (x == &zero) return y;
  if (y == &zero) return x;
  if (x == &one && y == &one) return &one;
  static map<pair<node *, node *>, node *> memo;
  if (memo.count({x, y})) return memo[{x, y}];
  node *res = new node(x->k);
  for (int i = 0; i < 10; i++) {
    res->ch[i] = cup(x->ch[i], y->ch[i]);
  }
  return memo[{x, y}] = res;
}

node *cap(node *x, node *y) {
  if (x == &zero || y == &zero) return &zero;
  if (x == &one) return y;
  if (y == &one) return x;
  static map<pair<node *, node *>, node *> memo;
  if (memo.count({x, y})) return memo[{x, y}];
  node *res = new node(x->k);
  for (int i = 0; i < 10; i++) {
    res->ch[i] = cap(x->ch[i], 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(node *x) {
  if (x->k == ZERO) return 0;
  if (x->k == ONE) return 1;
  static map<node *, mint> memo;
  if (memo.count(x)) return memo[x];
  mint res = 0;
  for (int i = 0; i < 10; i++) {
    res += count(x->ch[i]);
  }
  return memo[x] = res;
}

int main() {
  string A, B;
  cin >> A >> B;
  if (A.size() < B.size()) A = string(B.size() - A.size(), '0') + A;
  if (A.size() > B.size()) B = string(A.size() - B.size(), '0') + B;
  const int N = A.size();
  node *hani = cap(zdd_ge(A), zdd_le(B));
  node *nabeatu = cup(zdd_three(N), zdd_multiple(N, 3));
  node *seisyun = complement(zdd_multiple(N, 8));
  cout << count(cap(hani, cap(nabeatu, seisyun))) << endl;
}
0