結果
問題 | No.1548 [Cherry 2nd Tune B] 貴方と私とサイクルとモーメント |
ユーザー |
![]() |
提出日時 | 2021-06-11 23:12:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4,095 ms / 4,500 ms |
コード長 | 23,417 bytes |
コンパイル時間 | 3,615 ms |
コンパイル使用メモリ | 233,688 KB |
最終ジャッジ日時 | 2025-01-22 06:59:49 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 42 |
ソースコード
// >>> TEMPLATES#include <bits/stdc++.h>using namespace std;using ll = long long;using ld = long double;using i32 = int32_t;using i64 = int64_t;using u32 = uint32_t;using u64 = uint64_t;#define int ll#define rep(i, n) for (int i = 0; i < (int)(n); i++)#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)#define repR(i, n) for (int i = (int)(n)-1; i >= 0; i--)#define rep1R(i, n) for (int i = (int)(n); i >= 1; i--)#define loop(i, a, B) for (int i = a; i B; i++)#define loopR(i, a, B) for (int i = a; i B; i--)#define all(x) begin(x), end(x)#define allR(x) rbegin(x), rend(x)#define rng(x, l, r) begin(x) + (l), begin(x) + (r)#define pb push_back#define eb emplace_back#define fst first#define snd secondtemplate <class A, class B> constexpr auto mp(A &&a, B &&b) { return make_pair(forward<A>(a), forward<B>(b)); }template <class... T> constexpr auto mt(T&&... x) { return make_tuple(forward<T>(x)...); }template <class Int> auto constexpr inf_ = numeric_limits<Int>::max()/2-1;auto constexpr INF32 = inf_<int32_t>;auto constexpr INF64 = inf_<int64_t>;auto constexpr INF = inf_<int>;#ifdef LOCAL#include "debug.hpp"#else#define dump(...) (void)(0)#define say(x) (void)(0)#define debug if (0)#endiftemplate <class T, class Comp> struct pque : priority_queue<T, vector<T>, Comp> { vector<T> &data() { return this->c; } void clear() { this->c.clear(); } };template <class T> using pque_max = pque<T, less<T>>;template <class T> using pque_min = pque<T, greater<T>>;template <class T, class = typename T::iterator, enable_if_t<!is_same<T, string>::value, int> = 0>ostream& operator<<(ostream& os, T const& a) { bool f = true; for (auto const& x : a) os << (f ? "" : " ") << x, f = false; return os; }template <class T, size_t N, enable_if_t<!is_same<T, char>::value, int> = 0>ostream& operator<<(ostream& os, const T (&a)[N]) { bool f = true; for (auto const& x : a) os << (f ? "" : " ") << x, f = false; return os; }template <class T, class = decltype(begin(declval<T&>())), class = typename enable_if<!is_same<T, string>::value>::type>istream& operator>>(istream& is, T &a) { for (auto& x : a) is >> x; return is; }template <class T, class S> ostream& operator<<(ostream& os, pair<T, S> const& p) { return os << p.first << " " << p.second; }template <class T, class S> istream& operator>>(istream& is, pair<T, S>& p) { return is >> p.first >> p.second; }struct IOSetup { IOSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } iosetup;template <class F> struct FixPoint : private F {constexpr FixPoint(F&& f) : F(forward<F>(f)) {}template <class... T> constexpr auto operator()(T&&... x) const { return F::operator()(*this, forward<T>(x)...); }};struct MakeFixPoint { template <class F> constexpr auto operator|(F&& f) const { return FixPoint<F>(forward<F>(f)); } };#define MFP MakeFixPoint()|#define def(name, ...) auto name = MFP [&](auto &&name, __VA_ARGS__)template <class T, size_t d> struct vec_impl {using type = vector<typename vec_impl<T, d-1>::type>;template <class... U> static type make_v(size_t n, U&&... x) { return type(n, vec_impl<T, d-1>::make_v(forward<U>(x)...)); }};template <class T> struct vec_impl<T, 0> { using type = T; static type make_v(T const& x = {}) { return x; } };template <class T, size_t d = 1> using vec = typename vec_impl<T, d>::type;template <class T, size_t d = 1, class... Args> auto make_v(Args&&... args) { return vec_impl<T, d>::make_v(forward<Args>(args)...); }template <class T> void quit(T const& x) { cout << x << endl; exit(0); }template <class T, class U> constexpr bool chmin(T& x, U const& y) { if (x > (T)y) { x = (T)y; return true; } return false; }template <class T, class U> constexpr bool chmax(T& x, U const& y) { if (x < (T)y) { x = (T)y; return true; } return false; }template <class It> constexpr auto sumof(It b, It e) { return accumulate(b, e, typename iterator_traits<It>::value_type{}); }template <class T> int sz(T const& x) { return x.size(); }template <class C, class T> int lbd(C const& v, T const& x) { return lower_bound(begin(v), end(v), x)-begin(v); }template <class C, class T> int ubd(C const& v, T const& x) { return upper_bound(begin(v), end(v), x)-begin(v); }constexpr int64_t mod(int64_t x, int64_t m) { assert(m > 0); return (x %= m) < 0 ? x+m : x; }constexpr int64_t div_floor(int64_t x, int64_t y) { assert(y != 0); return x/y - ((x^y) < 0 and x%y); }constexpr int64_t div_ceil(int64_t x, int64_t y) { assert(y != 0); return x/y + ((x^y) > 0 and x%y); }constexpr int dx[] = { 1, 0, -1, 0, 1, -1, -1, 1 };constexpr int dy[] = { 0, 1, 0, -1, 1, 1, -1, -1 };constexpr int popcnt(ll x) { return __builtin_popcountll(x); }mt19937_64 seed_{random_device{}()};template <class Int> Int rand(Int a, Int b) { return uniform_int_distribution<Int>(a, b)(seed_); }i64 irand(i64 a, i64 b) { return rand<i64>(a, b); } // [a, b]u64 urand(u64 a, u64 b) { return rand<u64>(a, b); } //template <class It> void shuffle(It l, It r) { shuffle(l, r, seed_); }template <class T> vector<T> &operator--(vector<T> &v) { for (T &x : v) --x; return v; }template <class T> vector<T> &operator++(vector<T> &v) { for (T &x : v) ++x; return v; }// <<<// >>> modinttemplate <uint32_t md>class modint {static_assert(md < (1u<<31), "");using M = modint;using i64 = int64_t;uint32_t x;public:static constexpr uint32_t mod = md;constexpr modint(i64 x = 0) : x((x%=md) < 0 ? x+md : x) { }constexpr i64 val() const { return x; }constexpr explicit operator i64() const { return x; }constexpr bool operator==(M r) const { return x == r.x; }constexpr bool operator!=(M r) const { return x != r.x; }constexpr M operator+() const { return *this; }constexpr M operator-() const { return M()-*this; }constexpr M& operator+=(M r) { x += r.x; x = (x < md ? x : x-md); return *this; }constexpr M& operator-=(M r) { x += md-r.x; x = (x < md ? x : x-md); return *this; }constexpr M& operator*=(M r) { x = (uint64_t(x)*r.x)%md; return *this; }constexpr M& operator/=(M r) { return *this *= r.inv(); }constexpr M operator+(M r) const { return M(*this) += r; }constexpr M operator-(M r) const { return M(*this) -= r; }constexpr M operator*(M r) const { return M(*this) *= r; }constexpr M operator/(M r) const { return M(*this) /= r; }friend constexpr M operator+(i64 x, M y) { return M(x)+y; }friend constexpr M operator-(i64 x, M y) { return M(x)-y; }friend constexpr M operator*(i64 x, M y) { return M(x)*y; }friend constexpr M operator/(i64 x, M y) { return M(x)/y; }constexpr M inv() const { assert(x > 0); return pow(md-2); }constexpr M pow(i64 n) const {assert(not (x == 0 and n == 0));if (n < 0) return inv().pow(-n);M v = *this, r = 1;for (; n > 0; n >>= 1, v *= v) if (n&1) r *= v;return r;}#ifdef LOCALfriend string to_s(M r) { return to_s(r.val(), mod); }#endiffriend ostream& operator<<(ostream& os, M r) { return os << r.val(); }friend istream& operator>>(istream& is, M &r) { i64 x; is >> x; r = x; return is; }};// <<<constexpr int64_t MOD = 998244353;//constexpr int64_t MOD = 1e9+7;using mint = modint<MOD>;mint sign(int n) { return n & 1 ? -1 : +1; }// >>> mod tabletemplate <class mint> struct ModTable {vector<mint> fact, finv;void calc(int n) {int old = fact.size();if (n < old) return;n += 1000;fact.resize(n+1);finv.resize(n+1);if (old == 0) {fact[0] = fact[1] = finv[0] = finv[1] = 1;old = 2;}for (auto i = old; i <= n; i++) fact[i] = fact[i-1] * i;finv[n] = mint(1) / fact[n];for (auto i = n-1; i >= old; i--) finv[i] = finv[i+1] * (i+1);}};ModTable<mint> mod_tab;mint fact(int n) {assert(0 <= n);return mod_tab.calc(n), mod_tab.fact[n];}mint finv(int n) {assert(0 <= n);return mod_tab.calc(n), mod_tab.finv[n];}mint comb(int n, int k) {if (n < 0 || k < 0 || n < k) return 0;mod_tab.calc(n);return mod_tab.fact[n] * mod_tab.finv[k] * mod_tab.finv[n-k];}mint perm(int n, int k) {assert(k >= 0); assert(n >= k);mod_tab.calc(n);return mod_tab.fact[n] * mod_tab.finv[n-k];}// <<<// >>> FPStemplate <class NTT>struct FormalPowerSeries : NTT, vector<typename NTT::modint> {using mint = typename NTT::modint;using NTT::conv;using vector<mint>::vector; // inherit constructorsusing FPS = FormalPowerSeries;FormalPowerSeries() : vector<mint>() {}FormalPowerSeries(vector<mint> const& v) : vector<mint>(v) {}FormalPowerSeries(mint const& x) : vector<mint>({x}) {}void shrink() { while (this->size() and this->back() == 0) this->pop_back(); }mint get(int i) const {assert(i >= 0);if (i < (int)this->size()) return (*this)[i];else return 0;}mint &set(int i, mint x) {assert(i >= 0);if (i >= (int)this->size()) this->resize(i+1);return (*this)[i] = x;}bool operator==(FPS const& r) const {const int n = min(this->size(), r.size());rep (i, n) {if ((*this)[i] != r[i]) return false;}for (int i = n; i < (int)this->size(); ++i) {if ((*this)[i] != mint(0)) return false;}for (int i = n; i < (int)r.size(); ++i) {if (r[i] != mint(0)) return false;}return true;}bool operator!=(FPS const& r) const { return !((*this) == r); }FPS operator+(FPS const& r) const { return FPS(*this) += r; }FPS operator-(FPS const& r) const { return FPS(*this) -= r; }FPS& operator+=(FPS const& r) {if (r.size() > this->size()) this->resize(r.size());rep (i, r.size()) (*this)[i] += r[i];return *this;}FPS& operator-=(FPS const& r) {if (r.size() > this->size()) this->resize(r.size());rep (i, r.size()) (*this)[i] -= r[i];return *this;}FPS operator*(FPS const& r) const {if (this->empty() || r.empty()) return {};return conv(*this, r);}FPS& operator*=(FPS const& r) { return *this = *this * r; }friend FPS operator+(mint const& x, FPS const& f) { return FPS{x}+f; }friend FPS operator-(mint const& x, FPS const& f) { return FPS{x}-f; }friend FPS operator*(mint const& x, FPS const& f) { return FPS{x}*f; }friend FPS operator+(FPS const& f, mint const& x) { return f+FPS{x}; }friend FPS operator-(FPS const& f, mint const& x) { return f-FPS{x}; }friend FPS operator*(FPS const& f, mint const& x) { return f*FPS{x}; }FPS take(int sz) const {FPS ret(this->begin(), this->begin() + min<int>(this->size(), sz));ret.resize(sz);return ret;}FPS inv(int sz = -1) const {assert(this->size()); assert((*this)[0] != mint(0));if (sz < 0) sz = this->size();FPS ret = { mint(1)/(*this)[0] };for (int i = 1; i < sz; i <<= 1) {ret = ret + ret - ret*ret*take(i<<1);ret.resize(i<<1);}ret.resize(sz);return ret;}FPS diff() const {FPS ret(max<int>(0, this->size()-1));rep (i, ret.size()) ret[i] = (*this)[i+1]*mint(i+1);return ret;}FPS integral() const {FPS ret(this->size()+1);ret[0] = 0;rep (i, this->size()) ret[i+1] = (*this)[i]/mint(i+1);return ret;}FPS log(int sz = -1) const {assert(this->size()); assert((*this)[0] == mint(1));if (sz < 0) sz = this->size();return (diff()*inv(sz)).take(sz-1).integral();}// FPS log(int sz = -1) const {// assert(this->size()); assert((*this)[0] == mint(1));// if (sz < 0) sz = this->size();// auto ret = diff()*inv(sz);// ret.resize(sz);// for (int i = sz-1; i > 0; --i) ret[i] = ret[i-1]/mint(i);// ret[0] = 0;// return ret;// }FPS exp(int sz = -1) const {FPS ret = {mint(1)};if (this->empty()) return ret;assert((*this)[0] == mint(0));if (sz < 0) sz = this->size();for (int i = 1; i < sz; i <<= 1) {ret *= take(i<<1) + mint(1) - ret.log(i<<1);ret.resize(i<<1);}ret.resize(sz);return ret;}FPS pow(int64_t k, int sz = -1) const {if (sz < 0) sz = this->size();int deg = 0;while (deg < sz && (*this).get(deg) == mint(0)) ++deg;assert(k >= 0 || deg == 0);auto c = mint(1)/(*this).get(deg);FPS ret(sz-deg);rep (i, sz-deg) ret[i] = (*this).get(deg+i)*c;ret = (ret.log()*k).exp() * (*this).get(deg).pow(k);ret.resize(sz);for (int i = sz-1; i >= 0; --i) {int j = i-deg*k;ret[i] = (j >= 0 ? ret[j] : mint(0));}return ret;}mint eval(mint x) const {mint p = 1, ret = 0;rep (i, this->size()) {ret += (*this)[i] * p;p *= x;}return ret;}};// <<<// >>> NTTtemplate <class ModInt, int64_t g>struct NTT {using modint = ModInt;static constexpr int64_t mod = ModInt::mod, gen = g, max_lg = __builtin_ctzll(mod-1);// mod:prime, g:primitive rootstatic_assert(mod > 0 && g > 0 && max_lg > 0, "");using arr_t = array<ModInt, max_lg+1>;static arr_t ws, iws;static void init() {static bool built = false;if (built) return;for (int i = 0; i <= max_lg; i++) {ws[i] = -ModInt(g).pow((mod-1)>>(i+2));iws[i] = ModInt(1)/ws[i];}built = true;}static void ntt(ModInt a[], int lg) {for (int b = lg-1; b >= 0; b--) {ModInt w = 1;for (int i = 0, k = 0; i < (1<<lg); i += 1<<(b+1)) {for (int j = i; j < (i|(1<<b)); j++) {const int k = j|(1<<b);const auto x = a[j], y = a[k];a[j] = x + y*w;a[k] = x - y*w;}w *= ws[__builtin_ctz(++k)];}}// bit_reverse(a, 1<<lg);}static void intt(ModInt a[], int lg) {// bit_reverse(a, 1<<lg);for (int b = 0; b < lg; b++) {ModInt w = 1;for (int i = 0, k = 0; i < (1<<lg); i += 1<<(b+1)) {for (int j = i; j < (i|(1<<b)); j++) {const int k = j|(1<<b);const auto x = a[j], y = a[k];a[j] = x + y;a[k] = w*(x - y);}w *= iws[__builtin_ctz(++k)];}}}template <class T>static vector<ModInt> conv(vector<T> const& a, vector<T> const& b) {if (a.empty() || b.empty()) return {};init();const int s = a.size() + b.size() - 1, lg = __lg(2*s-1);assert(lg <= max_lg);vector<ModInt> aa(1<<lg);rep (i, a.size()) aa[i] = (int64_t)a[i];ntt(aa.data(), lg);vector<ModInt> bb(1<<lg);rep (i, b.size()) bb[i] = (int64_t)b[i];ntt(bb.data(), lg);const auto x = ModInt(1)/ModInt(1<<lg);rep (i, 1<<lg) aa[i] *= bb[i]*x;intt(aa.data(), lg); aa.resize(s);return aa;}template <class T>static vector<ModInt> conv(vector<T> const& a) {if (a.empty()) return {};init();const int s = a.size()*2 - 1, lg = __lg(2*s-1);assert(lg <= max_lg);vector<ModInt> aa(1<<lg);rep (i, a.size()) aa[i] = (int64_t)a[i];ntt(aa.data(), lg);const auto x = ModInt(1)/ModInt(1<<lg);rep (i, 1<<lg) aa[i] *= aa[i]*x;intt(aa.data(), lg); aa.resize(s);return aa;}};template <class ModInt, int64_t g>typename NTT<ModInt, g>::arr_t NTT<ModInt, g>::ws;template <class ModInt, int64_t g>typename NTT<ModInt, g>::arr_t NTT<ModInt, g>::iws;// <<<using ntt = NTT<mint, 3>;using FPS = FormalPowerSeries<ntt>;// >>> lazy segment treetemplate <class Handler> struct LazySegtree : Handler {using Value = typename Handler::Value;using Action = typename Handler::Action;using Handler::unit_value; // () -> Valueusing Handler::unit_action; // () -> Actionusing Handler::merge; // (Value, Value) -> Valueusing Handler::compose; // (Action, Action) -> Actionusing Handler::act; // (Action, Value) -> Valuevector<Value> v;vector<Action> a;int n, lg;LazySegtree() {}template <class... T> LazySegtree(T&&... x) { init(forward<T>(x)...); }template <class F, class = decltype(declval<F>()(0))>void init(int n, F gen) {assert(n >= 0);this->n = n;this->lg = (n == 0 ? 0 : __lg(2*n-1));v.resize(2*n);a.assign(n, unit_action());for (int i = 0; i < n; i++) v[n+i] = gen(i);for (int i = n-1; i >= 1; i--) v[i] = merge(v[i<<1], v[i<<1|1]);}// void init(int n) { init(n, [&](int) { return unit_value(); }); }void init(int n, Value const& x) { init(n, [&](int) { return x; }); }void init(vector<Value> const& v) { init(v.size(), [&](int i) { return v[i]; }); }int size() const { return n; }void act_at(Action const& x, int i) {if (i < n) a[i] = compose(x, a[i]);v[i] = act(x, v[i]);}void flush(int k) {if (n <= k || a[k] == unit_action()) return;act_at(a[k], k<<1);act_at(a[k], k<<1|1);a[k] = unit_action();}void flush(int l, int r) {for (int p = lg; p; --p) flush(l >> p), flush((r - 1) >> p);}Value get(int l, int r) {assert(0 <= l); assert(l <= r); assert(r <= n);l += n, r += n;flush(l, r);Value x = unit_value(), y = unit_value();for ( ; l < r; l >>= 1, r >>= 1) {if (l & 1) x = merge(x, v[l++]);if (r & 1) y = merge(v[--r], y);}return merge(x, y);}void build(int i) {i >>= __builtin_ctz(i);while (i >>= 1) v[i] = merge(v[i<<1], v[i<<1|1]);}void apply(int l, int r, Action const& x) {assert(0 <= l); assert(l <= r); assert(r <= n);l += n, r += n;flush(l, r);for (int a = l, b = r; a < b; a >>= 1, b >>= 1) {if (a & 1) act_at(x, a++);if (b & 1) act_at(x, --b);}build(l); build(r);}Value operator[](int i) const { return get(i); }Value get(int i) const {assert(0 <= i); assert(i < n);Value x = v[i += n];while (i >>= 1) x = act(a[i], x);return x;}void set(int i, Value const& x) {assert(0 <= i); assert(i < n);i += n;for (int p = lg; p; --p) flush(i >> p);v[i] = x;while (i >>= 1) v[i] = merge(v[i<<1], v[i<<1|1]);}template <class F> int max_right(int l, F f) {assert(0 <= l); assert(l <= size());assert(f(unit_value()));l += n;const int r = size() << 1;for (int p = lg; p; p--) flush(l >> p);Value x = unit_value();while (true) {if (l == r) return size();int k = __builtin_ctz(l | 1 << __lg(r - l));auto y = merge(x, v[l >> k]);if (not f(y)) { l >>= k; break; }x = y, l += 1 << k;}while (l < size()) {flush(l);auto y = merge(x, v[l <<= 1]);if (f(y)) x = y, l++;}return l - size();}template <class F> int min_left(int r, F f) {assert(0 <= r); assert(r <= size());assert(f(unit_value()));r += n;const int l = size();for (int p = lg; p; p--) flush((r - 1) >> p);Value x = unit_value();while (true) {if (l == r) return 0;int k = __builtin_ctz(r | 1 << __lg(r - l));auto y = merge(v[(r >> k) - 1], x);if (not f(y)) { r >>= k; --r; break; }x = y, r -= 1 << k;}while (r < size()) {flush(r);r = r << 1 | 1;auto y = merge(v[r], x);if (f(y)) x = y, r--;}return r + 1 - size();}vector<Value> dat() const {vector<Value> ret(size());for (int i = 0; i < size(); i++) ret[i] = get(i);return ret;}};template <class _Value, class _Action> struct Handler {using Value = _Value;using Action = _Action;constexpr static Value unit_value() { return {}; }constexpr static Action unit_action() { return {}; }constexpr static Value merge(Value const& x, Value const& y) { return x * y; }constexpr static Action compose(Action const& x, Action const& y) { return x * y; }constexpr static Value act(Action const& x, Value const& y) { return x(y); }};// <<<// >>> SumSetstruct Value {using T = FPS;T sum;int len;Value() : sum(FPS {}), len(0) {}Value(T val, int len = 1) : sum(val), len(len) {}Value operator*(Value const& rhs) const {return { sum + rhs.sum, len + rhs.len };}};#ifdef LOCALstring to_s(Value const& x) { return to_s(x.sum); }#endifstruct Action { // setusing T = optional<FPS>;T a;Action(FPS f) : a(f) {}Action(T a = {}) : a(a) {}Action operator*(Action const& rhs) const {if (a) {return a;} else {return rhs;}}Value operator()(Value const& val) const {if (a == Action().a) {return val;} else {return { *a * mint(val.len), val.len };}}bool operator==(Action const& rhs) const {return a == rhs.a;}};#ifdef LOCALstring to_s(Action const& a) { return to_s(a.a); }#endifusing SumSet = Handler<Value, Action>;// <<<int32_t main() {int n; cin >> n;vector<int> a(n); cin >> a;auto gen = [&](mint x) {return FPS { 0, x }.exp(5);};LazySegtree<SumSet> seg(n, [&](int i) { return gen(a[i]); });auto calc = [&](int x, int y, int z) {if (x > y) swap(x, y);FPS f;if (x < z and z < y) {int l = x, r = y+1;f = seg.get(l, r).sum;} else {int l = x+1, r = y;f = seg.get(0, n).sum - seg.get(l, r).sum;}mint cnt = f[0];mint sum = f[1];mint ave = sum / cnt;f *= gen(-ave);f.resize(5);rep (i, f.size()) {f[i] *= fact(i) / cnt;}return f;};int q; cin >> q;while (q--) {int t, x, y, z; cin >> t >> x >> y >> z; --x, --y, --z;if (x > y) swap(x, y);if (t == 0) {mint B; cin >> B;auto f = gen(B);if (x < z and z < y) {seg.apply(x, y+1, f);} else {seg.apply(0, x+1, f);seg.apply(y, n, f);}} else {auto f = calc(x, y, z);cout << f[t] << '\n';}}}