結果
問題 | No.220 世界のなんとか2 |
ユーザー |
|
提出日時 | 2019-12-20 10:04:39 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 3,295 bytes |
コンパイル時間 | 1,676 ms |
コンパイル使用メモリ | 191,336 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-07 23:08:43 |
合計ジャッジ時間 | 2,505 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 |
ソースコード
#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;}