結果

問題 No.2595 Parsing Challenge
ユーザー ecotteaecottea
提出日時 2023-12-23 06:01:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 5,345 ms / 6,000 ms
コード長 23,232 bytes
コンパイル時間 5,605 ms
コンパイル使用メモリ 284,140 KB
最終ジャッジ日時 2025-02-18 13:44:44
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 5
other AC * 55
権限があれば一括ダウンロードができます

ソースコード

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

#ifndef HIDDEN_IN_VS //
//
#define _CRT_SECURE_NO_WARNINGS
//
#include <bits/stdc++.h>
using namespace std;
//
using ll = long long; using ull = unsigned long long; // -2^63 2^63 = 9 * 10^18int -2^31 2^31 = 2 * 10^9
using pii = pair<int, int>; using pll = pair<ll, ll>; using pil = pair<int, ll>; using pli = pair<ll, int>;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vvvvi = vector<vvvi>;
using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>; using vvvvl = vector<vvvl>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vc = vector<char>; using vvc = vector<vc>; using vvvc = vector<vvc>;
using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>;
template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
using Graph = vvi;
//
const double PI = acos(-1);
const vi DX = { 1, 0, -1, 0 }; // 4
const vi DY = { 0, 1, 0, -1 };
int INF = 1001001001; ll INFL = 4004004003104004004LL; // (int)INFL = 1010931620;
//
struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp;
//
#define all(a) (a).begin(), (a).end()
#define sz(x) ((int)(x).size())
#define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), x))
#define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), x))
#define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");}
#define YES(b) {cout << ((b) ? "YES\n" : "NO\n");}
#define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 n-1
#define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s t
#define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s t
#define repe(v, a) for(const auto& v : (a)) // a
#define repea(v, a) for(auto& v : (a)) // a
#define repb(set, d) for(int set = 0, set##_ub = 1 << int(d); set < set##_ub; ++set) // d
#define repis(i, set) for(int i = lsb(set), bset##i = set; i >= 0; bset##i -= 1 << i, i = lsb(bset##i)) // set
#define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a
#define smod(n, m) ((((n) % (m)) + (m)) % (m)) // mod
#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} //
#define EXIT(a) {cout << (a) << endl; exit(0);} //
#define inQ(x, y, u, l, d, r) ((u) <= (x) && (l) <= (y) && (x) < (d) && (y) < (r)) //
//
template <class T> inline ll pow(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; }
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // true
    
template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // true
    
