結果

問題 No.220 世界のなんとか2
ユーザー pekempeypekempey
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0