結果

問題 No.220 世界のなんとか2
コンテスト
ユーザー pekempey
提出日時 2019-12-20 10:04:39
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 3,295 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,676 ms
コンパイル使用メモリ 191,336 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-07 23:08:43
合計ジャッジ時間 2,505 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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, int gt) {
  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, int lt) {
  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_mult_three(int n, int k, int md) {
  static map<pair<int, int>, node *> memo;
  if (k == n) return md == 0 ? &one : &zero;
  if (memo.count({k, md})) return memo[{k, md}];
  node *res = new node(k);
  for (int i = 0; i < 10; i++) {
    res->ch[i] = zdd_mult_three(n, k + 1, (md * 10 + i) % 3);
  }
  return memo[{k, md}] = res;
}

node *zdd_three(int n, int k, int has) {
  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 *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 && 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] = cap(x->ch[i], y->ch[i]);
  }
  return memo[{x, y}] = res;
}

ll count(node *x) {
  if (x->k == ZERO) return 0;
  if (x->k == ONE) return 1;
  static map<node *, ll> memo;
  if (memo.count(x)) return memo[x];
  ll res = 0;
  for (int i = 0; i < 10; i++) {
    res += count(x->ch[i]);
  }
  return memo[x] = res;
}

int main() {
  int P; cin >> P;
  string L = string(P, '0') + "1";
  string R = "1" + string(P, '0');
  node *l = zdd_ge(L, 0, 0);
  node *r = zdd_le(R, 0, 0);
  node *y = zdd_three(L.size(), 0, 0);
  node *z = zdd_mult_three(L.size(), 0, 0);
  node *w = cap(cap(l, r), cup(y, z));
  cout << count(w) << endl;
}
0