結果

問題 No.2513 Power Eraser
ユーザー fastmath
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

#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 up
ll div_down(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
ll math_mod(ll a, ll b) { return a - b * div_down(a, b); }
#define tcT template<class T
#define tcTU tcT, class U
tcT> 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 FFT
int v; explicit operator int() const { return v; } // explicit -> don't silently convert to int
mint() { 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 mods
typedef vector<mi> vmi;
std::ostream& operator << (std::ostream& o, const mi& a)
{
cout << a.v;
return o;
}
vector<vmi> scmb; // small combinations
void 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...n
int 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);
#endif
int 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0