結果
問題 | No.2513 Power Eraser |
ユーザー |
![]() |
提出日時 | 2023-10-20 22:29:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4,850 ms / 6,000 ms |
コード長 | 18,019 bytes |
コンパイル時間 | 3,139 ms |
コンパイル使用メモリ | 171,880 KB |
最終ジャッジ日時 | 2025-02-17 10:10:58 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 TLE * 1 -- * 4 |
ソースコード
#include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cmath>#include <vector>#include <set>#include <map>#include <unordered_set>#include <unordered_map>#include <queue>#include <ctime>#include <cassert>#include <complex>#include <string>#include <cstring>#include <chrono>#include <random>#include <bitset>#include <fstream>#include <array>#include <functional>#include <stack>#include <memory>using namespace std;#define int long long#define ii pair <int, int>#define app push_back#define all(a) a.begin(), a.end()#define bp __builtin_popcountll#define ll long long#define mp make_pair#define x first#define y second#define Time (double)clock()/CLOCKS_PER_SEC#define munq(a) sort(all(a)); a.resize(unique(all(a))-a.begin())#define sz(a) ((int)a.size())#ifdef LOCAL#define debug(x) do { cout << #x << ": " << x << endl; } while(0)#define debug2(x, y) do { std::cerr << #x << ", " << #y << ": " << x << ", " << y << endl; } while (0)#define debug3(x, y, z) do {std::cerr << #x << ", " << #y << ", " << #z << ": " << x << ", " << y << ", " << z << endl; } while(0)#else#define debug(x)#define debug2(x, y)#define debug3(x, y, z)#endif#define FORI(i,a,b) for (int i = (a); i < (b); ++i)#define FOR(i,a) FORI(i,0,a)#define ROFI(i,a,b) for (int i = (b)-1; i >= (a); --i)#define ROF(i,a) ROFI(i,0,a)#define rep(a) FOR(_,a)#define each(a,x) for (auto& a: x)#define FORN(i, n) FORI(i, 1, n + 1)using vi = vector<int>;template <typename T>std::istream& operator >>(std::istream& input, std::pair <T, T> & data){input >> data.x >> data.y;return input;}template <typename T>std::istream& operator >>(std::istream& input, std::vector<T>& data){for (T& x : data)input >> x;return input;}template <typename T>std::ostream& operator <<(std::ostream& output, const pair <T, T> & data){output << "(" << data.x << "," << data.y << ")";return output;}template <typename T>std::ostream& operator <<(std::ostream& output, const std::vector<T>& data){for (const T& x : data)output << x << " ";return output;}ll div_up(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded upll div_down(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded downll math_mod(ll a, ll b) { return a - b * div_down(a, b); }#define tcT template<class T#define tcTU tcT, class UtcT> using V = vector<T>;tcT> bool ckmin(T& a, const T& b) {return b < a ? a = b, 1 : 0;} // set a = min(a,b)tcT> bool ckmax(T& a, const T& b) {return a < b ? a = b, 1 : 0;}tcT> vector <T> presum(vector <T> &a) {vector <T> p(a.size() + 1);FOR (i, a.size()) {p[i + 1] = p[i] + a[i];}return p;}tcT> vector <T> sufsum(vector <T> &a) {vector <T> p(a.size() + 1);for (int i = (int)a.size() - 1; i >= 0; --i) {p[i] = p[i + 1] + a[i];}return p;}ll gcd(ll a, ll b) {while (b) {tie(a, b) = mp(b, a % b);}return a;}int Bit(int mask, int bit) { return (mask >> bit) & 1; }template<int MOD, int RT> struct mint {static const int mod = MOD;static constexpr mint rt() { return RT; } // primitive root for FFTint v; explicit operator int() const { return v; } // explicit -> don't silently convert to intmint() { v = 0; }mint(ll _v) { v = (int)((-MOD < _v && _v < MOD) ? _v : _v % MOD);if (v < 0) v += MOD; }friend bool operator==(const mint& a, const mint& b) {return a.v == b.v; }friend bool operator!=(const mint& a, const mint& b) {return !(a == b); }friend bool operator<(const mint& a, const mint& b) {return a.v < b.v; }friend string ts(mint a) { return to_string(a.v); }mint& operator+=(const mint& m) {if ((v += m.v) >= MOD) v -= MOD;return *this; }mint& operator-=(const mint& m) {if ((v -= m.v) < 0) v += MOD;return *this; }mint& operator*=(const mint& m) {v = (int)((ll)v*m.v%MOD); return *this; }mint& operator/=(const mint& m) { return (*this) *= inv(m); }friend mint pow(mint a, ll p) {mint ans = 1; assert(p >= 0);for (; p; p /= 2, a *= a) if (p&1) ans *= a;return ans; }mint & operator ^=(const int &p) { return (*this) = pow(this, p); }friend mint inv(const mint& a) { assert(a.v != 0);return pow(a,MOD-2); }mint operator-() const { return mint(-v); }mint& operator++() { return *this += 1; }mint& operator--() { return *this -= 1; }friend mint operator+(mint a, const mint& b) { return a += b; }friend mint operator-(mint a, const mint& b) { return a -= b; }friend mint operator*(mint a, const mint& b) { return a *= b; }friend mint operator/(mint a, const mint& b) { return a /= b; }friend mint operator^(mint a, const int p) { return pow(a, p); }};const int MOD = 998244353;typedef mint<MOD,5> mi; // 5 is primitive root for both common modstypedef vector<mi> vmi;std::ostream& operator << (std::ostream& o, const mi& a){cout << a.v;return o;}vector<vmi> scmb; // small combinationsvoid genComb(int SZ) {scmb.assign(SZ,vmi(SZ)); scmb[0][0] = 1;FORI(i,1,SZ) FOR(j,i+1)scmb[i][j] = scmb[i-1][j]+(j?scmb[i-1][j-1]:0);}vmi invs, fac, ifac; // make sure to convert to LL before doing any multiplications ...void genFac(int SZ) {invs.resize(SZ), fac.resize(SZ), ifac.resize(SZ);invs[1] = fac[0] = ifac[0] = 1;FORI(i,2,SZ) invs[i] = mi(-(ll)MOD/i*(int)invs[MOD%i]);FORI(i,1,SZ) {fac[i] = fac[i-1]*i;ifac[i] = ifac[i-1]*invs[i];}}mi comb(int a, int b) {if (a < b || b < 0) return 0;assert(a < fac.size());return fac[a]*ifac[b]*ifac[a-b];}mi partNonNegative(int a, int b) {assert(a >= 0);if (a == 0 && b == 0) {return 1;}else {return comb(a + b - 1, b - 1);}}mi partPositive(int a, int b) {assert(a >= 0);if (a == 0 && b == 0) {return 1;}else {return comb(a - 1, b - 1);}}const int md = 998244353;namespace faq{inline void add(int &x, int y) {x += y;if (x >= md) {x -= md;}}inline void sub(int &x, int y) {x -= y;if (x < 0) {x += md;}}inline int mul(int x, int y) {return (long long) x * y % md;}inline int power(int x, int y) {int res = 1;for (; y; y >>= 1, x = mul(x, x)) {if (y & 1) {res = mul(res, x);}}return res;}inline int inv(int a) {a %= md;if (a < 0) {a += md;}int b = md, u = 0, v = 1;while (a) {int t = b / a;b -= t * a;swap(a, b);u -= t * v;swap(u, v);}if (u < 0) {u += md;}return u;}namespace ntt {int base = 1, root = -1, max_base = -1;vector<int> rev = {0, 1}, roots = {0, 1};void init() {int temp = md - 1;max_base = 0;while (temp % 2 == 0) {temp >>= 1;++max_base;}root = 2;while (true) {if (power(root, 1 << max_base) == 1 && power(root, 1 << max_base - 1) != 1) {break;}++root;}}void ensure_base(int nbase) {if (max_base == -1) {init();}if (nbase <= base) {return;}assert(nbase <= max_base);rev.resize(1 << nbase);for (int i = 0; i < 1 << nbase; ++i) {rev[i] = rev[i >> 1] >> 1 | (i & 1) << nbase - 1;}roots.resize(1 << nbase);while (base < nbase) {int z = power(root, 1 << max_base - 1 - base);for (int i = 1 << base - 1; i < 1 << base; ++i) {roots[i << 1] = roots[i];roots[i << 1 | 1] = mul(roots[i], z);}++base;}}void dft(vector<int> &a) {int n = a.size(), zeros = __builtin_ctz(n);ensure_base(zeros);int shift = base - zeros;for (int i = 0; i < n; ++i) {if (i < rev[i] >> shift) {swap(a[i], a[rev[i] >> shift]);}}for (int i = 1; i < n; i <<= 1) {for (int j = 0; j < n; j += i << 1) {for (int k = 0; k < i; ++k) {int x = a[j + k], y = mul(a[j + k + i], roots[i + k]);a[j + k] = (x + y) % md;a[j + k + i] = (x + md - y) % md;}}}}vector<int> multiply(vector<int> a, vector<int> b) {int need = a.size() + b.size() - 1, nbase = 0;while (1 << nbase < need) {++nbase;}ensure_base(nbase);int sz = 1 << nbase;a.resize(sz);b.resize(sz);bool equal = a == b;dft(a);if (equal) {b = a;} else {dft(b);}int inv_sz = inv(sz);for (int i = 0; i < sz; ++i) {a[i] = mul(mul(a[i], b[i]), inv_sz);}reverse(a.begin() + 1, a.end());dft(a);a.resize(need);return a;}vector<int> inverse(vector<int> a) {int n = a.size(), m = n + 1 >> 1;if (n == 1) {return vector<int>(1, inv(a[0]));} else {vector<int> b = inverse(vector<int>(a.begin(), a.begin() + m));int need = n << 1, nbase = 0;while (1 << nbase < need) {++nbase;}ensure_base(nbase);int sz = 1 << nbase;a.resize(sz);b.resize(sz);dft(a);dft(b);int inv_sz = inv(sz);for (int i = 0; i < sz; ++i) {a[i] = mul(mul(md + 2 - mul(a[i], b[i]), b[i]), inv_sz);}reverse(a.begin() + 1, a.end());dft(a);a.resize(n);return a;}}}using ntt::multiply;using ntt::inverse;vector<int>& operator += (vector<int> &a, const vector<int> &b) {if (a.size() < b.size()) {a.resize(b.size());}for (int i = 0; i < b.size(); ++i) {add(a[i], b[i]);}return a;}vector<int> operator + (const vector<int> &a, const vector<int> &b) {vector<int> c = a;return c += b;}vector<int>& operator -= (vector<int> &a, const vector<int> &b) {if (a.size() < b.size()) {a.resize(b.size());}for (int i = 0; i < b.size(); ++i) {sub(a[i], b[i]);}return a;}vector<int> operator - (const vector<int> &a, const vector<int> &b) {vector<int> c = a;return c -= b;}vector<int>& operator *= (vector<int> &a, const vector<int> &b) {if (min(a.size(), b.size()) < 128) {vector<int> c = a;a.assign(a.size() + b.size() - 1, 0);for (int i = 0; i < c.size(); ++i) {for (int j = 0; j < b.size(); ++j) {add(a[i + j], mul(c[i], b[j]));}}} else {a = multiply(a, b);}return a;}vector<int> operator * (const vector<int> &a, const vector<int> &b) {vector<int> c = a;return c *= b;}vector<int>& operator /= (vector<int> &a, const vector<int> &b) {int n = a.size(), m = b.size();if (n < m) {a.clear();} else {vector<int> c = b;reverse(a.begin(), a.end());reverse(c.begin(), c.end());c.resize(n - m + 1);a *= inverse(c);a.erase(a.begin() + n - m + 1, a.end());reverse(a.begin(), a.end());}return a;}vector<int> operator / (const vector<int> &a, const vector<int> &b) {vector<int> c = a;return c /= b;}vector<int>& operator %= (vector<int> &a, const vector<int> &b) {int n = a.size(), m = b.size();if (n >= m) {vector<int> c = (a / b) * b;a.resize(m - 1);for (int i = 0; i < m - 1; ++i) {sub(a[i], c[i]);}}return a;}vector<int> operator % (const vector<int> &a, const vector<int> &b) {vector<int> c = a;return c %= b;}vector<int> derivative(const vector<int> &a) {int n = a.size();vector<int> b(n - 1);for (int i = 1; i < n; ++i) {b[i - 1] = mul(a[i], i);}return b;}vector<int> primitive(const vector<int> &a) {int n = a.size();vector<int> b(n + 1), invs(n + 1);for (int i = 1; i <= n; ++i) {invs[i] = i == 1 ? 1 : mul(md - md / i, invs[md % i]);b[i] = mul(a[i - 1], invs[i]);}return b;}vector<int> logarithm(const vector<int> &a) {vector<int> b = primitive(derivative(a) * inverse(a));b.resize(a.size());return b;}vector<int> exponent(const vector<int> &a) {vector<int> b(1, 1);while (b.size() < a.size()) {vector<int> c(a.begin(), a.begin() + min(a.size(), b.size() << 1));add(c[0], 1);vector<int> old_b = b;b.resize(b.size() << 1);c -= logarithm(b);c *= old_b;for (int i = b.size() >> 1; i < b.size(); ++i) {b[i] = c[i];}}b.resize(a.size());return b;}vector<int> power(const vector<int> &a, int m) {int n = a.size(), p = -1;vector<int> b(n);for (int i = 0; i < n; ++i) {if (a[i]) {p = i;break;}}if (p == -1) {b[0] = !m;return b;}if ((long long) m * p >= n) {return b;}int mu = power(a[p], m), di = inv(a[p]);vector<int> c(n - m * p);for (int i = 0; i < n - m * p; ++i) {c[i] = mul(a[i + p], di);}c = logarithm(c);for (int i = 0; i < n - m * p; ++i) {c[i] = mul(c[i], m);}c = exponent(c);for (int i = 0; i < n - m * p; ++i) {b[i + m * p] = mul(c[i], mu);}return b;}vector<int> sqrt(const vector<int> &a) {vector<int> b(1, 1);while (b.size() < a.size()) {vector<int> c(a.begin(), a.begin() + min(a.size(), b.size() << 1));vector<int> old_b = b;b.resize(b.size() << 1);c *= inverse(b);for (int i = b.size() >> 1; i < b.size(); ++i) {b[i] = mul(c[i], md + 1 >> 1);}}b.resize(a.size());return b;}vector<int> multiply_all(int l, int r, vector<vector<int>> &all) {if (l > r) {return vector<int>();} else if (l == r) {return all[l];} else {int y = l + r >> 1;return multiply_all(l, y, all) * multiply_all(y + 1, r, all);}}vector<int> evaluate(const vector<int> &f, const vector<int> &x) {int n = x.size();if (!n) {return vector<int>();}vector<vector<int>> up(n * 2);for (int i = 0; i < n; ++i) {up[i + n] = vector<int>{(md - x[i]) % md, 1};}for (int i = n - 1; i; --i) {up[i] = up[i << 1] * up[i << 1 | 1];}vector<vector<int>> down(n * 2);down[1] = f % up[1];for (int i = 2; i < n * 2; ++i) {down[i] = down[i >> 1] % up[i];}vector<int> y(n);for (int i = 0; i < n; ++i) {y[i] = down[i + n][0];}return y;}vector<int> interpolate(const vector<int> &x, const vector<int> &y) {int n = x.size();vector<vector<int>> up(n * 2);for (int i = 0; i < n; ++i) { up[i + n] = vector<int>{(md - x[i]) % md, 1};}for (int i = n - 1; i; --i) {up[i] = up[i << 1] * up[i << 1 | 1];}vector<int> a = evaluate(derivative(up[1]), x);for (int i = 0; i < n; ++i) {a[i] = mul(y[i], inv(a[i]));}vector<vector<int>> down(n * 2);for (int i = 0; i < n; ++i) {down[i + n] = vector<int>(1, a[i]);}for (int i = n - 1; i; --i) {down[i] = down[i << 1] * up[i << 1 | 1] + down[i << 1 | 1] * up[i << 1];}return down[1];}vi composition(vi p, vi q) {vi ans;vi cur = {1};each (x, p) {ans += vi({x}) * cur;cur *= q;}return ans;}vi multiply_all(V <vi> &all) {return multiply_all(0,(int)all.size()-1,all);}pair <vi,vi> sum_all(int l, int r, V <pair<vi,vi>> &all) {if (l == r) {return all[l];}int m = (l + r) / 2;auto [a, b] = sum_all(l, m, all);auto [c, d] = sum_all(m + 1, r, all);return {a * d + b * c, b * d};}pair<vi,vi> sum_all(V <pair<vi,vi>> &all) {return sum_all(0,(int)all.size()-1,all);}vi substitute_exp(vi a) {int n = a.size();V <pair <vi, vi> > w;FOR (i, n) {vi nom = {a[i]};vi den = {1,mul(i,998244352)};w.app({nom, den});}auto [u,v] = sum_all(w);vi q = u*inverse(v);int f = 1;FOR(i, n) {if (i) {f = mul(f,i);}q[i] = mul(q[i],inv(f));}return q;}vi binomial_representation(vi a) {int n = sz(a);vi po(n);iota(all(po), 0);vi val = evaluate(a, po);for (int i = 2; i < n; ++i) {val[i] = (mi(val[i])*ifac[i]).v;}vi invexp(n);FOR (i, n) {invexp[i] = ifac[i].v;if (i & 1) {invexp[i] = mi(-invexp[i]).v;}}vi ans = val * invexp;ans.resize(n);FOR (i, n) {ans[i] = (mi(ans[i])*fac[i]).v;}return ans;}vi binomial_representation_by_values(vi val) { //val is values of poly of degree n at 0...nint n = sz(val);for (int i = 2; i < n; ++i) {val[i] = (mi(val[i])*ifac[i]).v;}vi invexp(n);FOR (i, n) {invexp[i] = ifac[i].v;if (i & 1) {invexp[i] = mi(-invexp[i]).v;}}vi ans = val * invexp;ans.resize(n);FOR (i, n) {ans[i] = (mi(ans[i])*fac[i]).v;}return ans;}vi get_poly_by_binomial_representation_slow(vi bin) {int n = sz(bin);vi check(n);FOR (i, n) {V <vi> bi;bi.app({1});FOR (j, i) {bi.app({mi(-j).v, 1});}vi b = multiply_all(bi);each (e, b) {e = (mi(e)/fac[i]).v;}/*debug2(i, b);each (e, b) {cout << mi(e)*6 << ' ';}cout << endl;*/FOR (j, sz(b)) {check[j] = mi(check[j] + b[j]*bin[i]).v;}}return check;}}using namespace faq;mi ans = 1;vector <int> solve(int l, int r, vector <int> &a) {if (l == r) {vector <int> p = {a[l], 998244352};return p;}int m = (l + r) / 2;auto pl = solve(l, m, a), pr = solve(m + 1, r, a);vector <int> po;for (int i = m + 1; i <= r; ++i) {po.push_back(a[i]);}auto res = evaluate(pl, po);for (auto e : res) {ans *= e;}auto p = pl * pr;return p;}signed main() {#ifdef LOCAL#else#define endl '\n'ios_base::sync_with_stdio(0); cin.tie(0);#endifint n;cin >> n;vector <int> a(n);for (int i = 0; i < n; ++i) {cin >> a[i];}solve(0, n - 1, a);/*mi ans = 1;for (int i = 0; i < n; ++i) {for (int j = i + 1; j < n; ++j) {ans *= mi(a[i] - a[j]);}}*/cout << ans << endl;}