This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/queue_operate_all_composite"
#include "template/template.hpp"
#include "math/modint.hpp"
#include "structure/slide-window-aggregation.hpp"
#include "math/linear_function.hpp"
using mint = modint998244353;
using LF = LinearFunction<mint>;
// f_r(f_l)
LF op(LF lf, LF rf) {
return rf.composite(lf);
}
LF e() {
return LF::Mul_Identity();
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
FoldableDeque<LF,op,e> fdq;
int Q; cin >> Q;
for(int i=0; i<Q; i++) {
int op; cin >> op;
if (op == 0) {
int a,b; cin >> a >> b;
fdq.push_back({mint(a), mint(b)});
}
else if (op == 1) {
fdq.pop_front();
}
else if (op == 2) {
int x; cin >> x;
LF all_prod = fdq.all_prod();
cout << all_prod(x).val() << endl;
}
}
return 0;
}#line 1 "test/verify/yosupo-queue-operate-all-composite.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/queue_operate_all_composite"
#line 1 "template/template.hpp"
// https://harui-i.github.io/library/template/template.hpp.html
#include <iostream>
#include <cassert>
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, const T& b) {if (a<b) {a=b; return true;} return false;}
template<class T> inline bool chmin(T& a, const T& b) {if (b<a) {a=b; return true;} return false;}
const int INTINF = 1000001000;
const int INTMAX = 2147483647;
const ll LLMAX = 9223372036854775807;
const ll LLINF = 1000000000000000000;
#line 1 "math/modint.hpp"
// https://harui-i.github.io/library/math/modint.hpp.html
#line 1 "math/external_gcd.hpp"
// https://harui-i.github.io/library/math/external_gcd.hpp.html
#include <tuple>
// g,x,y
template<typename T>
constexpr std::tuple<T, T, T> extendedGCD(T a, T b) {
T x0 = 1, y0 = 0, x1 = 0, y1 = 1;
while (b != 0) {
T q = a / b;
T r = a % b;
a = b;
b = r;
T xTemp = x0 - q * x1;
x0 = x1;
x1 = xTemp;
T yTemp = y0 - q * y1;
y0 = y1;
y1 = yTemp;
}
return {a, x0, y0};
}
#line 6 "math/modint.hpp"
#include <type_traits>
#line 8 "math/modint.hpp"
long long mod_pow_ll(long long x, long long n, long long mod) {
long long ret = 1;
while (n > 0) {
if (n & 1) ret = (__int128)ret * x % mod;
x = (__int128)x * x % mod;
n >>= 1;
}
return ret;
}
// x^2 = a (mod p) となる x を返す。存在しない場合は -1。
// p は素数であることを仮定する。
long long mod_sqrt(long long a, long long p) {
a %= p;
if (a < 0) a += p;
if (a == 0) return 0;
if (p == 2) return a;
if (mod_pow_ll(a, (p - 1) / 2, p) != 1) return -1;
if (p % 4 == 3) return mod_pow_ll(a, (p + 1) / 4, p);
long long q = p - 1;
int s = 0;
while ((q & 1) == 0) {
q >>= 1;
s++;
}
long long z = 2;
while (mod_pow_ll(z, (p - 1) / 2, p) != p - 1) z++;
long long c = mod_pow_ll(z, q, p);
long long x = mod_pow_ll(a, (q + 1) / 2, p);
long long t = mod_pow_ll(a, q, p);
int m = s;
while (t != 1) {
int i = 1;
long long tt = (__int128)t * t % p;
while (tt != 1) {
tt = (__int128)tt * tt % p;
i++;
}
long long b = c;
for (int j = 0; j < m - i - 1; j++) b = (__int128)b * b % p;
x = (__int128)x * b % p;
c = (__int128)b * b % p;
t = (__int128)t * c % p;
m = i;
}
return x;
}
template<int MOD, typename T = int>
struct static_modint {
T value;
constexpr explicit static_modint() : value(0) {}
static constexpr int mod() { return MOD; }
constexpr static_modint(long long v) {
if constexpr (std::is_same<T, double>::value) {
value = double(v);
}
else {
value = int(((v % MOD) + MOD) % MOD);
}
}
constexpr static_modint& operator+=(const static_modint& other) {
if constexpr (std::is_same<T, double>::value) {
value += other.value;
}
else {
if ((value += other.value) >= MOD) value -= MOD;
}
return *this;
}
constexpr static_modint& operator-=(const static_modint& other) {
if constexpr (std::is_same<T, double>::value) {
value -= other.value;
}
else {
if ((value -= other.value) < 0) value += MOD;
}
return *this;
}
constexpr static_modint& operator*=(const static_modint& other) {
if constexpr (std::is_same<T, double>::value) {
value *= other.value;
}
else {
value = int((long long)value * other.value % MOD);
}
return *this;
}
constexpr static_modint operator+(const static_modint& other) const {
return static_modint(*this) += other;
}
constexpr static_modint operator-(const static_modint& other) const {
return static_modint(*this) -= other;
}
constexpr static_modint operator-() const {
return static_modint(0) - *this;
}
constexpr static_modint operator*(const static_modint& other) const {
return static_modint(*this) *= other;
}
constexpr static_modint pow(long long exp) const {
static_modint base = *this, res = static_modint(1);
while (exp > 0) {
if (exp & 1) res *= base;
base *= base;
exp >>= 1;
}
return res;
}
long long sqrt_val() const {
return mod_sqrt(value, MOD);
}
static_modint sqrt() const {
long long ret = sqrt_val();
assert(ret != -1);
return static_modint(ret);
}
constexpr static_modint inv() const {
if constexpr (std::is_same<T, double>::value) {
static_modint ret;
ret.value = double(1.0) / value;
return ret;
}
else {
int g, x, y;
std::tie(g, x, y) = extendedGCD(value, MOD);
assert(g == 1);
if (x < 0) x += MOD;
return x;
}
}
constexpr static_modint& operator/=(const static_modint& other) {
return *this *= other.inv();
}
constexpr static_modint operator/(const static_modint& other) const {
return static_modint(*this) /= other;
}
constexpr bool operator!=(const static_modint& other) const {
return val() != other.val();
}
constexpr bool operator==(const static_modint& other) const {
return val() == other.val();
}
T val() const {
if constexpr (std::is_same<T, double>::value) {
return double(value);
}
else return this->value;
}
friend std::ostream& operator<<(std::ostream& os, const static_modint& mi) {
return os << mi.value;
}
friend std::istream& operator>>(std::istream& is, static_modint& mi) {
long long x;
is >> x;
mi = static_modint(x);
return is;
}
};
template <int mod>
using modint = static_modint<mod>;
using doublemodint = static_modint<59, double>;
using modint998244353 = modint<998244353>;
using modint1000000007 = modint<1000000007>;
#line 1 "structure/slide-window-aggregation.hpp"
// https://harui-i.github.io/library/structure/slide-window-aggregation.hpp.html
#include <vector>
#include <algorithm>
template <class S, S (*op)(S, S), S (*e)()>
struct FoldableDeque {
struct Node {
S val;
S prod;
};
std::vector<Node> front, back;
FoldableDeque() : front(), back() {}
size_t size() const { return front.size() + back.size(); }
bool empty() const { return front.size() + back.size() == 0; }
// nyaanさんのをパクっており
void rebalance() {
int n = front.size() + back.size();
int s0 = n / 2 + (front.empty() ? n % 2 : 0);
// frontにs0個
// backにN - s0個入れる
vector<Node> a{front};
std::reverse(begin(a), end(a));
std::copy(begin(back), end(back), back_inserter(a));
front.clear(), back.clear();
for (int i = s0 - 1; i >= 0; i--) push_front(a[i].val);
for (int i = s0; i < n; i++) push_back(a[i].val);
return;
}
S all_prod() const {
if (front.empty() && back.empty() ) return e();
if (front.empty()) {
return back.back().prod;
}
else if (back.empty()) {
return front.back().prod;
}
else return op(front.back().prod, back.back().prod) ;
}
void push_back(const S& x) {
if (back.empty()) {
back.push_back({x, x});
}
else {
// 順序怪しいかも
back.push_back({x, op(back.back().prod, x) });
}
}
void push_front(const S& x) {
if (front.empty()) {
front.push_back({x, x});
}
else {
// 順序怪しいかも
front.push_back({x, op(x, front.back().prod) });
}
}
void pop_back() {
assert(size() > 0);
if (back.empty()) rebalance();
back.pop_back();
}
void pop_front() {
assert(size() > 0);
if (front.empty()) rebalance();
front.pop_back();
}
};
#line 1 "math/linear_function.hpp"
// https://harui-i.github.io/library/math/linear_function.hpp.html
template <typename T>
struct LinearFunction {
T a, b;
LinearFunction() : a{0}, b(0) {}
LinearFunction(T _a, T _b) : a(_a), b(_b) {}
static LinearFunction Add_Identity() {
return LinearFunction(T(0), T(0));
}
static LinearFunction Mul_Identity(){
return LinearFunction(T(1), T(0));
}
// f(g())
LinearFunction composite(LinearFunction& g) const {
return LinearFunction(a * g.a, a * g.b + b);
}
LinearFunction operator+(const LinearFunction& rhs) const {
return LinearFunction(a + rhs.a, b + rhs.b);
}
// rhs(f())
LinearFunction operator*(const LinearFunction& rhs) const {
LinearFunction f = *this;
return rhs.composite(f);
}
T operator()(T x) const {
return a * x + b;
}
};
#line 7 "test/verify/yosupo-queue-operate-all-composite.test.cpp"
using mint = modint998244353;
using LF = LinearFunction<mint>;
// f_r(f_l)
LF op(LF lf, LF rf) {
return rf.composite(lf);
}
LF e() {
return LF::Mul_Identity();
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
FoldableDeque<LF,op,e> fdq;
int Q; cin >> Q;
for(int i=0; i<Q; i++) {
int op; cin >> op;
if (op == 0) {
int a,b; cin >> a >> b;
fdq.push_back({mint(a), mint(b)});
}
else if (op == 1) {
fdq.pop_front();
}
else if (op == 2) {
int x; cin >> x;
LF all_prod = fdq.all_prod();
cout << all_prod(x).val() << endl;
}
}
return 0;
}