PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Alex Kristev
Tester: Nishank Suresh
Editorialist: Taranpreet Singh
DIFFICULTY
Medium
PREREQUISITES
Dynamic Programming, Number Theoretic Transform
PROBLEM
You are trying to create an array A containing N integers. However, your array-creating-machine has some restrictions. More formally, you are given a constant D, and two arrays B and C, each with M elements, then:
- A_i \le D for all 1 \le i \le N
- A_i \ge A_{i - 1} for all 1 \lt i \le N
- A_{C_j}\cdot B_j \le D for all 1 \le j \le M
Find how many different arrays can you create. Since the answer can be big, print it modulo
998244353.
QUICK EXPLANATION
- Based on restrictions, we can determine the maximum value we can assign for each position.
- This way, we can write a DP defined by state (n, x) denote the number of non-decreasing arrays of length n such that the last element is x. We have transitions \displaystyle DP_{n, x} = \sum_{1 \leq y \leq x} DP_{n-1, y}, and base state DP_{0, 1} = 1. This approach takes O(N*D^2)
- In order to optimize this, we can notice that there can be at most M intervals where the maximum value is the same, so we can group those transitions by some combinatorics, reducing complexity to O(M*D^2)
- The sum of distinct values of D/i is bounded by D*log(D), which reduces the time complexity to O(D^2*log(D))
- By replacing DP transitions with polynomial convolution, the time complexity is reduced to O(D*log^2(D)) which should get accepted with a reasonable constant factor.
EXPLANATION
Let’s say we have a restriction (C_i, B_i) where A_{C_i}*B_i \leq D. This implies A_{C_i} \leq \lfloor D/B_i \rfloor. We also have A_{i-1} \leq A_i, so a restriction affecting position p affects all positions before p as well.
This way, we can compute for each position, the maximum value allowed for that position.
This allows us to write a naive Dynamic Programming approach, where we define state (n, x) to be the number of arrays of first n elements such that A_n = x. Let’s say the maximum value allowed for index p is MX_p. So we can write \displaystyle DP_{n, x} = \sum_{1 \leq y \leq x} DP_{n-1, y}. This solution naviely takes O(N*D^2), and can be sped up to O(N*D) using prefix sums. But we need to improve it a lot.
Observation: Since there are M restrictions, the number of distinct values of MX_p doesn’t exceed M. Now, we can divide all positions in the range [1, N] into M+1 groups.
Let’s say we have A_p = x and A_q = y where p \lt q and x \leq y. What is the number of ways to choose the values for positions in range (p, q) such that array is non-decreasing? Let’s denote A = q-p-1 and V = y-x
Using Stars and Bars, we can find it out to be ^{q-p-1+y-x}C_{y-x}. Hence, we can now process the whole group having the same maximum in the same way. Just adding a restriction with C_i = N and B_i = 1 to avoid handling edge cases for last block.
The DP transitions now become (m, x) denote the number of ways to fill first m groups such that last position in last group has value x. Each group contains a number of people and a next maximum value. DP_{m, x} = \sum_{y \leq x} DP_{m-1, y} * ^{S_m-1+y-x}C_{S_m-1}, where S_m denote the number of position in m-th group.
This approach requires M groups and each group involves O(D^2) transitions, leading to O(M*D^2) solution. This solution can be further optimized by replacing the transition with polynomial multiplication. Let’s say for m-th group, MX_m denote the maximum value. Assuming the coefficient of x^v denote the number of ways such that the last element has value v, then we need to take the whole polynomial modulo x^{MX_m+1}. This would get rid of coefficients of degree \gt MX_m.
Hence, by replacing transitions with NTT, we get the time complexity down to O(M*D*log(D)), which should easily pass the first subtask.
Surprise: Above solution’s time complexity is actually O(D*log^2(D)) and would pass both subtasks.
Why? The convolution needs to happen whenever the maximum of a group changes. The way restrictions are given, the maximum value can only take values of the form D/x for some x, and there are around \sqrt D distinct values of D/x for fixed x. Moreover, the sum of D/x over all such instances would be approximately D*log(D), reducing the bound on overall time complexity to O(D*log^2(D)). Also, we need to compute factorials and inverse factorials to compute C, so we have another O(N) in time complexity.
TIME COMPLEXITY
The time complexity is O(N + \sum D*log^2(D)) per test case.
SOLUTIONS
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define FAST ios_base::sync_with_stdio(false); \
cin.tie(nullptr); \
cout.tie(nullptr)
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vpii = vector<pii>;
using vpll = vector<pll>;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define psum(x) ((x).first + (x).second)
#define ft first
#define sd second
#define cendl cout << endl
#define cyes cout << "YES" << endl
#define cno cout << "NO" << endl
template<int m>
struct modint
{
int x;
modint() :
x(0) {}
modint(long long arg)
{
arg%= m;
if (arg < 0) x = arg + m;
else x = arg;
}
modint& operator+= (const modint& other)
{
x += other.x;
if (x >= m) x -= m;
return *this;
}
modint& operator*= (const modint& other)
{
x = (x * 1ll * other.x) % m;
return *this;
}
modint& operator-= (const modint& other)
{
x+= m - other.x;
if (x >= m) x-= m;
return *this;
}
modint operator+ (const modint& other) const
{
modint tmp = *this;
tmp += other;
return tmp;
}
modint operator- (const modint& other) const
{
modint tmp = *this;
tmp -= other;
return tmp;
}
modint operator* (const modint& other) const
{
modint tmp = *this;
tmp *= other;
return tmp;
}
explicit operator int () const
{
return x;
}
modint& operator++ ()
{
++x;
if (x == m) x = 0;
return *this;
}
modint& operator-- ()
{
if (x == 0) x = m-1;
else --x;
return *this;
}
modint operator++ (int)
{
modint tmp = *this;
++*this;
return tmp;
}
modint operator-- (int)
{
modint tmp = *this;
--*this;
return tmp;
}
bool operator== (const modint& other) const
{
return x == other.x;
}
bool operator!= (const modint& other) const
{
return x != other.x;
}
template<class T>
modint operator^ (T arg) const
{
if (arg == 0) return 1;
if (arg == 1) return x;
auto t = *this ^ (arg >> 1);
t*= t;
if (arg & 1) t*= *this;
return t;
}
modint inv() const // works clearly only when 'm' is prime number
{
return *this ^ (m-2);
}
};
const int MOD = 998244353;
typedef modint<MOD> mint;
std::vector<mint> factorial;
std::vector<mint> invfactorial;
inline mint C(int N, int K)
{
if (N < K || K < 0)
return mint();
return factorial[N] * invfactorial[K] * invfactorial[N-K];
}
inline void SetupFactorial(int sz)
{
++sz;
::factorial.resize(sz);
::invfactorial.resize(sz);
::factorial[0] = 1;
for (int i = 1; i < sz; ++i)
::factorial[i] = ::factorial[i-1] * mint(i);
::invfactorial[sz-1] = ::factorial[sz-1].inv();
for (int i = sz-2; i >= 0; --i)
::invfactorial[i] = ::invfactorial[i+1]*mint(i+1);
}
const int mod = MOD;
const int root = 31;
const int root_1 = 128805723;
const int root_pw = 1<<23;
const mint mroot = mint(root);
const mint mroot_1 = mint(root_1);
void fft (vector<mint>& a, bool invert)
{
int n = (int) a.size();
for (int i=1, j=0; i<n; ++i)
{
int bit = n >> 1;
for (; j >= bit; bit >>= 1)
j -= bit;
j += bit;
if (i < j)
swap (a[i], a[j]);
}
for (int len = 2; len <= n; len <<= 1)
{
mint wlen = invert ? mroot_1 : mroot;
for (int i = len; i < root_pw; i <<= 1)
wlen *= wlen;
for (int i = 0; i < n; i += len)
{
mint w(1);
for (int j = 0; j < len/2; ++j)
{
mint u = a[i+j];
mint v = a[i+j+len/2] * w;
a[i + j] = u + v;
a[i + j + len/2] = u - v;
w *= wlen;
}
}
}
if (invert)
{
mint nrev = mint(n).inv();
for (int i = 0; i < n; ++i)
a[i] *= nrev;
}
}
void multiply (const vector<mint>& a, const vector<mint>& b, size_t sz, size_t ressz, vector<mint>& res)
{
size_t n = 1;
while (n < sz) n <<= 1;
n <<= 1;
vector<mint> fa (a.begin(), a.end()), fb (b.begin(), b.end());
fa.resize(n), fb.resize(n);
for (int i = sz; i < n; ++i)
{
fa[i] = mint();
fb[i] = mint();
}
fft (fa, false), fft (fb, false);
for (size_t i=0; i<n; ++i)
fa[i] *= fb[i];
fft (fa, true);
n = min(n, ressz);
if (res.size() < n)
res.resize (n);
for (size_t i=0; i<n; ++i)
res[i] = fa[i];
}
int a, b, k, n, m, tmp, d;
int solve()
{
cin >> n >> m >> d;
vpii data(m);
for (int i = 0; i < m; ++i)
{
cin >> data[i].ft >> data[i].sd;
data[i].sd = d / data[i].sd;
}
sort(all(data));
if (data[data.size()-1].ft != n)
data.pb({n, d});
vpii dt;
int cur_rest = d+1;
for (int i = data.size()-1; i >= 0; --i)
{
if (data[i].sd < cur_rest)
{
cur_rest = data[i].sd;
dt.pb(data[i]);
}
}
sort(all(dt));
vector<mint> dp (1, mint(1));
vector<mint> dpnw (d+1);
int curid = 0;
int curmax = 1;
for (int id = 0; id < dt.size(); ++id)
{
vector<mint> Cnk (dt[id].sd);
for (int i = 0; i < dt[id].sd; ++i)
Cnk[i] = C(i+dt[id].ft-curid-1, i);
multiply(dp, Cnk, Cnk.size(), Cnk.size(), dp);
curmax = dt[id].sd;
curid = dt[id].ft;
}
mint ans(0);
for (int i = 0; i < dp.size(); ++i)
ans += dp[i];
cout << ans.x << endl;
return 0;
}
int main()
{
FAST;
SetupFactorial(11000004);
int t;
cin >> t;
while(t--)
solve();
return 0;
}
Tester's Solution
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
/**
* Integers modulo p, where p is a prime
* Source: Aeren (modified from tourist?)
* Modmul for 64-bit mod from kactl:ModMulLL
* Works with p < 7.2e18 with x87 80-bit long double, and p < 2^52 ~ 4.5e12 with 64-bit
*/
template<typename T>
struct Z_p{
using Type = typename decay<decltype(T::value)>::type;
static vector<Type> MOD_INV;
constexpr Z_p(): value(){ }
template<typename U> Z_p(const U &x){ value = normalize(x); }
template<typename U> static Type normalize(const U &x){
Type v;
if(-mod() <= x && x < mod()) v = static_cast<Type>(x);
else v = static_cast<Type>(x % mod());
if(v < 0) v += mod();
return v;
}
const Type& operator()() const{ return value; }
template<typename U> explicit operator U() const{ return static_cast<U>(value); }
constexpr static Type mod(){ return T::value; }
Z_p &operator+=(const Z_p &otr){ if((value += otr.value) >= mod()) value -= mod(); return *this; }
Z_p &operator-=(const Z_p &otr){ if((value -= otr.value) < 0) value += mod(); return *this; }
template<typename U> Z_p &operator+=(const U &otr){ return *this += Z_p(otr); }
template<typename U> Z_p &operator-=(const U &otr){ return *this -= Z_p(otr); }
Z_p &operator++(){ return *this += 1; }
Z_p &operator--(){ return *this -= 1; }
Z_p operator++(int){ Z_p result(*this); *this += 1; return result; }
Z_p operator--(int){ Z_p result(*this); *this -= 1; return result; }
Z_p operator-() const{ return Z_p(-value); }
template<typename U = T>
typename enable_if<is_same<typename Z_p<U>::Type, int>::value, Z_p>::type &operator*=(const Z_p& rhs){
#ifdef _WIN32
uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;
asm(
"divl %4; \n\t"
: "=a" (d), "=d" (m)
: "d" (xh), "a" (xl), "r" (mod())
);
value = m;
#else
value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
#endif
return *this;
}
template<typename U = T>
typename enable_if<is_same<typename Z_p<U>::Type, int64_t>::value, Z_p>::type &operator*=(const Z_p &rhs){
uint64_t ret = static_cast<uint64_t>(value) * static_cast<uint64_t>(rhs.value) - static_cast<uint64_t>(mod()) * static_cast<uint64_t>(1.L / static_cast<uint64_t>(mod()) * static_cast<uint64_t>(value) * static_cast<uint64_t>(rhs.value));
value = normalize(static_cast<int64_t>(ret + static_cast<uint64_t>(mod()) * (ret < 0) - static_cast<uint64_t>(mod()) * (ret >= static_cast<uint64_t>(mod()))));
return *this;
}
template<typename U = T>
typename enable_if<!is_integral<typename Z_p<U>::Type>::value, Z_p>::type &operator*=(const Z_p &rhs){
value = normalize(value * rhs.value);
return *this;
}
template<typename U>
Z_p &operator^=(U e){
if(e < 0) *this = 1 / *this, e = -e;
Z_p res = 1;
for(; e; *this *= *this, e >>= 1) if(e & 1) res *= *this;
return *this = res;
}
template<typename U>
Z_p operator^(U e) const{
return Z_p(*this) ^= e;
}
Z_p &operator/=(const Z_p &otr){
Type a = otr.value, m = mod(), u = 0, v = 1;
if(a < (int)MOD_INV.size()) return *this *= MOD_INV[a];
while(a){
Type t = m / a;
m -= t * a; swap(a, m);
u -= t * v; swap(u, v);
}
assert(m == 1);
return *this *= u;
}
template<typename U> friend const Z_p<U> &abs(const Z_p<U> &v){ return v; }
Type value;
};
template<typename T> bool operator==(const Z_p<T> &lhs, const Z_p<T> &rhs){ return lhs.value == rhs.value; }
template<typename T, typename U, typename enable_if<is_integral<U>::value>::type* = nullptr> bool operator==(const Z_p<T>& lhs, U rhs){ return lhs == Z_p<T>(rhs); }
template<typename T, typename U, typename enable_if<is_integral<U>::value>::type* = nullptr> bool operator==(U lhs, const Z_p<T> &rhs){ return Z_p<T>(lhs) == rhs; }
template<typename T> bool operator!=(const Z_p<T> &lhs, const Z_p<T> &rhs){ return !(lhs == rhs); }
template<typename T, typename U, typename enable_if<is_integral<U>::value>::type* = nullptr> bool operator!=(const Z_p<T> &lhs, U rhs){ return !(lhs == rhs); }
template<typename T, typename U, typename enable_if<is_integral<U>::value>::type* = nullptr> bool operator!=(U lhs, const Z_p<T> &rhs){ return !(lhs == rhs); }
template<typename T> bool operator<(const Z_p<T> &lhs, const Z_p<T> &rhs){ return lhs.value < rhs.value; }
template<typename T> bool operator>(const Z_p<T> &lhs, const Z_p<T> &rhs){ return lhs.value > rhs.value; }
template<typename T> bool operator<=(const Z_p<T> &lhs, const Z_p<T> &rhs){ return lhs.value <= rhs.value; }
template<typename T> bool operator>=(const Z_p<T> &lhs, const Z_p<T> &rhs){ return lhs.value >= rhs.value; }
template<typename T> Z_p<T> operator+(const Z_p<T> &lhs, const Z_p<T> &rhs){ return Z_p<T>(lhs) += rhs; }
template<typename T, typename U, typename enable_if<is_integral<U>::value>::type* = nullptr> Z_p<T> operator+(const Z_p<T> &lhs, U rhs){ return Z_p<T>(lhs) += rhs; }
template<typename T, typename U, typename enable_if<is_integral<U>::value>::type* = nullptr> Z_p<T> operator+(U lhs, const Z_p<T> &rhs){ return Z_p<T>(lhs) += rhs; }
template<typename T> Z_p<T> operator-(const Z_p<T> &lhs, const Z_p<T> &rhs){ return Z_p<T>(lhs) -= rhs; }
template<typename T, typename U, typename enable_if<is_integral<U>::value>::type* = nullptr> Z_p<T> operator-(const Z_p<T>& lhs, U rhs){ return Z_p<T>(lhs) -= rhs; }
template<typename T, typename U, typename enable_if<is_integral<U>::value>::type* = nullptr> Z_p<T> operator-(U lhs, const Z_p<T> &rhs){ return Z_p<T>(lhs) -= rhs; }
template<typename T> Z_p<T> operator*(const Z_p<T> &lhs, const Z_p<T> &rhs){ return Z_p<T>(lhs) *= rhs; }
template<typename T, typename U, typename enable_if<is_integral<U>::value>::type* = nullptr> Z_p<T> operator*(const Z_p<T>& lhs, U rhs){ return Z_p<T>(lhs) *= rhs; }
template<typename T, typename U, typename enable_if<is_integral<U>::value>::type* = nullptr> Z_p<T> operator*(U lhs, const Z_p<T> &rhs){ return Z_p<T>(lhs) *= rhs; }
template<typename T> Z_p<T> operator/(const Z_p<T> &lhs, const Z_p<T> &rhs) { return Z_p<T>(lhs) /= rhs; }
template<typename T, typename U, typename enable_if<is_integral<U>::value>::type* = nullptr> Z_p<T> operator/(const Z_p<T>& lhs, U rhs) { return Z_p<T>(lhs) /= rhs; }
template<typename T, typename U, typename enable_if<is_integral<U>::value>::type* = nullptr> Z_p<T> operator/(U lhs, const Z_p<T> &rhs) { return Z_p<T>(lhs) /= rhs; }
template<typename T> istream &operator>>(istream &in, Z_p<T> &number){
typename common_type<typename Z_p<T>::Type, int64_t>::type x;
in >> x;
number.value = Z_p<T>::normalize(x);
return in;
}
template<typename T> ostream &operator<<(ostream &out, const Z_p<T> &number){ return out << number(); }
/*
using ModType = int;
struct VarMod{ static ModType value; };
ModType VarMod::value;
ModType &mod = VarMod::value;
using Zp = Z_p<VarMod>;
*/
// constexpr int mod = 1e9 + 7; // 1000000007
constexpr int mod = (119 << 23) + 1; // 998244353
// constexpr int mod = 1e9 + 9; // 1000000009
using Zp = Z_p<integral_constant<decay<decltype(mod)>::type, mod>>;
template<typename T> vector<typename Z_p<T>::Type> Z_p<T>::MOD_INV;
template<typename T = integral_constant<decay<decltype(mod)>::type, mod>>
void precalc_inverse(int SZ){
auto &inv = Z_p<T>::MOD_INV;
if(inv.empty()) inv.assign(2, 1);
for(; inv.size() <= SZ; ) inv.push_back((mod - 1LL * mod / (int)inv.size() * inv[mod % (int)inv.size()]) % mod);
}
template<typename T>
vector<T> precalc_power(T base, int SZ){
vector<T> res(SZ + 1, 1);
for(auto i = 1; i <= SZ; ++ i) res[i] = res[i - 1] * base;
return res;
}
template<typename T>
vector<T> precalc_factorial(int SZ){
vector<T> res(SZ + 1, 1); res[0] = 1;
for(auto i = 1; i <= SZ; ++ i) res[i] = res[i - 1] * i;
return res;
}
ll modpow(ll a, ll n) {
a %= mod;
ll r = 1;
while (n) {
if (n&1) r = (r*a)%mod;
a = (a*a)%mod;
n /= 2;
}
return r;
}
const int root = 62;
void ntt(vector<ll> &a) {
int n = size(a), L = 31 - __builtin_clz(n);
static vector<ll> rt(2, 1);
for (static int k = 2, s = 2; k < n; k *= 2, s++) {
rt.resize(n);
ll z[] = {1, modpow(root, mod >> s)};
for (int i = k; i < 2*k; ++i) rt[i] = rt[i / 2] * z[i & 1] % mod;
}
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]]);
for (int k = 1; k < n; k *= 2)
for (int i = 0; i < n; i += 2 * k) for (int j = 0; j < k; ++j) {
ll z = rt[j + k] * a[i + j + k] % mod, &ai = a[i + j];
a[i + j + k] = ai - z + (z > ai ? mod : 0);
ai += (ai + z >= mod ? z - mod : z);
}
}
vector<ll> conv(const vector<ll> &a, const vector<ll> &b) {
if (a.empty() || b.empty()) return {};
int s = size(a) + size(b) - 1, B = 32 - __builtin_clz(s), n = 1 << B;
int inv = modpow(n, mod - 2);
vector<ll> L(a), R(b), out(n);
L.resize(n), R.resize(n);
ntt(L), ntt(R);
for (int i = 0; i < n; ++i) out[-i & (n - 1)] = (ll)L[i] * R[i] % mod * inv % mod;
ntt(out);
return {out.begin(), out.begin() + s};
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
const int MAXN = 1.1e7;
auto fac = precalc_factorial<Zp>(MAXN);
auto C = [&] (int n, int r) {
if (r < 0 or r > n) return Zp(0);
return fac[n] / (fac[r] * fac[n-r]);
};
int t; cin >> t;
while (t--) {
int n, m , d; cin >> n >> m >> d;
vector<array<int, 2>> constraint(m);
for (int i = 0; i < m; ++i) {
int pos, val; cin >> pos >> val;
constraint[i] = {pos, d/val};
}
sort(begin(constraint), end(constraint));
if (constraint.back()[0] != n) constraint.push_back({n, d});
vector<array<int, 2>> reduced;
for (auto [pos, val] : constraint) {
while (!reduced.empty()) {
auto [x, y] = reduced.back();
if (y < val) break;
reduced.pop_back();
}
reduced.push_back({pos, val});
}
vector<ll> dp(2); dp[1] = 1;
int prevval = 1, prevpos = 0;
for (auto [pos, val] : reduced) {
auto dp2 = dp;
dp.resize(val+1);
int len = pos - prevpos - 1;
for (int i = 0; i <= val; ++i)
dp[i] = C(len + i, i)();
auto res = conv(dp, dp2);
dp = res;
while (dp.size() > val+1) dp.pop_back();
prevpos = pos;
prevval = val;
}
cout << accumulate(begin(dp), end(dp), Zp(0)) << '\n';
}
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class NOL_LESS{
//SOLUTION BEGIN
long[][] fif;
long MOD = 998244353;
long BIG = MOD*MOD;
void pre() throws Exception{
fif = fif(100000+10000000);
}
void solve(int TC) throws Exception{
int N = ni(), M = ni(), D = ni();
int[][] restr = new int[M][];
for(int i = 0; i< M; i++)restr[i] = new int[]{ni()-1, ni()};
Arrays.sort(restr, (int[] i1, int[] i2) -> Integer.compare(i1[0], i2[0]));
int[][] intervals = new int[M+1][];
int cnt = 0;
int last = N-1, maxVal = D;
for(int i = M-1; i>= 0; i--){
if(D/restr[i][1] < maxVal){
if(last > restr[i][0])intervals[cnt++] = new int[]{restr[i][0]+1, last, maxVal};
maxVal = D/restr[i][1];
last = restr[i][0];
}
}
intervals[cnt++] = new int[]{0, last, maxVal};
for(int l = 0, r = cnt-1; l< r; l++, r--){
int[] tmp = intervals[l];
intervals[l] = intervals[r];
intervals[r] = tmp;
}
long[] ways = new long[]{0, 1};
for(int i = 0; i< cnt; i++){
int C = intervals[i][1]-intervals[i][0]+1, upto = intervals[i][2];
long[] P = new long[1+upto];
for(int j = 0; j <= upto; j++)P[j] = C(j+C-1, C-1);
ways = Arrays.copyOf(Convolution.convolution(ways, P, (int)MOD), 1+upto);
}
long ans = 0;
for(long x:ways)ans = (ans+x)%MOD;
pn(ans);
}
void dbg(Object... o){System.out.println(Arrays.deepToString(o));}
long ways(int min, int max, int C){
int M = max-min;
return C(M+C-1, M);
}
long[][] fif(int mx){
mx++;
long[] F = new long[mx], IF = new long[mx];
F[0] = 1;
for(int i = 1; i< mx; i++)F[i] = (F[i-1]*i)%MOD;
//GFG
long M = MOD;
long y = 0, x = 1;
long a = F[mx-1];
while(a> 1){
long q = a/M;
long t = M;
M = a%M;
a = t;
t = y;
y = x-q*y;
x = t;
}
if(x<0)x+=MOD;
IF[mx-1] = x;
for(int i = mx-2; i>= 0; i--)IF[i] = (IF[i+1]*(i+1))%MOD;
return new long[][]{F, IF};
}
long C(int n, int r){
if(n<r || r<0)return 0;
return (fif[0][n]*((fif[1][r]*fif[1][n-r])%MOD))%MOD;
}
long inv(long x){
long o = 1;
for(long p = MOD-2; p > 0; p>>=1){
if((p&1)==1)o = (o*x)%MOD;
x = (x*x)%MOD;
}
return o;
}
/**
* Convolution.
*
* @verified https://atcoder.jp/contests/practice2/submissions/24449847
* @verified https://judge.yosupo.jp/submission/53841
*/
static class Convolution {
/**
* Find a primitive root.
*
* @param m A prime number.
* @return Primitive root.
*/
private static int primitiveRoot(int m) {
if (m == 2) return 1;
if (m == 167772161) return 3;
if (m == 469762049) return 3;
if (m == 754974721) return 11;
if (m == 998244353) return 3;
int[] divs = new int[20];
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (long) (i) * i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) {
divs[cnt++] = x;
}
for (int g = 2; ; g++) {
boolean ok = true;
for (int i = 0; i < cnt; i++) {
if (pow(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
/**
* Power.
*
* @param x Parameter x.
* @param n Parameter n.
* @param m Mod.
* @return n-th power of x mod m.
*/
private static long pow(long x, long n, int m) {
if (m == 1) return 0;
long r = 1;
long y = x % m;
while (n > 0) {
if ((n & 1) != 0) r = (r * y) % m;
y = (y * y) % m;
n >>= 1;
}
return r;
}
/**
* Ceil of power 2.
*
* @param n Value.
* @return Ceil of power 2.
*/
private static int ceilPow2(int n) {
int x = 0;
while ((1L << x) < n) x++;
return x;
}
private static class FftInfo {
private static int bsfConstexpr(int n) {
int x = 0;
while ((n & (1 << x)) == 0) x++;
return x;
}
private static long inv(long a, long mod) {
long b = mod;
long p = 1, q = 0;
while (b > 0) {
long c = a / b;
long d;
d = a;
a = b;
b = d % b;
d = p;
p = q;
q = d - c * q;
}
return p < 0 ? p + mod : p;
}
private final int rank2;
public final long[] root;
public final long[] iroot;
public final long[] rate2;
public final long[] irate2;
public final long[] rate3;
public final long[] irate3;
public FftInfo(int g, int mod) {
rank2 = bsfConstexpr(mod - 1);
root = new long[rank2 + 1];
iroot = new long[rank2 + 1];
rate2 = new long[Math.max(0, rank2 - 2 + 1)];
irate2 = new long[Math.max(0, rank2 - 2 + 1)];
rate3 = new long[Math.max(0, rank2 - 3 + 1)];
irate3 = new long[Math.max(0, rank2 - 3 + 1)];
root[rank2] = pow(g, (mod - 1) >> rank2, mod);
iroot[rank2] = inv(root[rank2], mod);
for (int i = rank2 - 1; i >= 0; i--) {
root[i] = root[i + 1] * root[i + 1] % mod;
iroot[i] = iroot[i + 1] * iroot[i + 1] % mod;
}
{
long prod = 1, iprod = 1;
for (int i = 0; i <= rank2 - 2; i++) {
rate2[i] = root[i + 2] * prod % mod;
irate2[i] = iroot[i + 2] * iprod % mod;
prod = prod * iroot[i + 2] % mod;
iprod = iprod * root[i + 2] % mod;
}
}
{
long prod = 1, iprod = 1;
for (int i = 0; i <= rank2 - 3; i++) {
rate3[i] = root[i + 3] * prod % mod;
irate3[i] = iroot[i + 3] * iprod % mod;
prod = prod * iroot[i + 3] % mod;
iprod = iprod * root[i + 3] % mod;
}
}
}
};
/**
* Garner's algorithm.
*
* @param c Mod convolution results.
* @param mods Mods.
* @return Result.
*/
private static long garner(long[] c, int[] mods) {
int n = c.length + 1;
long[] cnst = new long[n];
long[] coef = new long[n];
java.util.Arrays.fill(coef, 1);
for (int i = 0; i < n - 1; i++) {
int m1 = mods[i];
long v = (c[i] - cnst[i] + m1) % m1;
v = v * pow(coef[i], m1 - 2, m1) % m1;
for (int j = i + 1; j < n; j++) {
long m2 = mods[j];
cnst[j] = (cnst[j] + coef[j] * v) % m2;
coef[j] = (coef[j] * m1) % m2;
}
}
return cnst[n - 1];
}
/**
* Inverse NTT.
*
* @param a Target array.
* @param g Primitive root of mod.
* @param mod NTT Prime.
*/
private static void butterflyInv(long[] a, int g, int mod) {
int n = a.length;
int h = ceilPow2(n);
FftInfo info = new FftInfo(g, mod);
int len = h; // a[i, i+(n>>len), i+2*(n>>len), ..] is transformed
while (len > 0) {
if (len == 1) {
int p = 1 << (h - len);
long irot = 1;
for (int s = 0; s < (1 << (len - 1)); s++) {
int offset = s << (h - len + 1);
for (int i = 0; i < p; i++) {
long l = a[i + offset];
long r = a[i + offset + p];
a[i + offset] = (l + r) % mod;
a[i + offset + p] = (mod + l - r) % mod * irot % mod;
}
if (s + 1 != (1 << (len - 1))) {
irot *= info.irate2[Integer.numberOfTrailingZeros(~s)];
irot %= mod;
}
}
len--;
} else {
// 4-base
int p = 1 << (h - len);
long irot = 1, iimag = info.iroot[2];
for (int s = 0; s < (1 << (len - 2)); s++) {
long irot2 = irot * irot % mod;
long irot3 = irot2 * irot % mod;
int offset = s << (h - len + 2);
for (int i = 0; i < p; i++) {
long a0 = 1L * a[i + offset + 0 * p];
long a1 = 1L * a[i + offset + 1 * p];
long a2 = 1L * a[i + offset + 2 * p];
long a3 = 1L * a[i + offset + 3 * p];
long a2na3iimag = 1L * (mod + a2 - a3) % mod * iimag % mod;
a[i + offset] = (a0 + a1 + a2 + a3) % mod;
a[i + offset + 1 * p] = (a0 + (mod - a1) + a2na3iimag) % mod * irot % mod;
a[i + offset + 2 * p] = (a0 + a1 + (mod - a2) + (mod - a3)) % mod * irot2 % mod;
a[i + offset + 3 * p] = (a0 + (mod - a1) + (mod - a2na3iimag)) % mod * irot3 % mod;
}
if (s + 1 != (1 << (len - 2))) {
irot *= info.irate3[Integer.numberOfTrailingZeros(~s)];
irot %= mod;
}
}
len -= 2;
}
}
}
/**
* Inverse NTT.
*
* @param a Target array.
* @param g Primitive root of mod.
* @param mod NTT Prime.
*/
private static void butterfly(long[] a, int g, int mod) {
int n = a.length;
int h = ceilPow2(n);
FftInfo info = new FftInfo(g, mod);
int len = 0; // a[i, i+(n>>len), i+2*(n>>len), ..] is transformed
while (len < h) {
if (h - len == 1) {
int p = 1 << (h - len - 1);
long rot = 1;
for (int s = 0; s < (1 << len); s++) {
int offset = s << (h - len);
for (int i = 0; i < p; i++) {
long l = a[i + offset];
long r = a[i + offset + p] * rot % mod;
a[i + offset] = (l + r) % mod;
a[i + offset + p] = (l + mod - r) % mod;
}
if (s + 1 != (1 << len)) {
rot *= info.rate2[Integer.numberOfTrailingZeros(~s)];
rot %= mod;
}
}
len++;
} else {
// 4-base
int p = 1 << (h - len - 2);
long rot = 1, imag = info.root[2];
for (int s = 0; s < (1 << len); s++) {
long rot2 = rot * rot % mod;
long rot3 = rot2 * rot % mod;
int offset = s << (h - len);
for (int i = 0; i < p; i++) {
long mod2 = 1L * mod * mod;
long a0 = 1L * a[i + offset];
long a1 = 1L * a[i + offset + p] * rot % mod;
long a2 = 1L * a[i + offset + 2 * p] * rot2 % mod;
long a3 = 1L * a[i + offset + 3 * p] * rot3 % mod;
long a1na3imag = 1L * (a1 + mod2 - a3) % mod * imag % mod;
long na2 = mod2 - a2;
a[i + offset] = (a0 + a2 + a1 + a3) % mod;
a[i + offset + 1 * p] = (a0 + a2 + (2 * mod2 - (a1 + a3))) % mod;
a[i + offset + 2 * p] = (a0 + na2 + a1na3imag) % mod;
a[i + offset + 3 * p] = (a0 + na2 + (mod2 - a1na3imag)) % mod;
}
if (s + 1 != (1 << len)) {
rot *= info.rate3[Integer.numberOfTrailingZeros(~s)];
rot %= mod;
}
}
len += 2;
}
}
}
/**
* Convolution.
*
* @param a Target array 1.
* @param b Target array 2.
* @param mod NTT Prime.
* @return Answer.
*/
public static long[] convolution(long[] a, long[] b, int mod) {
int n = a.length;
int m = b.length;
if (n == 0 || m == 0) return new long[0];
int z = 1 << ceilPow2(n + m - 1);
{
long[] na = new long[z];
long[] nb = new long[z];
System.arraycopy(a, 0, na, 0, n);
System.arraycopy(b, 0, nb, 0, m);
a = na;
b = nb;
}
int g = primitiveRoot(mod);
butterfly(a, g, mod);
butterfly(b, g, mod);
for (int i = 0; i < z; i++) {
a[i] = a[i] * b[i] % mod;
}
butterflyInv(a, g, mod);
a = java.util.Arrays.copyOf(a, n + m - 1);
long iz = pow(z, mod - 2, mod);
for (int i = 0; i < n + m - 1; i++) a[i] = a[i] * iz % mod;
return a;
}
/**
* Convolution.
*
* @param a Target array 1.
* @param b Target array 2.
* @param mod Any mod.
* @return Answer.
*/
public static long[] convolutionLL(long[] a, long[] b, int mod) {
int n = a.length;
int m = b.length;
if (n == 0 || m == 0) return new long[0];
int mod1 = 754974721;
int mod2 = 167772161;
int mod3 = 469762049;
long[] c1 = convolution(a, b, mod1);
long[] c2 = convolution(a, b, mod2);
long[] c3 = convolution(a, b, mod3);
int retSize = c1.length;
long[] ret = new long[retSize];
int[] mods = {mod1, mod2, mod3, mod};
for (int i = 0; i < retSize; ++i) {
ret[i] = garner(new long[]{c1[i], c2[i], c3[i]}, mods);
}
return ret;
}
/**
* Naive convolution. (Complexity is O(N^2)!!)
*
* @param a Target array 1.
* @param b Target array 2.
* @param mod Mod.
* @return Answer.
*/
public static long[] convolutionNaive(long[] a, long[] b, int mod) {
int n = a.length;
int m = b.length;
int k = n + m - 1;
long[] ret = new long[k];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ret[i + j] += a[i] * b[j] % mod;
ret[i + j] %= mod;
}
}
return ret;
}
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new NOL_LESS().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 