Think about what it means for one number to divide another. If $$$x$$$ and $$$y$$$ are two distinct integers and $$$x$$$ divides $$$y$$$ then $$$x$$$ can't be too big with respect to $$$y$$$, more specifically $$$x \leq \frac{y}{2}$$$. How can we use this in our problem?

Read the hint first. $$$\newline$$$ While constructing the array $$$a$$$ of size $$$n$$$, the goal is to pick numbers from $$$1$$$ to $$$2n$$$ such that no number divides another. The hint gives us a nudge: $$$x | y \implies x \leq y/2$$$, so what if we construct the array in a way that $$$\text{min}(a)$$$ (the smallest element of the array) is greater than $$$\frac{\text{max}(a)}{2}$$$ (half of the maximum element). We can construct the array $$$[n + 1 \ldots 2n]$$$ which satisfies our required condition. $$$\newline$$$ Time Complexity : $$$O(n)$$$

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define sz(a) (int)((a).size())
#define all(x) (x).begin(), (x).end()

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

using pii = pair<int, int>;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;

const ld eps = 1e-9;
const int mod = 998244353;
const ll INF = 4e18;

void Solve(int _) {
    int n; cin >> n;
    for (int i = n + 1; i <= 2 * n; i ++) {
        cout << i << " ";
    }
    cout << endl;
}

