Skip to Content
CTRL K

Queue Composite

Explicación

Consideremos ff cuando le hemos agregado dos ecuaciones, {a,b},{c,d}\{a, b\}, \{c, d\}.

  1. c(ax+b)+dc(ax + b) + d
  2. acx+bc+dacx + bc + d

A partir de esto, podemos hacer dos observaciones.

  1. En la ecuación expandida, xx simplemente se multiplica por todos sus coeficientes.
  2. Cualquier constante se multiplica por todos los coeficientes futuros.

Podemos calcular todo esto sobre la marcha a medida que procesamos las consultas de “agregar” y “calcular”, pero ¿cómo lidiar con las consultas de “quitar” bajo un módulo?

Manejar las consultas de quitar

Calcularemos inversos modulares para dividir los coeficientes quitados, y restaremos la constante multiplicada por nuestro nuevo coeficiente.

El cuello de botella viene de calcular inversos modulares, así que la complejidad temporal es O(log⁡n)\mathcal{O}(\log n).

Implementación

Complejidad temporal: O(log⁡n)\mathcal{O}(\log n)

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
const ll MOD = 998244353;
 
// source: https://usaco.guide/gold/modular#solution---exponentiation
ll bin_exp(ll x, ll n) {
	assert(n >= 0);
 
	x %= MOD;
 
	ll res = 1;
	while (n > 0) {
		if (n % 2 == 1) { res = res * x % MOD; }
		x = x * x % MOD;
		n /= 2;
	}
	return res;
}
 
int main() {
	int q;
	cin >> q;
 
	ll mult_x = 1;
	ll constant = 0;
	queue<pair<int, int>> f;
	for (int i = 0; i < q; i++) {
		int type;
		cin >> type;
 
		if (type == 0) {
			int a, b;
			cin >> a >> b;
 
			// add to our queue
			f.push({a, b});
 
			// x will gain a factor of a in the final expansion
			mult_x = (mult_x * a) % MOD;
 
			/*
			 * any existing constants will be multiplied by a
			 * and b will be multiplied against all future "a"s
			 */
			constant = ((constant * a) % MOD + b) % MOD;
		} else if (type == 1) {
			pair<int, int> x = f.front();
			f.pop();
 
			// compute modular inverse with exponentiation
			ll inv = bin_exp(x.first, MOD - 2);
 
			mult_x = (mult_x * inv) % MOD;
			constant -= (x.second * mult_x) % MOD;
 
			if (constant < 0) { constant += MOD; }
		} else if (type == 2) {
			int x;
			cin >> x;
 
			cout << ((mult_x * x) + constant) % MOD << endl;
		}
	}
}
Fundamentos