template <class T> inline T get(T set, int i) { return (set >> i) & T(1); }
//
template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repea(x, v) is >> x; return is; }
template <class T> inline vector<T>& operator--(vector<T>& v) { repea(x, v) --x; return v; }
template <class T> inline vector<T>& operator++(vector<T>& v) { repea(x, v) ++x; return v; }
#endif //
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#ifdef _MSC_VER
#include "localACL.hpp"
#endif
//using mint = modint1000000007;
using mint = modint998244353;
//using mint = modint; // mint::set_mod(m);
namespace atcoder {
inline istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; }
inline ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; }
}
using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>; using vvvvm = vector<vvvm>;
#endif
#ifdef _MSC_VER // Visual Studio
#include "local.hpp"
#else // gcc
inline int popcount(int n) { return __builtin_popcount(n); }
inline int popcount(ll n) { return __builtin_popcountll(n); }
inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : -1; }
inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : -1; }
inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; }
inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; }
#define dump(...)
#define dumpel(v)
#define dump_list(v)
#define dump_mat(v)
#define input_from_file(f)
#define output_to_file(f)
#define Assert(b) { if (!(b)) while (1) cout << "OLE"; }
#endif
//O(max(n, m))
/*
* b s[0..n) t[0..m)
*/
string add_bint(const string& s, const string& t, int b = 10) {
// verify : https://judge.yosupo.jp/problem/addition_of_big_integers
int i = sz(s) - 1, j = sz(t) - 1, c = 0;
string res;
while (i >= 0 || j >= 0 || c > 0) {
int v = (i >= 0 ? (s[i] - '0') : 0) + (j >= 0 ? (t[j] - '0') : 0) + c;
c = v / b;
res.push_back('0' + (v % b));
i--; j--;
}
reverse(all(res));
return res;
}
//O(max(n, m))
/*
* b s[0..n) t[0..m)
*
* s >= t
*/
string sub_bint(const string& s, const string& t, int b = 10) {
// verify : https://judge.yosupo.jp/problem/addition_of_big_integers
int i = sz(s) - 1, j = sz(t) - 1, c = 0;
string res;
while (i >= 0) {
int vs = (int)(s[i] - '0') - c;
int vt = j >= 0 ? (t[j] - '0') : 0;
c = 0;
if (vs < vt) {
vs += b;
c = 1;
}
res.push_back('0' + (vs - vt));
i--; j--;
}
int k = sz(res) - 1;
while (k >= 0 && res[k] == '0') {
res.pop_back();
k--;
}
if (k == -1) res.push_back('0');
reverse(all(res));
return res;
}
//O((n + m) log(n + m))
/*
* b s[0..n) t[0..m)
*/
string mul_bint(const string& s, const string& t, int base = 10) {
// verify : https://judge.yosupo.jp/problem/multiplication_of_big_integers
if (s == "0" || t == "0") return "0";
int n = sz(s), m = sz(t);
vl a(n), b(m);
rep(i, n) a[i] = s[n - 1 - i] - '0';
rep(j, m) b[j] = t[m - 1 - j] - '0';
vl c = convolution_ll(a, b);
int k = 0;
for (; k < n + m - 2; k++) {
c[k + 1] += c[k] / base;
c[k] %= base;
}
while (c[k] >= base) {
c.push_back(c[k] / base);
c[k] %= base;
k++;
}
string res;
while (k >= 0) {
res += (char)(c[k] + '0');
k--;
}
return res;
}
//O(min(n, m))
/*
* b s[0..n), t[0..m) s[0..n) op t[0..m)
* op ">", ">=", "=", "<=", "<"
*/
bool comp_bint(const string& s, const string& op, const string& t) {
// verify : https://judge.yosupo.jp/problem/addition_of_big_integers
int n = sz(s), m = sz(t);
if (op[0] == '=') return s == t;
if (op[0] == '<') {
// 0
if (n < m) return true;
if (n > m) return false;
//
return op == "<" ? (s < t) : (s <= t);
}
else {
// 0
if (n > m) return true;
if (n < m) return false;
//
return op == ">" ? (s > t) : (s >= t);
}
}
//
/*
* (S, add, o, mi, mul, e) add, mi, mul +, -, *
*/
template <class S, S(*add)(S, S), S(*o_)(), S(*mi)(S), S(*mul)(S, S), S(*e_)()>
struct Ring {
S v;
//
static S o() { return o_(); }
//
static S e() { return e_(); }
//
Ring() : v(o()) {}
Ring(S v) : v(v) {}
Ring(int v) : v(to_string(v)) {}
//
operator S() const { return v; }
//
bool operator==(const Ring& b) const { return v == b.v; }
bool operator!=(const Ring& b) const { return v != b.v; }
//
Ring operator-() const { return Ring(mi(v)); }
//
Ring& operator+=(const Ring& b) { v = add(v, b.v); return *this; }
Ring& operator-=(const Ring& b) { v = add(v, mi(b.v)); return *this; }
Ring& operator*=(const Ring& b) { v = mul(v, b.v); return *this; }
friend Ring operator+(Ring a, const Ring& b) { a += b; return a; }
friend Ring operator-(Ring a, const Ring& b) { a -= b; return a; }
friend Ring operator*(Ring a, const Ring& b) { a *= b; return a; }
//
friend istream& operator>>(istream& is, Ring& a) { is >> a.v; return is; }
friend ostream& operator<<(ostream& os, const Ring& a) {
#ifdef _MSC_VER
if (a.v == o()) return os << "o";
if (a.v == e()) return os << "e";
#endif
return os << a.v;
}
};
// -
using S405 = string;
S405 add405(S405 a, S405 b) {
int ca = 1, cb = 1;
if (a[0] == '-') {
ca = -1;
a.erase(a.begin());
}
if (b[0] == '-') {
cb = -1;
b.erase(b.begin());
}
string res;
if (ca == 1 && cb == 1) {
res = add_bint(a, b);
}
else if (ca == 1 && cb == -1) {
if (comp_bint(a, "<", b)) {
res = sub_bint(b, a);
res.insert(res.begin(), '-');
}
else {
res = sub_bint(a, b);
}
}
else if (ca == -1 && cb == 1) {
if (comp_bint(a, ">", b)) {
res = sub_bint(a, b);
res.insert(res.begin(), '-');
}
else {
res = sub_bint(b, a);
}
}
else if (ca == -1 && cb == -1) {
res = add_bint(a, b);
res.insert(res.begin(), '-');
}
return res;
}
S405 o405() { return "0"; }
S405 mi405(S405 a) {
if (a == "0") {
;
}
else if (a[0] == '-') {
a.erase(a.begin());
}
else {
a.insert(a.begin(), '-');
}
return a;
}
S405 mul405(S405 a, S405 b) {
int ca = 1, cb = 1;
if (a[0] == '-') {
ca = -1;
a.erase(a.begin());
}
if (b[0] == '-') {
cb = -1;
b.erase(b.begin());
}
string res;
if (ca == cb) {
res = mul_bint(a, b);
}
else {
res = mul_bint(b, a);
if (res != "0") res.insert(res.begin(), '-');
}
return res;
}
S405 e405() { return "1"; }
#define BintAdd_Mul_cring S405, add405, o405, mi405, mul405, e405
using Bint = Ring<BintAdd_Mul_cring>;
string s; int i = 0;
vi l, r; vc op; vector<Bint> v; int pt = 0;
int number2() {
int sgn = 1;
while (s[i] == '-') {
i++;
sgn *= -1;
}
string num;
while (isdigit(s[i])) {
num += s[i];
i++;
}
l.push_back(-1);
r.push_back(-1);
op.push_back('n');
v.emplace_back(Bint(to_string(sgn)) * Bint(move(num)));
return pt++;
}
int expression2();
int factor2() {
int x = -1;
if (s[i] == '(') {
i++;
x = expression2();
i++;
}
else {
x = number2();
}
return x;
}
int term2() {
int x = factor2();
while (1) {
if (s[i] == '*') {
i++;
int y = factor2();
l.push_back(x);
r.push_back(y);
op.push_back('*');
v.emplace_back(0);
x = pt++;
}
else break;
}
return x;
}
int expression2() {
int x = term2();
while (1) {
if (s[i] == '+') {
i++;
int y = term2();
l.push_back(x);
r.push_back(y);
op.push_back('+');
v.emplace_back(0);
x = pt++;
}
else if (s[i] == '-') {
i++;
int y = term2();
l.push_back(x);
r.push_back(y);
op.push_back('-');
v.emplace_back(0);
x = pt++;
}
else break;
}
return x;
}
//
/*
* Fixed_matrix<T, n>() : O(n^2)
* T n×n
*
* Fixed_matrix<T, n>(bool identity = true) : O(n^2)
* T n×n
*
* Fixed_matrix<T, n>(vvT a) : O(n^2)
* a[0..n)[0..n)
*
* A + B : O(n^2)
* n×n A, B += 使
*
* A - B : O(n^2)
* n×n A, B -= 使
*
* c * A A * c : O(n^2)
* n×n A c *= 使
*
* A * x : O(n^2)
* n×n A n array<T, n> x
*
* x * A : O(n^2)
* n array<T, n> x n×n A
*
* A * B : O(n^3)
* n×n A n×n B
*
* Mat pow(ll d) : O(n^3 log d)
* d
*/
template <class T, int n>
struct Fixed_matrix {
array<array<T, n>, n> v; //
// n×n identity = true n×n
Fixed_matrix(bool identity = false) {
rep(i, n) v[i].fill(T(0));
if (identity) rep(i, n) v[i][i] = T(1);
}
// a[0..n)[0..n)
Fixed_matrix(const vector<vector<T>>& a) {
// verify : https://yukicoder.me/problems/no/1000
Assert(sz(a) == n && sz(a[0]) == n);
rep(i, n) rep(j, n) v[i][j] = a[i][j];
}
//
Fixed_matrix(const Fixed_matrix&) = default;
Fixed_matrix& operator=(const Fixed_matrix&) = default;
//
inline array<T, n> const& operator[](int i) const { return v[i]; }
inline array<T, n>& operator[](int i) { return v[i]; }
//
friend istream& operator>>(istream& is, Fixed_matrix& a) {
rep(i, n) rep(j, n) is >> a[i][j];
return is;
}
//
bool operator==(const Fixed_matrix& b) const { return v == b.v; }
bool operator!=(const Fixed_matrix& b) const { return !(*this == b); }
//
Fixed_matrix& operator+=(const Fixed_matrix& b) {
rep(i, n) rep(j, n) v[i][j] += b[i][j];
return *this;
}
Fixed_matrix& operator-=(const Fixed_matrix& b) {
rep(i, n) rep(j, n) v[i][j] -= b[i][j];
return *this;
}
Fixed_matrix& operator*=(const T& c) {
rep(i, n) rep(j, n) v[i][j] *= c;
return *this;
}
Fixed_matrix operator+(const Fixed_matrix& b) const { return Fixed_matrix(*this) += b; }
Fixed_matrix operator-(const Fixed_matrix& b) const { return Fixed_matrix(*this) -= b; }
Fixed_matrix operator*(const T& c) const { return Fixed_matrix(*this) *= c; }
friend Fixed_matrix operator*(const T& c, const Fixed_matrix& a) { return a * c; }
Fixed_matrix operator-() const { return Fixed_matrix(*this) *= T(-1); }
// : O(n^2)
array<T, n> operator*(const array<T, n>& x) const {
array<T, n> y{ 0 };
rep(i, n) rep(j, n) y[i] += v[i][j] * x[j];
return y;
}
// : O(n^2)
friend array<T, n> operator*(const array<T, n>& x, const Fixed_matrix& a) {
array<T, n> y{ 0 };
rep(i, n) rep(j, n) y[j] += x[i] * a[i][j];
return y;
}
// O(n^3)
Fixed_matrix operator*(const Fixed_matrix& b) const {
// verify : https://yukicoder.me/problems/no/1000
Fixed_matrix res;
rep(i, n) rep(j, n) rep(k, n) res[i][j] += v[i][k] * b[k][j];
return res;
}
Fixed_matrix& operator*=(const Fixed_matrix& b) { *this = *this * b; return *this; }
// O(n^3 log d)
Fixed_matrix pow(ll d) const {
Fixed_matrix res(true), pow2(*this);
while (d > 0) {
if (d & 1) res *= pow2;
pow2 *= pow2;
d /= 2;
}
return res;
}
#ifdef _MSC_VER
friend ostream& operator<<(ostream& os, const Fixed_matrix& a) {
rep(i, n) {
os << "[";
rep(j, n) os << a[i][j] << " ]"[j == n - 1];
if (i < n - 1) os << "\n";
}
return os;
}
#endif
};
using MAT = Fixed_matrix<Bint, 2>;
//O(n (log n)^2)
/*
* Πi∈[0..n) (z - x[i])
*
* i x[0..n) n-i
*/
MAT expand(vector<MAT> f) {
// verify : https://judge.yosupo.jp/problem/factorial
int n = sz(f);
// 2
for (int k = 1; k < n; k *= 2) {
for (int i = 0; i + k < n; i += 2 * k) {
f[i] = f[i] * f[i + k];
}
}
return f[0];
}
// DPmod 998244353O(n (log n)^3)
/*
* r r
*
* :
* f(z), g(z)
* f(z) g(z)
*
* MFPS leaf(int s) :
* s
*
* pair<MFPS, MFPS> apply(int s) :
* f(z) s
* a(z) f(z) + b(z) {a(z), b(z)}
*
* ,
*/
Bint tree_getDP_forest_MFPS(int rt) {
// : https://atcoder.jp/contests/abc269/editorial/4838
// verify : https://atcoder.jp/contests/abc269/tasks/abc269_h
int n = pt;
// DP
//
vi w(n);
function<int(int)> dfs_w = [&](int s) {
w[s]++;
if (l[s] != -1) w[s] += dfs_w(l[s]);
if (r[s] != -1) w[s] += dfs_w(r[s]);
return w[s];
};
dfs_w(rt); dump(w);
function<MAT(int)> dfs_root;
function<void(int, vector<MAT>&)> dfs_path;
// heavy path s
dfs_root = [&](int s) {
// s
if (l[s] == -1) {
MAT mat;
mat[0][0] = v[s];
mat[1][0] = Bint("1");
return mat;
}
// fh : s heavy path
// coef : fh
vector<MAT> fh;
// heavy path fh, coef
if (w[l[s]] > w[r[s]]) {
MAT mat(true);
if (op[s] == '+') {
mat[0][1] = dfs_root(r[s])[0][0];
}
else if (op[s] == '-') {
mat[0][1] = -dfs_root(r[s])[0][0];
}
else {
mat[0][0] = dfs_root(r[s])[0][0];
}
fh.emplace_back(mat);
dfs_path(l[s], fh);
}
else {
MAT mat(true);
if (op[s] == '+') {
mat[0][1] = dfs_root(l[s])[0][0];
}
else if (op[s] == '-') {
mat[0][0] = Bint("-1");
mat[0][1] = dfs_root(l[s])[0][0];
}
else {
mat[0][0] = dfs_root(l[s])[0][0];
}
fh.emplace_back(mat);
dfs_path(r[s], fh);
}
// heavy path
auto mat = expand(fh);
dump("s:", s); dumpel(fh); dump(mat);
return mat;
};
// heavy path s
// fh : s heavy path
// coef : fh
dfs_path = [&](int s, vector<MAT>& fh) {
// s
if (l[s] == -1) {
MAT mat;
mat[0][0] = v[s];
mat[1][0] = Bint("1");
fh.emplace_back(mat);
return;
}
if (w[l[s]] > w[r[s]]) {
MAT mat(true);
if (op[s] == '+') {
mat[0][1] = dfs_root(r[s])[0][0];
}
else if (op[s] == '-') {
mat[0][1] = -dfs_root(r[s])[0][0];
}
else {
mat[0][0] = dfs_root(r[s])[0][0];
}
fh.emplace_back(mat);
dfs_path(l[s], fh);
}
else {
MAT mat(true);
if (op[s] == '+') {
mat[0][1] = dfs_root(l[s])[0][0];
}
else if (op[s] == '-') {
mat[0][0] = Bint("-1");
mat[0][1] = dfs_root(l[s])[0][0];
}
else {
mat[0][0] = dfs_root(l[s])[0][0];
}
fh.emplace_back(mat);
dfs_path(r[s], fh);
}
};
return dfs_root(rt)[0][0];
};
int main() {
// input_from_file("input.txt");
// output_to_file("output.txt");
int n;
cin >> n >> s;
s.push_back('$');
int rt = expression2();
dump(l); dump(r); dump(op); dump(v); dump(rt); dump(pt);
//function<void(int)> dfs = [&](int s) {
// if (l[s] == -1) {
// cout << v[s];
// }
// else {
// cout << "(";
// dfs(l[s]);
// cout << op[s];
// dfs(r[s]);
// cout << ")";
// }
//};
//dfs(rt); cout << endl;
//
cout << tree_getDP_forest_MFPS(rt) << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0