int32_t main() {
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifndef ONLINE_JUDGE
     freopen("error.txt", "w", stderr);
    #endif
     
    int _ = 1;
    cin >> _;
    cout << fixed;
    cout << setprecision(20);
    for(int i = 1; i <= _; i++) 
    {
        // cout << "Case #" << i << ": ";
        Solve(i);
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

Write down the first few observations of the series and try to find a pattern.

The first thing to notice is that the limit on $$$n$$$ is pretty huge, which makes it impractical to simulate the values. Following from the hint, suppose $$$a_1 = p$$$ and $$$a_2 = q$$$, then

• $$$a_3 = q - p$$$
• $$$a_4 = -p$$$
• $$$a_5 = -q$$$
• $$$a_6 = -q + p$$$
• $$$a_7 = p$$$
• $$$a_8 = q$$$

Thus the series loops after every 6 terms, and moreover the sum of each 6-length block is zero. Now, if we need the sum of first $$$n$$$ terms, the full cycles (multiples of 6) contribute nothing and we can only add up the first $$$n \% 6$$$ numbers. Make sure to use the mod operator.

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define sz(a) (int)((a).size())
#define all(x) (x).begin(), (x).end()

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

using pii = pair<int, int>;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;

const ld eps = 1e-9;
const int mod = 1e9 + 7;
const ll INF = 4e18;

void Solve(int _) {
    int n; cin >> n; 
    n %= 6;

    // generate the first 6 terms
    vector<int> a(6, 0);
    cin >> a[1] >> a[2];
    for (int i = 3; i < 6; i++)
        a[i] = a[i - 1] - a[i - 2];

    int sum = 0;
    for (int i = 0; i <= n; i++) {
        sum += a[i]; 
        sum %= mod; sum += mod; sum %= mod;
    }

    cout << sum << endl;
}

int32_t main() {
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifndef ONLINE_JUDGE
     freopen("error.txt", "w", stderr);
    #endif

    int _ = 1;
    cin >> _;
    cout << fixed << setprecision(20);

    for(int i = 1; i <= _; i++) 
    {
        // cout << "Case #" << i << ": ";
        Solve(i);
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

Given a polynomial $$$Q(x) = a_0 + a_1x + a_2x ^2 + \ldots a_n x^n$$$. What is the relationship between $$$x$$$ and sum of coefficients of $$$Q(x)$$$?

Note that for any arbitrary polynomial $$$Q(x)$$$, the sum of coefficients is obtained by putting $$$x=1$$$, that is $$$Q(1)$$$ is the sum of coefficients. As $$$P^{k}(x)$$$ is also a polynomial, the required sum is $$$P^{k}(1)$$$. Now write $$$P^{k}(x)$$$ as the product of k polynomials $$$P(x)$$$, and we get $$$P^k(1) = (P(1)) ^ k$$$. Now, $$$P(1)$$$ can be obtained in $$$O(n)$$$ by just adding up the values in the given array. For finding $$$k^{\text{th}}$$$ exponent of this sum, we have to use binary exponentiation, as the sum of $$$k$$$ is not bounded across all test cases.

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define sz(a) (int)((a).size())
#define all(x) (x).begin(), (x).end()

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

using pii = pair<int, int>;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;

const ld eps = 1e-9;
const int mod = 1e9 + 7;
const ll INF = 4e18;

ll expo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}

void Solve(int _) {
    int k, n; cin >> k >> n;
    vector<int> a(n + 1);
    for (auto &x: a) cin >> x;
    int sum = 0;
    for (int i = 0; i < n + 1; ++i)
    {
        sum += a[i]; sum %= mod; sum += mod; sum %= mod;
    }
    cout << expo(sum, k, mod) << endl;
}

int32_t main() {
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifndef ONLINE_JUDGE
     freopen("error.txt", "w", stderr);
    #endif
    int _ = 1;
    cin >> _;
    cout << fixed << setprecision(20);
    for(int i = 1; i <= _; i++) 
    {
        // cout << "Case #" << i << ": ";
        Solve(i);
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

Start by thinking about the two operations. Type-1 just incremements $$$ a_1 $$$, while type-2 grows the array with a new number attached to when you use it. What happens if you fix how many times you use each one? How does that shape the final array?

Focus on type-2 for a sec. Every time you use it, you add the operation number $$$ i $$$ after some position in the array. Try building and counting the arrays with say, say 1, 2, or 3 type-2 moves. Can you generalise the expression for some number $$$y$$$ of these operations?

Suppose total number of operations we perform are $$$t$$$ ($$$l \leq t \leq r $$$). Suppose we also fix the number of times type-1 operations we are going to perform — say $$$k$$$ operations ($$$0 \leq k \leq x$$$ as $$$a_1$$$ can't exceed $$$x$$$), that is $$$a_1$$$ will eventually be equal to $$$k$$$. We will use the remaining $$$t - k$$$ operations on type-2 operation. What's cool about type-2 operation is that it adds a fresh element $$$i$$$ based on the time it is used. So if we change the time points when type-2 operation is applied it will always result in a different array.

Hence we can first fix the time points when type-2 operation will be applied (or alternatively fix the times which operation 1 will be applied) and then multiply this with the number of arrays formed by type-2 operation (with fixed time points). Fixing the time points can be done in $$$\binom{t}{k}$$$ ways. Now all that remains is to count the number of different arrays that can be generated by using type-2 operation $$$t - k$$$ times.

Think about what happens when we do operation of type-2. If currently at any stage we have already performed $$$y - 1$$$ type-2 operations (that is currently our array is of size $$$y$$$, as each type-2 operation adds an element) then we have the choice of putting some new element after any of the $$$y$$$ current position. So the first type-2 operation has 1 choice (after $$$a_1$$$, size $$$1$$$), second type-2 operation has 2 choices (size $$$2$$$), third type-2 operation has 3 choices (size $$$3$$$), and so on. The number of ways to build the array with $$$t - k$$$ operations can be counted by by multiplying all the possible ways that each element can be added i.e. $$$1 \times 2 \times \ldots \times (t - k)$$$ = $$$(t - k)!$$$.

Hence the final expression can be calculated by summing over all values of $$$t$$$ and $$$k$$$:

Expanding the binomial coefficient, the expression can be simplified further:

The first part's the sum of factorials from $$$l$$$ to $$$r$$$ and the second's sum of inverse factorials till $$$x$$$. As $$$l,\ r$$$ and $$$x$$$ are upper bounded by $$$10 ^ 6$$$, we can pre-calculate the prefix sums on factorial and inverse factorials in $$$O(1e6 \cdot \log p)$$$ or $$$O(1e6 + \log p)$$$ time based on implementation and answer each query in $$$O(1)$$$ time.

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define sz(a) (int)((a).size())
#define all(x) (x).begin(), (x).end()

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

using pii = pair<int, int>;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;

const ld eps = 1e-9;
const int mod = 998244353;
const ll INF = 4e18;
const int N = 1e6 + 15; 

vector<int> fact(N), ifact(N), pf(N), pif(N);

ll expo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}

void Solve(int _) {
    int x, l, r; cin >> x >> l >> r;

    cout << (((pf[r] - pf[l - 1] + mod) % mod) * pif[x]) % mod << endl;
}

int32_t main() {
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifndef ONLINE_JUDGE
     freopen("error.txt", "w", stderr);
    #endif
    int _ = 1;
    cin >> _;
    cout << fixed << setprecision(20);

    fact[0] = ifact[0] = pf[0] = pif[0] = 1;

    for (int i = 1; i < N; i++) {
        fact[i] = (fact[i - 1] * i) % mod; 
        ifact[i] = expo(fact[i], mod - 2, mod);

        pf[i] = pf[i - 1] + fact[i]; pf[i] %= mod;
        pif[i] = pif[i - 1] + ifact[i]; pif[i] %= mod;
    }

    for(int i = 1; i <= _; i++) 
    {
        // cout << "Case #" << i << ": ";
        Solve(i);
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

We start by observing that the condition

is multiplicative. Because $$$\operatorname{lcm}$$$, $$$\gcd$$$ and division are all multiplicative.

So this can be handled one prime at a time. Write

so that for each prime $$$p$$$ dividing $$$a_1$$$ the exponent in $$$a_1$$$ is $$$e_p$$$. For any sequence $$${a_1, a_2, \dots, a_n}$$$, let $$$f_i$$$ denote the exponent of $$$p$$$ in $$$a_i$$$. Notice that $$$f_1 = e_p$$$.

The $$$\gcd$$$ and $$$\operatorname{lcm}$$$ for the prime $$$p$$$ are given by

so the contribution of $$$p$$$ to

is

Since the overall condition requires that

for each prime $$$p$$$ we must have

For each prime $$$p$$$ with exponent $$$e_p$$$ in $$$a_1$$$, let's analyze how we can choose the other exponents $$$f_2, f_3, \dots, f_n$$$ (for $$$n-1$$$ positions).

The key observation is that for any valid sequence with $$$f_1 = e_p$$$, if we have $$$\max{f_i} - \min{f_i} = e_p$$$, then the possible ranges for $$$[\min{f_i}, \max{f_i}]$$$ (or $$$[m, M]$$$) are: $$$[0, e_p], [1, e_p+1], \dots, [e_p, 2e_p]$$$

This gives us $$$e_p + 1$$$ possible ranges.

For each range $$$[m, M]$$$, let's try to count the number of valid sequences.

In general, we can choose each $$$f_i$$$ (for $$$n-1$$$ positions $$$f_2, f_3, \dots, f_n$$$) to be any value within $$$[m, M]$$$, giving $$$(M-m+1)^{n-1} = (e_p + 1)^{n-1}$$$ possibilities.

However, this overcounts sequences that don't actually achieve both the minimum and maximum values in their range. We need to apply inclusion-exclusion.

Case 1: $$$m = 0$$$

In this case, $$$[m, M] = [0, e_p]$$$

• All $$$f_2, f_3, \dots, f_n$$$ can be chosen from $$$[0, e_p]$$$, so there are $$$(e_p+1)^{n-1}$$$ valid sequences.
• Subtract sequences where no $$$f_i$$$ equals the minimum:
  • The number of choices for $$$f_i$$$ is $$$e_p$$$ (any of $$$[1, e_p]$$$)
  • There are $$$n-1$$$ positions to choose, so the total number of sequences is $$$e_p^{n-1}$$$
• Subtract sequences where no $$$f_i$$$ equals the maximum:
  • But as $$$f_1 = e_p$$$, this is impossible as we already have $$$f_1$$$ as the maximum.
  • So we don't need to subtract anything here.

So the number of valid sequences in this case is:

Case 2: $$$m = e_p$$$

In this case, $$$[m, M] = [e_p, 2e_p]$$$

• All $$$f_2, f_3, \dots, f_n$$$ can be chosen from $$$[e_p, 2e_p]$$$, so there are $$$(2e_p-e_p+1)^{n-1} = (e_p+1)^{n-1}$$$ valid sequences.
• Subtract sequences where no $$$f_i$$$ equals the minimum:
  • As $$$f_1 = e_p$$$, this is impossible as we already have $$$f_1$$$ as the minimum.
  • So we don't need to subtract anything here.
• Subtract sequences where no $$$f_i$$$ equals the maximum:
  • The number of choices for $$$f_i$$$ is $$$e_p$$$ (any of $$$[e_p, 2e_p - 1]$$$)
  • There are $$$n-1$$$ positions to choose, so the total number of sequences is $$$(e_p-1)^{n-1}$$$

So the number of valid sequences in this case is:

Case 3: $$$0 \lt m \lt e_p$$$

In this case, $$$M = m + e_p$$$

• All $$$f_2, f_3, \dots, f_n$$$ can be chosen from $$$[m, M]$$$, so there are $$$(M-m+1)^{n-1} = (e_p+1)^{n-1}$$$ valid sequences.
• Subtract sequences where no $$$f_i$$$ equals the minimum:
  • The number of choices for $$$f_i$$$ is $$$M-m$$$ (any of $$$[m+1, M]$$$)
  • There are $$$n-1$$$ positions to choose, so the total number of sequences is $$$(M-m)^{n-1} = e_p^{n-1}$$$
• Subtract sequences where no $$$f_i$$$ equals the maximum:
  • The number of choices for $$$f_i$$$ is $$$M-m$$$ (any of $$$[m, M-1]$$$)
  • There are $$$n-1$$$ positions to choose, so the total number of sequences is $$$(M-m)^{n-1} = e_p^{n-1}$$$
• Add back sequences where neither minimum nor maximum appears (as these were subtracted twice):
  • The number of choices for $$$f_i$$$ is $$$M-m-1$$$ (any of $$$[m+1, M-1]$$$)
  • There are $$$n-1$$$ positions to choose, so the total number of sequences is $$$(M-m-1)^{n-1} = (e_p-1)^{n-1}$$$

So the number of valid sequences for a fixed range $$$[m, M]$$$ is:

So for each $$$0 \lt m \lt e_p$$$, ($$$e_p - 1$$$ such ranges), the number of valid sequences is:

So over all three cases, the total number of valid sequences is:

Which is the same as (after some simplification):

The final answer is the product over all primes $$$p$$$ dividing $$$a_1$$$:

So basically the solution is: factorize $$$a_1$$$, compute the contribution for each prime factor as shown using fast exponentiation, and multiply all contributions modulo $$$998\,244\,353$$$.

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define sz(a) (int)((a).size())
#define all(x) (x).begin(), (x).end()

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

using pii = pair<int, int>;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;

const ld eps = 1e-9;
const int mod = 998244353;
const ll INF = 4e18;
const int N = 2e5 + 10;

ll expo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}

void Solve(int _) {
    int a1, n; cin >> a1 >> n;
    int ans = 1;
    // auto calc = [&] (int alpha) -> int {
    //     return (expo(1 + alpha, n - 1, mod) - expo(alpha, n - 1, mod) - 1 + mod + mod) % mod;
    // };
    vector<int> pow(32);
    for (int i = 0; i < 32; i++) {
        pow[i] = expo(i, n, mod);
    }

    vector<int> alpha(32);
    for (int i = 1; i < 31; i++) {
        alpha[i] = pow[i + 1] - 2 * pow[i] + pow[i - 1];
        alpha[i] += 2 * mod; alpha[i] %= mod;
    }

    for (ll i = 2; i * i <= a1; i++) {
        if (a1 % i)
            continue;
        int cnt = 0;
        while (a1 % i == 0) {
            cnt++;
            a1 /= i;
        }
        ans *= alpha[cnt]; ans %= mod;
    }

    if (a1 > 1) {
        int cnt = 1;
        ans *= alpha[1]; ans %= mod;
    }
    cout << ans << endl;
}

int32_t main() {
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifndef ONLINE_JUDGE
     freopen("error.txt", "w", stderr);
    #endif
    int _ = 1;
    cin >> _;
    cout << fixed;
    cout << setprecision(20);

    for(int i = 1; i <= _; i++) 
    {
        // cout << "Case #" << i << ": ";
        Solve(i);
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

Let’s figure out what $$$ g^{(k)}(x) $$$ looks like first:

Next find the the conditions under which $$$f(x)$$$ will divide $$$g^{(k)}(x)$$$:

1. $$$q$$$ (the quotient) $$$\in \mathbb{Z}$$$
2. $$$0 \leq k \leq n + 1$$$ (we stop at $$$n + 1$$$, since the polynomial is zero then)
3. $$$A \cdot q = \frac{n!}{(n-k)!}\cdot C $$$, and $$$ B \cdot q = \frac{(n - 1)!}{(n - 1 - k)!} \cdot D$$$

Dividing both the equations in condition 3 yields

On rearranging, we get

This also includes the case when $$$k = 0$$$. Note that the answer can never be $$$n$$$ (Why?). If $$$k$$$ is not in the desired range stated in condition 2, we can just print $$$n + 1$$$, as a zero polynomial is divisible by any other polynomial. Now we need to check if the first condition i.e. $$$q \in \mathbb{Z}$$$ holds. How to do this?

From condition 2, we just need to check if $$$A | \frac{n!}{(n-k)!}\cdot C$$$. Denote $$$g$$$ by $$$\text{gcd}(A, C)$$$. We need to check if $$$\frac{A}{g} | \frac{n!}{(n-k)!}$$$. For the sake of brevity, denote $$$\frac{A}{g}$$$ by $$$R$$$. Since the value of $$$\frac{n!}{(n-k)!}$$$ can get huge we can't compute it directly. One way to solve further, is to look at the prime factors, suppose $$$R = p_1^{\alpha_1}\ldots p_k^{\alpha_k}$$$. For each prime $$$p_i, (i \in {1 \ldots k})$$$, denote the exponent of this prime in the expression $$$\frac{n!}{(n-k)!}$$$ by $$$\beta_i$$$. $$$R | \frac{n!}{(n-k)!} \iff \forall i \in {1 \ldots k}, \beta_i \geq \alpha_i$$$, and so, $$$q \in \mathbb{Z}$$$. All that remains is to calculate $$$\beta_i$$$ that is the power of $$$p_i$$$ in $$$\frac{n!}{(n-k)!}$$$, which can be calculated by subtracting exponents of $$$p_i$$$ in $$$n!$$$ and $$$(n - k)!$$$. Finding exponents of a positive number in a factorial is a standard task and can be calculated using the formula $$$\beta_{n, i} = \sum_{j = 1}^{\infty} \lfloor {\frac{n}{p_i^j}} \rfloor$$$ (this is the exponent of $$$p_i$$$ in $$$n!$$$, In a similar fashion obtain $$$\beta_{n - k, i}$$$ and subtract). For more details, refer Multiplicity of prime $$$p$$$ in $n!$. For implementation details, look at the code.

Time Complexity

To find $$$p_i$$$'s, we can pre-compute smallest prime factor array for all the numbers till $$$N$$$, using Sieve of Eratosthenes. For any $$$R$$$, there can be atmost 7 different primes, calculating $$$\beta_{n, i}$$$ and $$$\alpha_i$$$ for some prime $$$p_i$$$ takes $$$O(\log _p N)$$$ time. Thus, time complexity = $$$O(t \cdot 21 \cdot \log N + N \log \log N)$$$.

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define sz(a) (int)((a).size())
#define all(x) (x).begin(), (x).end()

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

using pii = pair<int, int>;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;

const ld eps = 1e-9;
const int mod = 998244353;
const ll INF = 4e18;
const int N = 2e5 + 10;

vector<int> spf(N, -1); // smallest prime factor vector

void Solve(int _) {
    int A, B, C, D, n; cin >> A >> B >> C >> D >> n;

    int sum = ((A * D) - (B * C)) * n;
    int AD = A * D;

    auto count = [&] (int N, int p) -> int {
        // counts exponent of p in N!
        int ret = 0;
        while (N) {
            ret += N / p;
            N /= p;
        }
        return ret;
    };

    if (sum >= 0 && sum % AD == 0) {
        int k = sum / AD;
        // check if (n!) * C / (n - k)! is divisible by A
        int R = A / gcd(C, A);
        // check if R divides n! / (n - k)!
        if (k < n && k >= 0) {
            bool ok = true;
            while (R != 1) {
                int p = spf[R];
                int alpha = 0;
                while (R % p == 0) {
                    alpha++; R /= p;
                } 
                // beta = count(n, p) - count(n - k, p)
                if (count(n, p) - count(n - k, p) < alpha) {
                    ok = false; 
                    break;
                }
            }

            if (ok) {
                cout << k << endl; 
                return;
            }
        }
    }

    cout << n + 1 << endl;;
}

int32_t main() {
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifndef ONLINE_JUDGE
     freopen("error.txt", "w", stderr);
    #endif
    int _ = 1;
    cin >> _;
    cout << fixed;
    cout << setprecision(20);

    for (int i = 2; i < N; i++) {
        if (spf[i] != -1) continue;
        for (int j = i; j < N; j += i) {
            if (spf[j] == -1)
                spf[j] = i;
        }
    }

    for(int i = 1; i <= _; i++) 
    {
        // cout << "Case #" << i << ": ";
        Solve(i);
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

We begin by noting that the only thing that matters in the array is the collection of its values; that is, the positions are not important, only the multiset of numbers. In particular, if we sort the array in increasing order to get

then every operation only decreases some of these values. Moreover, if we consider the reverse-sorted array

one can prove that each valid operation strictly decreases $$$\operatorname{rev}(a)$$$ in the lexicographic order. This fact guarantees that the process terminates after a finite number of steps.

To maximize the total number of operations, we need to ``slow down'' the decrease. The following greedy strategy is optimal:

• If $$$a_1 \gt 0$$$ (i.e. the smallest element is positive), simply perform Operation 1 on $$$a_1$$$ by decrementing it.
• Otherwise, when $$$a_1 = 0$$$, let $$$i$$$ be the smallest index such that $$$a_i \gt 0$$$. Then perform Operation 2 on the indices $$$1, 2, \dots, i$$$. This operation sets every $$$a_j$$$ for $$$1 \le j \le i$$$ to $$$a_i - 1$$$, which is exactly the lexicographic predecessor of the current $$$a$$$.

This strategy is optimal because every operation moves the state to its immediate predecessor in the lexicographic order (when considering the reversed array), so no extra operations can be squeezed in between.

To count the maximum number of operations, let's analyze the scenario when all elements of the array are equal.

Let $$$f(i,j)$$$ denote the maximum number of operations that can be performed on an array of length $$$i$$$ where every element is equal to $$$j$$$. Basically the number of operations to convert all elements to $$$0$$$.

To construct the transition, we can consider the following:

• First we need to convert all elements of the first $$$i-1$$$ positions to $$$0$$$. So this will take $$$f(i-1,j)$$$ operations.
• Then we perform Operation 2 on the indices $$$1, 2, \dots, i$$$. This will convert all elements to $$$j-1$$$. So this will add $$$1$$$ operation.
• Now we need to convert all elements to $$$0$$$. So this will take $$$f(i,j-1)$$$ operations.

So we have the recurrence:

It is convenient to define $$$g(i,j) = f(i,j) + 1.$$$

Then, substituting $$$f(i,j) = g(i,j) - 1$$$ into the recurrence gives:

Now, add $$$1$$$ to both sides:

The base case is $$$g(0,0) = f(0,0) + 1 = 0 + 1 = 1$$$. Similarly, $$$g(i, 0) = g(0, i) = 1$$$ for all $$$i \ge 0$$$.

But this is exactly the Pascal's Triangle (rotated by $$$45$$$ degrees).

Hence, we have

Or you can think of it like this: the above recurrence is the exact same recurrence of the number of ways to go from point $$$(0, 0)$$$ to point $$$(i, j)$$$ if we can only go right or up. And that problem can be solved using stars and bars by imagining $$$i$$$ stars and $$$j$$$ bars and the number of such sequences is $$$\binom{i+j}{i}$$$.

So, the maximum number of operations on an array of length $$$i$$$ with all entries equal to $$$j$$$ is given by

Using this combinatorial formula, we can compute the answer for a given array. The steps are the following:

• Sort the array in increasing order.
• First, we need to convert $$$a_1$$$ to $$$0$$$. This will take $$$f(1, a_1)$$$ operations.
• Then, use one Operation 2 on indices $$$1, 2$$$ to set both elements to $$$a_2 - 1$$$.
• Then, perform $$$f(2, a_2 - 1)$$$ operations to convert the prefix of size $$$2$$$ to $$$0$$$.
• Then, use one Operation 2 on indices $$$1, 2, \dots, 3$$$ to set all elements to $$$a_3 - 1$$$.
• Then, perform $$$f(3, a_3 - 1)$$$ operations to convert the prefix of size $$$3$$$ to $$$0$$$.
• Continue this process until the whole array is converted to $$$0$$$.

The total number of operations is

which is equivalent to

By precomputing factorials and inverse factorials, you can compute the answer easily in $$$O(n + M)$$$ time where $$$M$$$ is the maximum element in the array.

// Counting Template
#include<bits/stdc++.h>

using namespace std;

#define mod 998244353
#define FACSIZE 2097152

long long power(long long a,long long b){
  long long x=1,y=a;
  while(b>0){
    if(b&1ll){
      x=(x*y)%mod;
    }
    y=(y*y)%mod;
    b>>=1;
  }
  return x%mod;
}

long long modular_inverse(long long n){
  return power(n,mod-2);
}

long long factorial[FACSIZE];
long long invfact[FACSIZE];

void cfact(){
  long long i;
  factorial[0]=1;
  factorial[1]=1;
  for(i=2;i<FACSIZE;i++){
    factorial[i]=factorial[i-1]*i;
    factorial[i]%=mod;
  }
  invfact[FACSIZE-1]=modular_inverse(factorial[FACSIZE-1]);
  for(i=FACSIZE-2;i>=0;i--){
    invfact[i]=invfact[i+1]*(i+1);
    invfact[i]%=mod;
  }
}

long long calcnCr(long long n,long long k){
  if(k<0 || n<k){return 0;}
  return (factorial[n]*((invfact[k]*invfact[n-k])%mod))%mod;
}

long long solve(){
  // write your code here, and return the answer
  long long n;
  cin >> n;
  vector<long long> a(n);
  for(auto &nx : a){cin >> nx;}
  sort(a.begin(),a.end());
  long long res=0;
  for(long long i=0;i<n;i++){
    res+=calcnCr(a[i]+i,i+1);
    res%=mod;
  }
  return res;
}

int main(){
  cfact();
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t=1;
  cin >> t;
  while(t>0){
    t--;
    cout << solve()%mod << "\n";
  }
  return 0;
}

// #include<bits/stdc++.h>
//
// using namespace std;
//
// map<vector<int>,int> mp;
//
// int sol(vector<int> a){
//   sort(a.begin(),a.end());
//   if(a.back()==0){return 0;}
//   if(mp.find(a)!=mp.end()){return mp[a];}
//
//   int n=a.size();
//   int res=0;
//   for(int i=0;i<n;i++){
//     if(a[i]>0){
//       auto ua=a;
//       ua[i]--;
//       res=max(res,sol(ua)+1);
//     }
//   }
//   for(int i=0;i<(1<<n);i++){
//     if(__builtin_popcount(i)<2){continue;}
//     int l=1e9,r=-1e9;
//     for(int j=0;j<n;j++){
//       if(i&(1<<j)){
//         l=min(l,a[j]);
//         r=max(r,a[j]);
//       }
//     }
//     if(l<r){
//       auto ua=a;
//       int v=(r-l-1);
//       for(int j=0;j<n;j++){
//         if(i&(1<<j)){
//           ua[j]=v;
//         }
//       }
//       res=max(res,sol(ua)+1);
//     }
//   }
//   mp[a]=res;
//   return res;
// }
//
// int main(){
//   ios::sync_with_stdio(false);
//   cin.tie(nullptr);
//   int n;
//   cin >> n;
//   vector<int> a(n);
//   for(auto &nx : a){cin >> nx;}
//   sol(a);
//   for(auto &nx : mp){
//     for(auto &ny : nx.first){
//       cout << ny << " ";
//     }
//     cout << ": " << nx.second << "\n";
//   }
//   return 0;
// }

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve: