Falling Multiset#12415
Problem Author: | turneja |
Prepared by: | turneja |
Edited by: | turneja |
Solution
We will use a square root decomposition based approach to efficiently solve this problem.
For an item inserted at time with weight and value , define A = v \cdot w! and t = s + w - 1. Then the contribution of that item at time is \mathrm{contrib}(j)= \begin{cases} 0, & j < s,\\[1ex] A \cdot \dfrac{1}{(t-j)!}, & s \le j \le t,\\[2ex] A, & j > t. \end{cases}
We will select a value and divide the time units in groups of size . For each group, we will add each item in that group to a temporary buffer and naively calculate its contribution for each time unit in that group.
After processing the entire group, we will clear all items in the temporary buffer and construct a polynomial consisting of all active items and convolve it with the inverse factorial array using FFT/NTT to get the contribution for each time unit in the next group.
There are a few nuances to keep in mind of here, such as if at the time of convolution an active item's expiry time (the time at which its value becomes constant and doesn't change anymore) falls within the next group we should move it to the naive contribution buffer instead, or that the expired items should be handled separately. The details are left in the implementation code.
By selecting B = \sqrt{n \log n} we can achieve a time complexity of \mathcal{O}(n \sqrt{n \log n}).
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define endl "\n"
#define ll long long
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr);
const int N = 1e5 + 5;
const ll M = 998244353;
const int SQ = 2500;
ll inv[N];
ll fact[N];
ll factinv[N];
ll modPow(ll a, ll y) {
ll res = 1;
while (y > 0) {
if (y % 2 != 0) {
res = res * a % M;
}
y /= 2;
a = a * a % M;
}
return res;
}
void ntt(vector<ll> &a, int typ) {
int n = a.size(), L = 31 - __builtin_clz(n);
vector<int> rev(n);
for (int i = 0; i < n; i++) {
rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
}
for (int i = 0; i < n; i++) {
if (i < rev[i]) {
swap(a[i], a[rev[i]]);
}
}
int g = modPow(3, (M - 1) / n);
vector<ll> wn(n), w(n);
wn[0] = 1;
for (int i = 1; i < n; i++) {
wn[i] = wn[i - 1] * g % M;
}
for (int k = 1; k < n; k *= 2) {
for (int i = 0, t = n / (2 * k); i < k; i++) {
w[i] = wn[i * t];
}
for (int i = 0; i < n; i += 2 * k) {
for (int j = 0; j < k; j++) {
ll x = a[i + j], y = a[i + j + k] * w[j] % M;
a[i + j] = x + y - (x + y >= M ? M : 0);
a[i + j + k] = x - y + (x - y < 0 ? M : 0);
}
}
}
if (!typ) {
reverse(a.begin() + 1, a.end());
ll inv_n = modPow(n, M - 2);
for (int i = 0; i < n; i++) {
a[i] = a[i] * inv_n % M;
}
}
}
vector<ll> convMod(vector<ll> a, vector<ll> b) {
int m = a.size() + b.size() - 1;
if (m == 1) {
return {a[0] * b[0] % M};
}
int B = 32 - __builtin_clz(m - 1);
int n = 1 << B;
a.resize(n), b.resize(n);
ntt(a, 1), ntt(b, 1);
for (int i = 0; i < n; i++) {
a[i] = a[i] * b[i] % M;
}
ntt(a, 0);
a.resize(m);
return a;
}
int main() {
IOS;
fact[0] = 1, factinv[0] = 1;
for (int i = 1; i < N; i++) {
inv[i] = (i == 1 ? 1 : M - (M / i) * inv[M % i] % M);
fact[i] = fact[i - 1] * i % M;
factinv[i] = factinv[i - 1] * inv[i] % M;
}
int n;
cin >> n;
vector<pair<int, int>> items(n);
for (int i = 0; i < n; i++) {
int w, v;
cin >> w >> v;
items[i] = {w, v};
}
vector<tuple<int, int, int>> current_items;
vector<tuple<int, int, int>> buf;
vector<ll> ans(n, 0);
vector<ll> add_expired(n, 0);
int nx_upd = SQ;
ll sum_expired = 0;
for (int i = 0; i < n; i++) {
sum_expired = (sum_expired + add_expired[i]) % M;
if (i == nx_upd) {
nx_upd += SQ;
vector<tuple<int, int, int>> nx_items;
for (auto [st, t, val] : current_items) {
if (t < nx_upd) {
for (int j = i; j < min(n, t + 1); j++) {
ans[j] = (ans[j] + val * factinv[t - j]) % M;
}
} else {
nx_items.push_back({st, t, val});
}
}
for (auto [st, t, val] : buf) {
if (t < nx_upd) {
for (int j = i; j < min(n, t + 1); j++) {
ans[j] = (ans[j] + val * factinv[t - j]) % M;
}
} else {
nx_items.push_back({st, t, val});
}
}
current_items = nx_items;
if (current_items.size()) {
int mx = 0;
for (auto [st, t, val] : current_items) {
int base_time = t - i;
mx = max(mx, base_time);
}
vector<ll> a(mx + 1, 0), b(mx + 1, 0);
for (auto [st, t, val] : current_items) {
int base_time = t - i;
a[base_time] = (a[base_time] + val) % M;
}
for (int j = 0; j <= mx; j++) {
b[j] = factinv[mx - j];
}
vector<ll> c = convMod(a, b);
for (int j = mx; j < c.size() && i + j - mx < min(n, nx_upd); j++) {
ans[i + j - mx] = (ans[i + j - mx] + c[j]) % M;
}
}
buf.clear();
}
auto [w, v] = items[i];
ll val = v * fact[w] % M;
int t = i + w - 1;
if (t < n - 1) {
add_expired[t + 1] = (add_expired[t + 1] + val) % M;
}
if (t < nx_upd) {
for (int j = i; j < min(n, t + 1); j++) {
ans[j] = (ans[j] + val * factinv[t - j]) % M;
}
} else {
buf.push_back({i, t, val});
}
ll buf_contrib = 0;
for (auto [st, t, val] : buf) {
buf_contrib = (buf_contrib + val * factinv[t - i]) % M;
}
cout << (ans[i] + buf_contrib + sum_expired) % M << endl;
}
return 0;
}