The operation allows us to choose a divisor $$$z$$$ of $$$x$$$ and update $$$x := \frac{x}{z}$$$.

Since $$$z$$$ is a divisor of $$$x$$$, the resulting value $$$\frac{x}{z}$$$ is strictly an integer and is also a divisor of $$$x$$$. Because we can freely choose any valid $$$z$$$, a single operation effectively allows us to replace $$$x$$$ with any of its divisors.

Applying this operation multiple times does not yield any additional numbers, because a divisor of a divisor is still just a divisor of the original $$$x$$$. Therefore, the set of all possible numbers reachable from $$$x$$$ is strictly limited to its divisors.

Therefore, to solve the problem:

• If $$$y$$$ is a divisor of $$$x$$$ (i.e., $$$x \bmod y = 0$$$), we output YES. We can reach $$$y$$$ in at most $$$1$$$ operation by choosing $$$z = \frac{x}{y}$$$.
• If $$$y$$$ is not a divisor of $$$x$$$, we output NO, as it is impossible to reach.

Time Complexity: $$$\mathcal{O}(1)$$$.

#include<bits/stdc++.h>
using namespace std;
 
int main(){
 
    int tt;
    cin >> tt;
 
    while(tt--){
        int x, y;
        cin >> x >> y;
        
        cout << (x % y == 0 ? "YES" : "NO") << '\n';
    }
 
    return 0;
}

• Best Problem
• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Let $$$d$$$ be the number of digits of $$$x$$$, and choose $$$y = 10^d + 1$$$. The number $$$y$$$ contains only the digits $$$0$$$ and $$$1$$$, so $$$y$$$ is good. Also,

Since $$$x \lt 10^d$$$, multiplying by $$$10^d$$$ simply shifts $$$x$$$ by $$$d$$$ positions. Therefore, $$$x \cdot y$$$ is exactly the decimal concatenation of $$$x$$$ with itself. Hence, the set of digits appearing in $$$x \cdot y$$$ is the same as in $$$x$$$. Since $$$x$$$ is good, $$$x \cdot y$$$ is good as well.

Thus, for every test case, one of the possible answers is simply

The construction always satisfies $$$2 \le y \le 10^9$$$.

Time Complexity: $$$\mathcal{O}(\log_{10}(x))$$$.

#include<bits/stdc++.h>
using namespace std;
 
int main(){
 
    int tt;
    cin >> tt;
 
    while(tt--){
        int x;
        cin >> x;
 
        int y = 1;
 
        while(x > 0){
            y *= 10;
            x /= 10;
        }
 
        cout << y + 1 << '\n';
    }
 
    return 0;
}

• Best Problem
• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Let $$$c$$$ be the number of positions $$$i$$$ such that $$$s_i \ne s_{i+1}$$$.

If $$$c=0$$$, all characters are equal. The whole string is always a palindrome, so we can repeatedly delete characters until only one remains.

If $$$c=1$$$, the string consists of exactly two contiguous blocks of equal characters. Any palindrome of length at least $$$2$$$ must be contained entirely inside one of these blocks, so every operation only shortens a block and can never remove it completely. Therefore, both blocks remain nonempty, and the minimum possible length is $$$2$$$.

If $$$c\ge 2$$$, then the string has at least three blocks. First, we can shrink every block to length $$$1$$$, because any block of equal characters is itself a palindrome of length at least $$$2$$$ as long as its length is at least $$$2$$$. So we may assume the string becomes alternating.

Now consider an alternating string of length at least $$$3$$$. Its last three characters are always of the form $$$010$$$ or $$$101$$$; hence, they form a palindrome. Deleting the last character of this palindrome shortens the string by $$$1$$$, and the remaining string is still alternating. Repeating this step, we can reduce the string to length $$$3$$$. Then the whole string is a palindrome, and deleting its middle character gives two equal characters, which can be reduced to length $$$1$$$ in one more move.

Hence, the answer is $$$2$$$ iff $$$c=1$$$, and $$$1$$$ otherwise.

Time Complexity: $$$\mathcal{O}(n)$$$.

#include<bits/stdc++.h>
using namespace std;
 
int main(){
 
    int tt;
    cin >> tt;
 
    while(tt--){
        int n;
        string s;
        cin >> n >> s;
 
        int count = 0;
        for(int i = 0; i < n - 1; i++) if(s[i] != s[i + 1]) count++;
 
        cout << (count == 1 ? 2 : 1) << '\n';
    }
 
    return 0;
}

• Best Problem
• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Let

The key is to look at prefix sums. One operation on segment $$$[l,r]$$$ adds the pattern $$$+1,-1,+1,-1,\dots$$$ starting from the left end. Therefore, the prefix sum of the modified array changes by $$$1$$$ on some prefixes and by $$$0$$$ on the others, so no prefix sum can ever decrease.

Now take the special segment $$$[i,i+1]$$$. It adds $$$+1$$$ to $$$a_i$$$ and $$$-1$$$ to $$$a_{i+1}$$$, so only the $$$i$$$-th prefix sum increases by $$$1$$$, while all other prefix sums stay unchanged. Also, $$$[n,n]$$$ increases only the $$$n$$$-th prefix sum by $$$1$$$.

So every prefix sum can be increased independently and never decreased. Hence, the transformation is possible iff

Time Complexity: $$$\mathcal{O}(n)$$$.

An alternative way to solve the problem is to first understand which operations are actually useful.

Consider an operation on a subarray of length greater than $$$2$$$. Its effect is exactly the sum of the operations on consecutive subarrays of length $$$2$$$ inside it (partitioning the subarray into consecutive pairs; if its length is odd, the last element is treated as a subarray of length $$$1$$$). Therefore, every operation on a longer subarray can be decomposed into operations on length-$$$2$$$ subarrays, so it is sufficient to consider only these.

Now there are only two useful operations:

• applying the operation on $$$[i,i]$$$, which increases $$$a_i$$$ by $$$1$$$;
• applying the operation on $$$[i-1,i]$$$, which decreases $$$a_i$$$ by $$$1$$$ and increases $$$a_{i-1}$$$ by $$$1$$$.

We process the array from right to left. Suppose we are currently at position $$$i$$$.

• If $$$a_i \lt b_i$$$, we simply apply the first operation $$$b_i-a_i$$$ times, increasing only $$$a_i$$$ until it becomes $$$b_i$$$.
• If $$$a_i \gt b_i$$$, we apply the second operation $$$a_i-b_i$$$ times. Each application decreases $$$a_i$$$ by $$$1$$$ while increasing $$$a_{i-1}$$$ by $$$1$$$, so after these operations we have $$$a_i=b_i$$$. Any excess is pushed one position to the left.

Notice that after finishing position $$$i$$$, no later operation can change it again. Hence, every position except the first can always be fixed independently. After processing all positions from $$$n$$$ down to $$$2$$$, the only remaining value is $$$a_1$$$. Since every operation can only increase $$$a_1$$$, the transformation is possible if and only if

Thus, the algorithm is simply to process the array backwards as described above and finally check whether $$$a_1\le b_1$$$.

Time Complexity: $$$\mathcal{O}(n)$$$.

#include<bits/stdc++.h>
using namespace std;
 
int main(){
 
    int tt;
    cin >> tt;
 
    while(tt--){
        int n;
        cin >> n;
 
        vector<long long> a(n), b(n);
 
        for(int i = 0; i < n; i++) cin >> a[i];
        for(int i = 0; i < n; i++) cin >> b[i];
        for(int i = 1; i < n; i++) a[i] += a[i - 1];
        for(int i = 1; i < n; i++) b[i] += b[i - 1];
 
        bool is = 1;
        for(int i = 0; i < n; i++) if(a[i] > b[i]) is = 0;
 
        if(is) cout << "YES\n";
        else cout << "NO\n";
    }
 
    return 0;
}

• Best Problem
• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

For any two vertices $$$x$$$ and $$$y$$$, let us denote $$$P(x, y)$$$ as the simple path from $$$x$$$ to $$$y$$$.

Now, let us fix an unordered triplet of vertices $$${u,v,w}$$$. We claim that there is exactly one vertex (say $$$c$$$) that belongs to all three paths $$$P(u,v)$$$, $$$P(v,w)$$$, and $$$P(w,u)$$$, and every other vertex is counted $$$0$$$ or $$$2$$$ times.

Therefore, for the product

every vertex contributes an even exponent except $$$c$$$, whose exponent is $$$3$$$. Hence, the product is a perfect square iff $$$a_c$$$ is a perfect square.

So now we only need to count, for every vertex $$$x$$$ with $$$a_x$$$ a perfect square, how many triplets have $$$x$$$ as the unique common vertex. Remove $$$x$$$, and let the component sizes be $$$s_1,s_2,\dots,s_k$$$.

A valid triplet is of two types:

• $$$x$$$ is one of the chosen vertices. Then the other two vertices must come from two different components, so the count is

• $$$x$$$ is not chosen. Then the three chosen vertices must come from three different components, so the count is

Both values can be computed in one scan over the components:

and for each component size $$$s$$$:

Then the contribution of $$$x$$$ is $$$\text{pairs}+\text{triples}$$$.

To get the component sizes for every $$$x$$$, root the tree once and store subtree sizes. For a vertex $$$x$$$, its components after deletion are all child subtrees of $$$x$$$, plus the parent-side component of size $$$n-\mathrm{sz}[x]$$$ if it exists.

So the solution is:

• root the tree and compute subtree sizes;
• for every vertex $$$x$$$, build the sizes of components of $$$T-x$$$;
• if $$$a_x$$$ is a perfect square, add $$$\text{pairs}+\text{triples}$$$ to the answer.

Time Complexity: $$$\mathcal{O}(n)$$$.

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
 
int main(){
 
    int tt = 1;
    cin >> tt;
 
    while(tt--){
        ll n;
        cin >> n;
 
        vector<ll> a(n);
        for(ll i = 0; i < n; i++) cin >> a[i];
 
        vector<vector<ll>> v(n);
        for(ll i = 1; i < n; i++){
            ll x, y;
            cin >> x >> y;
            x--;
            y--;
            v[x].push_back(y);
            v[y].push_back(x);
        }
 
        ll ans = 0;
        vector<ll> ss(n, 1);
 
        function<void(ll, ll)> dfs = [&](ll u, ll par){
 
            vector<ll> val;
            for(auto& z : v[u]) if(z != par){
                dfs(z, u);
                val.push_back(ss[z]);
                ss[u] += ss[z];
            }
 
            val.push_back(n - ss[u]);
            assert(accumulate(val.begin(), val.end(), 0ll) == n - 1);
 
            if((ll)sqrtl(a[u]) * (ll)sqrtl(a[u]) < a[u]) return;
 
            ll sum = 0;
            ll pairs = 0;
            ll triplets = 0;

            for(auto& z : val){
                triplets += pairs * z;
                pairs += sum * z;
                sum += z;
            }

            ans += pairs;
            ans += triplets;
        };
 
        dfs(0, -1);
 
        cout << ans << '\n';
    }
 
    return 0;
}

• Best Problem
• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

One common way to solve these kinds of games is to first identify the losing states and then generalize their structure.

Let's first consider the states where the current player has no valid moves. An obvious example is a binary string consisting entirely of 0s or entirely of 1s. Since a player may delete any subsequence with an odd number of inversions, there is a lot of freedom in choosing a move. So instead of analyzing every possible move, let us ask a simpler question: When can Alice win immediately by deleting all 0s or all 1s?

Suppose Alice wants to delete all 1s. Then the chosen subsequence must have an odd number of inversions. This is possible iff it contains at least one 0 that is preceded by an odd number of 1s in the original string. Similarly, if Alice wants to delete all 0s, then the chosen subsequence must contain at least one 1 that is followed by an odd number of 0s. Both conditions can be checked in $$$\mathcal{O}(n)$$$ using prefix (or suffix) parity.

Now let us consider the strings that satisfy neither of these conditions. Such strings must have the form

where each $$$X_i$$$ is either 00 or 11. The leading 0 and trailing 1 are optional. Since these endpoint characters can never affect any inversion parity, we may simply ignore them. We claim that every string of this form is a losing state.

Therefore, Alice wins iff the initial string does not have the above form. Checking this structure is straightforward.

Time Complexity: $$$\mathcal{O}(n)$$$.

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
 
int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int tt = 1;
    cin >> tt;
 
    while(tt--){
        ll n;
        cin >> n;
 
        string s;
        cin >> s;

        bool is = 1;
        int left = 0, right = n - 1;

        while(left < n && s[left] == '0') left++;
        while(right >= 0 && s[right] == '1') right--;

        if(left > right){
            cout << "Bob\n";
            continue;
        }

        int count = 1;
        for(int i = left; i < right; i++){
            if(s[i + 1] == s[i]) count++;
            else{
                if(count % 2 == 1) is = 0;
                count = 1;
            }
        }

        if(count % 2 == 1) is = 0;

        cout << (is ? "Bob\n" : "Alice\n");
    }
 
    return 0;
}

• Best Problem
• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Let us look at what one operation really means.

Suppose we are working with a subarray $$$[l,r]$$$, and let $$$x=a_l$$$. The first element is special because it never changes: every operation only uses earlier values to modify later positions, so the leftmost value stays fixed forever.

Now the only thing that matters is how much freedom we have for the next elements. This is where $$$\text{gcd}$$$ enters naturally. If the current prefix has $$$\text{gcd}$$$ equal to $$$g$$$, then we claim that the next element can be changed by any multiple of $$$g$$$.

Now let us focus on subarrays starting at index $$$l$$$.

As long as every element to the right of $$$a_l$$$ is divisible by $$$a_l$$$, the $$$\text{gcd}$$$ of the processed prefix remains exactly $$$a_l$$$ — because all seen values are multiples of $$$a_l$$$, and $$$a_l$$$ itself is present. So every such element can be moved by multiples of $$$a_l$$$, which means each of them can be made equal to $$$a_l$$$. Therefore, if the subarray never contains an element not divisible by $$$a_l$$$, then the whole subarray can be made constant, and the value of $$$f$$$ is $$$0$$$.

Now define $$$\text{next[l]}$$$ as the first position $$$t \gt l$$$ such that $$$a_t$$$ is not divisible by $$$a_l$$$. If no such position exists, set $$$\text{next[l]=n+1}$$$.

If such a position exists, we write

Since $$$t$$$ is the first such position, the $$$\text{gcd}$$$ of everything before it is still $$$a_l$$$, so the value at position $$$t$$$ can only move inside its residue class modulo $$$a_l$$$. Hence, the closest it can get to $$$a_l$$$ is

So the spread of the subarray can never go below $$$d$$$.

The key observation is that the first non-divisible element already fixes the answer. The lower bound $$$d$$$ obtained from this element is tight, and no later element can increase it. Therefore, once this position appears, every longer subarray starting at $$$l$$$ has the same answer $$$d$$$.

Hence, for a fixed $$$l$$$:

• for every $$$r \lt \text{next}[l]$$$, we have $$$f([a_l,\dots,a_r])=0$$$;
• for every $$$r\ge \text{next}[l]$$$, we have

So, once $$$\text{next[l]}$$$ is found, all longer subarrays starting at $$$l$$$ contribute the same value. That makes counting easy. The number of subarrays starting at $$$l$$$ that contain this position is $$$n-t+1$$$. So the contribution from index $$$l$$$ is

Now we only need to find $$$\text{next[l]}$$$ for every $$$l$$$. This can be done with a monotonic stack while scanning from left to right. The stack stores indices whose first non-divisible element has not been found yet. In detail, when we are at position $$$i$$$, if

then we have $$$i = \text{next[top]}$$$. Why? Because if any earlier position had already broken divisibility for that index, it would already have been removed from the stack. So we can finalize its contribution immediately and pop it. This way, each index is pushed once and popped once, so the whole procedure is linear.

Time Complexity: $$$\mathcal{O}(n)$$$.

Note that one can also find $$$\text{next[l]}$$$ for every index $$$l$$$ by performing binary search using a sparse table to store $$$\text{gcd}$$$, leading to an $$$\mathcal{O}(n \cdot \log n \cdot \log a)$$$ solution. These implementations are also intended to pass.

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
typedef __int128 int128;

std::ostream& operator<<(std::ostream& os, int128 t) {
    if (t == 0) return os << "0";
    if (t < 0) {
        os << "-";
        t = -t;
    }
    int a[50], i = 0;
    while (t > 0) {
        a[i++] = t % 10;
        t /= 10;
    }
    for (int j = i - 1; j >= 0; j--) {
        os << (char)(a[j] + '0');
    }
    return os;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int tt = 1;
    cin >> tt;
 
    while(tt--){
        ll n;
        cin >> n;
 
        vector<ll> a(n);
        for(auto& z : a) cin >> z;

        int128 ans = 0;
        stack<ll> s;

        for(int i = 0; i < n; i++){
            while(!s.empty() && a[i] % a[s.top()] > 0){
                ans += (int128)1 * (n - i) * min(a[i] % a[s.top()], a[s.top()] - a[i] % a[s.top()]);
                s.pop();
            }
            s.push(i);
        }

        cout << ans << '\n';
    }
 
    return 0;
}

• Best Problem
• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Excellent round

Good round

Average round

Bad round

Awful round

#include<bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, C;
        cin >> n >> C;
        int ans = 0;
        vector<int> a(n), b(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        for (int i = 0; i < n; ++i) cin >> b[i];
        bool needReorder = false;
        for (int i = 0; i < n; ++i) {
            if (a[i] < b[i]) needReorder = true;
            ans += a[i];
            ans -= b[i];
        }
        if (needReorder) {
            needReorder = false;
            ans += C;
            sort(a.begin(), a.end());
            sort(b.begin(), b.end());
            for (int i = 0; i < n; ++i) {
                if (a[i] < b[i]) {
                    needReorder = true;
                }
            }
        }
        if (needReorder) cout << "-1\n";
        else cout << ans << "\n";
    }
}

Excellent problem

Good problem

Average problem

Bad problem

Awful problem

#include <bits/stdc++.h>

using namespace std;


void solve() {
    int n;
    cin >> n;
    long long an = 0;
    for (int b = 1; b <= n; b++) {
        an += 1ll * (n / b) * (n / b);
    }
    cout << an << '\n';
}

signed main() {
    signed t_ = 1;
    cin >> t_;
    while (t_--) {
        solve();
    }
}

Excellent problem

Good problem

Average problem

Bad problem

Awful problem

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5;
vector<int> g[maxn];
int depth[maxn], dp[maxn];
long long ans[maxn];

void dfs(int v, int p = -1) {
    ans[v] = 0;
    dp[v] = depth[v];
    int m1 = depth[v], m2 = depth[v];
    for (auto u : g[v]) {
        if (u != p) {
            depth[u] = depth[v] + 1;
            dfs(u, v);
            dp[v] = max(dp[v], dp[u]);
            ans[v] += ans[u];
            if (dp[u] >= m1) {
                m2 = m1;
                m1 = dp[u];
            }  else if (dp[u] >= m2) {
                m2 = dp[u];
            }
        }
    }
    ans[v] += m2 - depth[v] + 1;
}

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int p;
        cin >> p;
        g[p - 1].push_back(i);
    }
    dfs(0);
    cout << ans[0] << '\n';
    for (int i = 0; i < n; ++i) {
        g[i].clear();
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

Excellent problem

Good problem

Average problem

Bad problem

Awful problem

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 7;

int m[maxn], A[maxn], prime[maxn], nxt[maxn];

int main() {
    for (int p = 2; p < maxn; ++p) {
        if (prime[p] == 0) {
            for (int x = p; x < maxn; x += p) {
                if (prime[x] == 0) prime[x] = p;
            }
        }
        if (prime[p / prime[p]] == prime[p]) nxt[p] = nxt[p / prime[p]];
        else nxt[p] = p / prime[p];
        m[p] = m[nxt[p]] + 1;
        A[p] = A[p / prime[p]] + 1;
    }
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << m[n] + A[n] - 1 << "\n";
    }
    return 0;
}

Excellent problem

Good problem

Average problem

Bad problem

Awful problem

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    string s;
    cin >> n >> s;
    vector<vector<int>> dp(n + 1, vector<int> (n + 1, 1e9));
    dp[0][0] = 0; 
    for (int i = 0; i < n; ++i) {
        vector<vector<int>> ndp(n + 1, vector<int> (n + 1, 1e9));
        for (int cnt_f = 0; cnt_f <= i; ++cnt_f) {
            for (int cur_s = 0; cur_s <= i; ++cur_s) {
                if (s[i] != 'T') {
                    ndp[cnt_f + 1][cur_s + 1] = min(ndp[cnt_f + 1][cur_s + 1], max(dp[cnt_f][cur_s], cur_s + 1));
                }
                if (s[i] != 'F') {
                    ndp[cnt_f][max(0, cur_s - 1)] = min(ndp[cnt_f][max(0, cur_s - 1)], dp[cnt_f][cur_s]);
                }
            }
        }
        swap(dp, ndp);
    }
    int rs = 0;
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            rs = max(rs, i - dp[i][j]);
        }
    }
    cout << rs << '\n';
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

Excellent problem

Good problem

Average problem

Bad problem

Awful problem

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int maxn = 2e6 + 1;
const ll mod = 1e9 + 7;

struct md {
    ll x;

    md(ll p) {
        x = p % mod;
    }

    md operator+(md other) {
        int p = x + other.x;
        if (p >= mod) {
            p -= mod;
        }
        if (p >= mod) {
            p %= mod;
        }
        return {p};
    }

    md operator-(md other) {
        int p = x - other.x;
        if (p < 0) {
            p += mod;
        }
        if (p < 0) {
            p = (p % mod + mod) % mod;
        }
        return {p};
    }

    md operator*(md other) {
        return {1ll * x * other.x % mod};
    }

    md operator^(int x) {
        if (x == 0) {
            return {1};
        }
        if (x % 2 == 0) {
            md p = *this ^ (x / 2);
            return {p * p};
        }
        return *this * (*this ^ (x - 1));
    }

    md operator/(md p) {
        return *this * (p ^ (mod - 2));
    }
};

vector<md> fact(1, md(1));
vector<md> rfact = fact;

void prec() {
    fact.resize(maxn, md(1));
    rfact = fact;
    for (int i = 1; i < fact.size(); ++i) {
        fact[i] = fact[i - 1] * md(i);
    }
    rfact[maxn - 1] = md(1) / fact[maxn - 1];
    for (int i = maxn - 2; i >= 0; --i) {
        rfact[i] = rfact[i + 1] * (i + 1);
    }
}

md c(int n, int k) {
    if (n < 0 || k < 0 || k > n)return md(1);
    return fact[n] * rfact[k] * rfact[n - k];
}

md catalan(int n) {
    if(n == 0){
        return 1;
    }
    return c(2 * n, n) - c(2 * n, n - 1);
}

void solve() {
    ll n, k;
    cin >> n >> k;
    k++;
    vector<ll> bits(61);
    for (int i = 0; i < 61; ++i) {
        bits[i] = k >> i & 1;
    }
    for (ll x = 60; x >= n; x--) {
        bits[x - 1] += 2 * bits[x];
        bits[x] = 0;
    }
    int sm = 0;
    for (int i = 0; i < 61; ++i) {
        sm += bits[i];
    }
    md an = catalan(sm - 1) * fact[sm];
    for (int i = 0; i < 61; ++i) {
        if (bits[i] >= 2) {
            an = an * rfact[bits[i]];
        }
    }
    cout << an.x << '\n';
}

signed main() {
    prec();
    signed t_ = 1;
    cin >> t_;
    while (t_--) {
        solve();
    }
}

Excellent problem

Good problem

Average problem

Bad problem

Awful problem

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int n;
vector<long long> a;
vector<vector<int>> adj;
vector<int> subtree_size;
long long total_good_triplets;

// 检查是否为完美平方数
bool is_perfect_square(long long x) {
    long long r = round(sqrt(x));
    return r * r == x;
}

void dfs(int u, int p) {
    subtree_size[u] = 1;
    vector<long long> comp_sizes;
    
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        subtree_size[u] += subtree_size[v];
        comp_sizes.push_back(subtree_size[v]); // 子树构成一个连通块
    }
    
    if (u != 1) {
        comp_sizes.push_back(n - subtree_size[u]); // 父亲方向的剩余部分构成一个连通块
    }
    
    // 如果当前节点是完美平方数，统计以它为核心的中位数三元组
    if (is_perfect_square(a[u])) {
        long long S1 = 0, S2 = 0, S3 = 0;
        for (long long s : comp_sizes) {
            S1 += s;
            S2 += s * s;
            S3 += s * s * s;
        }
        
        // E2 = sum_{a < b} s_a * s_b
        long long E2 = (S1 * S1 - S2) / 2;
        // E3 = sum_{a < b < c} s_a * s_b * s_c
        long long E3 = (S1 * S1 * S1 - 3 * S1 * S2 + 2 * S3) / 6;
        
        total_good_triplets += (E2 + E3);
    }
}

void solve() {
    cin >> n;
    a.resize(n + 1);
    adj.assign(n + 1, vector<int>());
    subtree_size.resize(n + 1);
    total_good_triplets = 0;
    
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    dfs(1, 0);
    cout << total_good_triplets << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <string>

using namespace std;

void print128(__int128 num) {
    if (num == 0) {
        cout << 0 << "\n";
        return;
    }
    string buf;
    while (num > 0) {
        buf += (char)('0' + (num % 10));
        num /= 10;
    }
    reverse(buf.begin(), buf.end());
    cout << buf << "\n";
}

void solve() {
    int arr_len;
    if (!(cin >> arr_len)) return;
    vector<long long> arr(arr_len + 1);
    for (int pos = 1; pos <= arr_len; ++pos) {
        cin >> arr[pos];
    }
    
    __int128 sum_total = 0;
    vector<pair<long long, int>> seg_gcd_list;
    
    for (int left_pt = arr_len; left_pt >= 1; --left_pt) {
        long long base_val = arr[left_pt];
        vector<pair<long long, int>> new_seg_gcd;
        long long curr_gcd = base_val;
        int last_seg_r = left_pt;
        
        for (auto& seg_item : seg_gcd_list) {
            long long new_g = gcd(curr_gcd, seg_item.first);
            if (new_g == curr_gcd) {
                last_seg_r = seg_item.second;
            } else {
                new_seg_gcd.push_back({curr_gcd, last_seg_r});
                curr_gcd = new_g;
                last_seg_r = seg_item.second;
            }
        }
        new_seg_gcd.push_back({curr_gcd, last_seg_r});
        seg_gcd_list.swap(new_seg_gcd);
        
        vector<pair<int, long long>> split_point_list;
        int seg_start = left_pt;
        for (int idx = 0; idx < (int)seg_gcd_list.size(); ++idx) {
            if (idx > 0) {
                split_point_list.push_back({seg_start, seg_gcd_list[idx - 1].first});
            }
            seg_start = seg_gcd_list[idx].second + 1;
        }
        
        vector<pair<long long, long long>> interval_set;
        int curr_r_begin = left_pt;
        
        for (int sp_idx = 0; sp_idx <= (int)split_point_list.size(); ++sp_idx) {
            int next_r_begin = (sp_idx < (int)split_point_list.size()) ? split_point_list[sp_idx].first : arr_len + 1;
            
            long long block_length = next_r_begin - curr_r_begin;
            if (block_length > 0) {
                long long min_diff = 0;
                if (!interval_set.empty()) {
                    vector<pair<long long, long long>> sorted_intervals = interval_set;
                    sort(sorted_intervals.begin(), sorted_intervals.end());
                    
                    long long res_min = 2e18;
                    long long max_right = base_val;
                    for (int i = 0; i < (int)sorted_intervals.size(); ++i) {
                        res_min = min(res_min, max_right - sorted_intervals[i].first);
                        max_right = max(max_right, sorted_intervals[i].second);
                    }
                    res_min = min(res_min, max_right - base_val);
                    min_diff = res_min;
                }
                sum_total += (__int128)min_diff * block_length;
            }
            
            if (sp_idx < (int)split_point_list.size()) {
                int split_pos = split_point_list[sp_idx].first;
                long long gcd_split = split_point_list[sp_idx].second;
                long long num_val = arr[split_pos];
                long long rem_diff = (base_val % gcd_split - num_val % gcd_split + gcd_split) % gcd_split;
                if (rem_diff > 0) {
                    long long l_bound = base_val - rem_diff;
                    long long r_bound = base_val - rem_diff + gcd_split;
                    interval_set.push_back({l_bound, r_bound});
                }
            }
            curr_r_begin = next_r_begin;
        }
    }
    print128(sum_total);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int test_cnt;
    if (cin >> test_cnt) {
        while (test_cnt--) {
            solve();
        }
    }
    return 0;
}

// using namespace std;

// bool isSquare(long long x){
//     if(x < 0) return false;
//     long long r = round(sqrt(x));
//     return r * r == x;
// }

// void solve(){
//     int n;
//     cin >> n;

//     vector<long long> a(n + 1);
//     for(int i = 1; i <= n; i++){
//         cin >> a[i];
//     }

//     vector<vector<int>> adj(n + 1);
//     for(int i = 0; i < n - 1; i++){
//         int u, v;
//         cin >> u >> v;
//         adj[u].push_back(v);
//         adj[v].push_back(u);
//     }

//     vec
// }

// int main()
// {
//     ios_base::sync_with_stdio(false);
//     cin.tie(NULL);
//     int t;
//     cin >> t;
//     while (t--)
//     {

//     }
// }

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

// Fast check for perfect square
bool is_square(long long x) {
    if (x < 0) return false;
    long long r = round(sqrt(x));
    return r * r == x;
}

void solve() {
    int n;
    cin >> n;
    
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> sz(n + 1, 0);
    long long total_good_triplets = 0;

    // DFS to calculate subtree sizes and count valid triplets
    auto dfs = [&](auto& self, int u, int p) -> void {
        sz[u] = 1;
        vector<int> component_sizes;
        
        for (int v : adj[u]) {
            if (v != p) {
                self(self, v, u);
                sz[u] += sz[v];
                component_sizes.push_back(sz[v]);
            }
        }
        
        // Add the component representing the rest of the tree (if u is not the root)
        if (n - sz[u] > 0) {
            component_sizes.push_back(n - sz[u]);
        }

        // If the current node is a valid median (its value is a perfect square)
        if (is_square(a[u])) {
            long long A = 0; // Ways to pick 3 nodes from different components
            long long B = 0; // Ways to pick 2 nodes from different components (3rd node is u)
            long long sum = 0;
            long long sum_pairs = 0;
            
            // Calculate combinations dynamically to maintain O(degree) complexity
            for (long long s : component_sizes) {
                A += sum_pairs * s;
                sum_pairs += sum * s;
                B += sum * s;
                sum += s;
            }
            total_good_triplets += (A + B);
        }
    };

    dfs(dfs, 1, 0);
    cout << total_good_triplets << "\n";
}

int main() {
    // Optimize standard I/O operations for competitive programming
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

Consider each binary bit independently.

Think about a greedy approach.

/*
author: Yuneko

time: 2026/5/5

contest:

Tips:

RE, MLE?
greedy, dp?
natural time?
map, umap?
giveup rating, get score.
brute force, right solution?
%mod? std/run/maker/checker?
add bruteforce?
clear?
double, long double?
O(n)? O(n^2)!
make data!

last but not least.

bruteforce -> SegTree?
Think more.
*/
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include<bits/stdc++.h>
using namespace std;
//#define map unordered_map
#define re register
#define ll long long
#define cll const ll
#define forl(i,a,b) for(re ll (i)=(a);i<=(b);(i)++)
#define forr(i,a,b) for(re ll (i)=(a);i>=(b);(i)--)
#define forll(i,a,b,c) for(re ll (i)=(a);i<=(b);(i)+=(c))
#define forrr(i,a,b,c) for(re ll (i)=(a);i>=(b);(i)-=(c))
#define forL(i,a,b,c) for(re ll (i)=(a);((i)<=(b)) && (c);(i)++)
#define forR(i,a,b,c) for(re ll (i)=(a);((i)>=(b)) && (c);(i)--)
#define forLL(i,a,b,c,d) for(re ll (i)=(a);((i)<=(b)) && (d);(i)+=(c))
#define forRR(i,a,b,c,d) for(re ll (i)=(a);((i)>=(b)) && (d);(i)-=(c))
#define pii pair<ll,ll>
#define mid ((l+r)>>1)
#define lowbit(x) ((x)&-(x))
#define pb push_back
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
#define db long double
#define ull unsigned long long
#define lcm(x,y) (1ll*(x)/__gcd(x,y)*(y))
#define Sum(x,y) (1ll*((x)+(y))*((y)-(x)+1)/2)
#define x first
#define y second
#define aty cout<<"Yes\n";
#define atn cout<<"No\n";
#define cfy cout<<"YES\n";
#define cfn cout<<"NO\n";
#define xxy cout<<"yes\n";
#define xxn cout<<"no\n";
#define printcf(x) x?cout<<"YES\n":cout<<"NO\n";
#define printat(x) x?cout<<"Yes\n":cout<<"No\n";
#define printxx(x) x?cout<<"yes\n":cout<<"no\n";
#define maxqueue priority_queue<ll>
#define minqueue priority_queue<ll,vector<ll>,greater<ll>>
#define bug1 cout<<"bug1,AWaDa?\n";
#define bug2 cout<<"bug2,AWaDa!\n";
#define bug3 cout<<"bug3,AKTang?\n";
#define bug4 cout<<"bug4,AKTang!\n";
#define IM (ll)1e9
#define LM (ll)1e18
#define MIM (ll)-1e9
#define MLM (ll)-1e18
#define sort stable_sort
ll rd(ll&x){cin>>x;return x;}ll rd(){ll x;cin>>x;return x;}
ll pw(ll x,ll y,ll mod){if(mod==1)return 0;if(y==0)return 1;if(x==0)return 0;ll an=1,tmp=x;while(y){if(y&1)an=(an*tmp)%mod;tmp=(tmp*tmp)%mod;y>>=1;}return an;}
ll pw(ll x){return 1ll<<x;}
template<typename T1,typename T2>bool Max(T1&x,T2 y){if(y>x)return x=y,1;return 0;}template<typename T1,typename T2>bool Min(T1&x,T2 y){if(y<x)return x=y,1;return 0;}ll Ss=chrono::steady_clock::now().time_since_epoch().count();mt19937_64 Apple(Ss);ll rand_lr(ll l,ll r){return Apple()%(r-l+1)+l;}
cll mod=1e9+7,N=300010;ll fac[N],inv[N];void init(){fac[0]=1;forl(i,1,N-5)fac[i]=i*fac[i-1],fac[i]%=mod;inv[N-5]=pw(fac[N-5],mod-2,mod);forr(i,N-5,1)inv[i-1]=inv[i]*i%mod;}ll C(ll n,ll m){if(n<m || m<0)return 0;return (fac[n]%mod)*(inv[n-m]*inv[m]%mod)%mod;}
void add(ll&x,ll y){x=((x+y)%mod+mod)%mod;}void del(ll&x,ll y){x=(x%mod-y%mod+mod)%mod;}
ll _t_;
struct BIT{
    ll maxn;
    ll tree[1000010];
    void clear(ll l){
        forl(i,0,l)
            tree[i]=0;
    }
    void add(ll x,ll y){
        for(;x<=maxn;x+=lowbit(x))
            tree[x]+=y;
    }
    ll query(ll x){
        ll S=0;
        for(;x;x-=lowbit(x))
            S+=tree[x];
        return S;
    }
    ll query(ll l,ll r){
        return query(r)-query(l-1);
    }
};
ll lg[1000010];
void Init(){
    forl(i,2,1e6+5)
        lg[i]=lg[i>>1]+1;
}
//xw
ll n,m;
ll ans;
//st
void _clear(){}
void solve()
{
    _clear();
	cin>>n>>m;
	forl(i,0,30)
	{
		ll num=min(n/pw(i),m);
		ans+=num,n-=num*pw(i);
	}
	cout<<ans<<endl;
	ans=0;
}
int main()
{
    Init();
//    freopen("tst.txt","r",stdin);
//    freopen("sans.txt","w",stdout);
    IOS;
    _t_=1;
    cin>>_t_;
    while(_t_--)
        solve();
    QwQ;
}

Try some special cases, such as $$$r=c=2$$$, $$$n=r$$$, or $$$m=c$$$, etc.

In terms of systems of equations, the given problem fixes for us the parities of at most (and exactly) $$$(n-r+1)\cdot(m-c+1)$$$ cells (by giving us a system of equations to solve with that many equations). What this means is that, if we are to fill an upper border of thickness $$$r-1$$$ and a left border of thickness of $$$c-1$$$, then every cell from that point onward is determined uniquely by some equation (Tip: imagine how this pans out for a $$$2\times2$$$ matrix; after filling the first row and left column arbitrarily, cell (2,2) is uniquely determined, then (2,3), and so on).

Therefore, the answer is $$$2^{nm - (n-r+1)(m-c+1)}$$$.

#include<bits/stdc++.h>
#define cint const int
#define uint unsigned int
#define cuint const unsigned int
#define ll long long
#define cll const long long
#define ull unsigned long long
#define cull const unsigned long long
using namespace std;
namespace FastIO
{
    const int BUF_SIZE=1<<20;
    char in_buf[BUF_SIZE],out_buf[BUF_SIZE];
    char* in_ptr=in_buf+BUF_SIZE;
    char* out_ptr=out_buf;
    char get_char()
    {
        if(in_ptr==in_buf+BUF_SIZE)
        {
            in_ptr=in_buf;
            fread(in_buf,1,BUF_SIZE,stdin);
        }
        return *in_ptr++;
    }
    void put_char(char c)
    {
        if(out_ptr==out_buf+BUF_SIZE)
        {
            fwrite(out_buf,1,BUF_SIZE,stdout);
            out_ptr=out_buf;
        }
        *out_ptr++=c;
    }
    struct Flusher
    {
        ~Flusher()
        {
            if(out_ptr!=out_buf)
            {
                fwrite(out_buf,1,out_ptr-out_buf,stdout);
            }
        }
    } flusher;
}
#define getchar FastIO::get_char
#define putchar FastIO::put_char
inline int read()
{
    int x=0;
    bool zf=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            zf=0;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return zf?x:-x;
}
void print(cint x)
{
    if(x==0)
    {
        putchar('0');
        return;
    }
    char buf[12];
    int len=0,y=x;
    if(y<0)
    {
        putchar('-');
        y=-y;
    }
    while(y)
    {
        buf[len++]=(y%10)+'0';
        y/=10;
    }
    while(len--)
    {
        putchar(buf[len]);
    }
}
inline void princh(cint x,const char ch)
{
    print(x);
    putchar(ch);
}
cint mod=998244353;
int n,m,r,c;
int qpow(int x,int y)
{
    int res=1;
    while(y)
    {
        if(y&1)res=1ll*res*x%mod;
        x=1ll*x*x%mod;
        y>>=1;
    }
    return res;
}
void solve()
{
    n=read();
    m=read();
    r=read();
    c=read();
    princh(qpow(2,(1ll*n*(c-1)+1ll*m*(r-1)-1ll*(c-1)*(r-1))%(mod-1)),'\n');
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    int T=read();
    while(T--)solve();
    return 0;
}

Try working through some cases by hand. You may notice that whenever there is more than one non-zero number, the first player wins. Then think about why this is true.

#include<bits/stdc++.h>
#define cint const int
#define uint unsigned int
#define cuint const unsigned int
#define ll long long
#define cll const long long
#define ull unsigned long long
#define cull const unsigned long long
using namespace std;
namespace FastIO
{
    const int BUF_SIZE=1<<20;
    char in_buf[BUF_SIZE],out_buf[BUF_SIZE];
    char* in_ptr=in_buf+BUF_SIZE;
    char* out_ptr=out_buf;
    char get_char()
    {
        if(in_ptr==in_buf+BUF_SIZE)
        {
            in_ptr=in_buf;
            fread(in_buf,1,BUF_SIZE,stdin);
        }
        return *in_ptr++;
    }
    void put_char(char c)
    {
        if(out_ptr==out_buf+BUF_SIZE)
        {
            fwrite(out_buf,1,BUF_SIZE,stdout);
            out_ptr=out_buf;
        }
        *out_ptr++=c;
    }
    struct Flusher
    {
        ~Flusher()
        {
            if(out_ptr!=out_buf)
            {
                fwrite(out_buf,1,out_ptr-out_buf,stdout);
            }
        }
    } flusher;
}
#define getchar FastIO::get_char
#define putchar FastIO::put_char
inline int read()
{
    int x=0;
    bool zf=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            zf=0;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return zf?x:-x;
}
void print(cint x)
{
    if(x==0)
    {
        putchar('0');
        return;
    }
    char buf[12];
    int len=0,y=x;
    if(y<0)
    {
        putchar('-');
        y=-y;
    }
    while(y)
    {
        buf[len++]=(y%10)+'0';
        y/=10;
    }
    while(len--)
    {
        putchar(buf[len]);
    }
}
inline void princh(cint x,const char ch)
{
    print(x);
    putchar(ch);
}
cint N=1e6;
int n,a[N+1],s,ans;
void solve()
{
    n=read();
    s=0;
    ans=0;
    for(int i=1;i<=n;++i)s^=(a[i]=read());
    if(n==1)
    {
        princh(0,'\n');
        return;
    }
    if(!s)
    {
        princh(1,'\n');
        return;
    }
    for(int i=1;i<=n;++i)
    {
        if((s^a[i])<a[i])++ans;
    }
    princh(ans,'\n');
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    int T=read();
    while(T--)solve();
    return 0;
}

How does everyone’s contribution change when you give a gift to someone?

#include<bits/stdc++.h>
#define cint const int
#define uint unsigned int
#define cuint const unsigned int
#define ll long long
#define cll const long long
#define ull unsigned long long
#define cull const unsigned long long
#define sh short
#define csh const short
#define ush unsigned short
#define cush const unsigned short
using namespace std;
namespace FastIO
{
    const int BUF_SIZE=1<<20;
    char in_buf[BUF_SIZE],out_buf[BUF_SIZE];
    char* in_ptr=in_buf+BUF_SIZE;
    char* out_ptr=out_buf;
    char get_char()
    {
        if(in_ptr==in_buf+BUF_SIZE)
        {
            in_ptr=in_buf;
            fread(in_buf,1,BUF_SIZE,stdin);
        }
        return *in_ptr++;
    }
    void put_char(char c)
    {
        if(out_ptr==out_buf+BUF_SIZE)
        {
            fwrite(out_buf,1,BUF_SIZE,stdout);
            out_ptr=out_buf;
        }
        *out_ptr++=c;
    }
    struct Flusher
    {
        ~Flusher()
        {
            if(out_ptr!=out_buf)
            {
                fwrite(out_buf,1,out_ptr-out_buf,stdout);
            }
        }
    } flusher;
}
#define getchar FastIO::get_char
#define putchar FastIO::put_char
inline int read()
{
    int x=0;
    bool zf=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            zf=0;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return zf?x:-x;
}
void print(cll x)
{
    if(x==0)
    {
        putchar('0');
        return;
    }
    char buf[20];
    int len=0;
    ll y=x;
    if(y<0)
    {
        putchar('-');
        y=-y;
    }
    while(y)
    {
        buf[len++]=(y%10)+'0';
        y/=10;
    }
    while(len--)
    {
        putchar(buf[len]);
    }
}
inline void princh(cll x,const char ch)
{
    print(x);
    putchar(ch);
}
cint N=6e5;
int n,d;
int a[N+1];
ll s[N+1],val[N+1];
ll ans;
void solve()
{
    n=read();
    d=read();
    for(int i=1;i<=n;++i)
    {
        a[i]=a[i+n]=a[i+(n<<1)]=read();
    }
    for(int i=1;i<=n*3;++i)s[i]=s[i-1]+a[i];
    for(int i=n+1;i<=(n<<1);++i)
    {
        val[i-n]=1ll*(d<<1|1)*a[i]-(s[i+d]-s[i-d-1]);
    }
    ans=0;
    for(int i=1;i<=n;++i)ans+=max(0ll,val[i]);
    princh(ans,'\n');
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int T=read();
    while(T--)solve();
    return 0;
}

Consider determining all the numbers from back to front.

When you determine a number, subtract $$$1$$$ from all previous values that are greater than this number. This way, all $$$p$$$ values decrease by one, while all $$$s$$$ values remain unchanged. Now you only need to solve the problem of determining the last number.

#include<bits/stdc++.h>
#define cint const int
#define uint unsigned int
#define cuint const unsigned int
#define ll long long
#define cll const long long
#define ull unsigned long long
#define cull const unsigned long long
#define sh short
#define csh const short
#define ush unsigned short
#define cush const unsigned short
using namespace std;
namespace FastIO
{
    const int BUF_SIZE=1<<20;
    char in_buf[BUF_SIZE],out_buf[BUF_SIZE];
    char* in_ptr=in_buf+BUF_SIZE;
    char* out_ptr=out_buf;
    char get_char()
    {
        if(in_ptr==in_buf+BUF_SIZE)
        {
            in_ptr=in_buf;
            fread(in_buf,1,BUF_SIZE,stdin);
        }
        return *in_ptr++;
    }
    void put_char(char c)
    {
        if(out_ptr==out_buf+BUF_SIZE)
        {
            fwrite(out_buf,1,BUF_SIZE,stdout);
            out_ptr=out_buf;
        }
        *out_ptr++=c;
    }
    struct Flusher
    {
        ~Flusher()
        {
            if(out_ptr!=out_buf)
            {
                fwrite(out_buf,1,out_ptr-out_buf,stdout);
            }
        }
    } flusher;
}
#define getchar FastIO::get_char
#define putchar FastIO::put_char
inline ll read()
{
    ll x=0;
    bool zf=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            zf=0;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return zf?x:-x;
}
void print(cint x)
{
    if(x==0)
    {
        putchar('0');
        return;
    }
    char buf[12];
    int len=0,y=x;
    if(y<0)
    {
        putchar('-');
        y=-y;
    }
    while(y)
    {
        buf[len++]=(y%10)+'0';
        y/=10;
    }
    while(len--)
    {
        putchar(buf[len]);
    }
}
inline void princh(cint x,const char ch)
{
    print(x);
    putchar(ch);
}
cint N=1e6;
int n;
ll val[N+1];
char type[N+1];
int ans[N+1];
struct Binary_Index_Tree{
    int a[N+1];
    void clear()
    {
        for(int i=1;i<=n;++i)a[i]=0;
    }
    inline void add(cint x,cint y)
    {
        for(int i=x;i<=n;i+=(i&-i))a[i]+=y;
    }
    inline int ask(cint x)
    {
        int s=0;
        for(int i=x;i;i-=(i&-i))s+=a[i];
        return s;
    }
    inline int find(int x)
    {
        int res=0;
        for(int len=1<<__lg(n);len;len>>=1)
        {
            if(res+len>n)continue;
            if(a[res+len]<=x)
            {
                res+=len;
                x-=a[res];
            }
        }
        return res+1;
    }
}T;
int lst[N+1];
void solve()
{
    n=read();
    T.clear();
    for(int i=1;i<=n;++i)
    {
        char ch=getchar();
        while(ch!='p'&&ch!='s')ch=getchar();
        type[i]=ch;
        val[i]=read();
        if(type[i]=='p')ans[i]=val[i];
        else val[i]=1ll*i*(i-1)/2-val[i];
    }
    for(int i=1;i<=n;++i)lst[i]=(type[i]=='s'?i:lst[i-1]);
    for(int i=1;i<=n;++i)T.add(i,1);
    for(int i=lst[n]+1;i<=n;++i)T.add(ans[i],-1);
    for(int i=lst[n];i;i=lst[i-1])
    {
        cint p=lst[i-1];
        ll d=val[i]-val[p];
        for(int j=i-1;j>p;--j)
        {
            d-=T.ask(ans[j]-1);
            T.add(ans[j],-1);
        }
        d+=i-p-1;
        for(int j=i-1;j>p;--j)T.add(ans[j],2);
        ans[i]=T.find(d);
        for(int j=i-1;j>p;--j)T.add(ans[j],-2);
        T.add(ans[i],-1);
    }
    for(int i=1;i<=n;++i)
    {
        princh(ans[i]," \n"[i==n]);
    }
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int T=read();
    while(T--)solve();
    return 0;
}

By symmetry, all vertices are equivalent. Therefore, we only need to calculate the number of graphs in which a specific set is successful, and then multiply by $$$\binom{n}{m}$$$.

Let the nodes in the set be key nodes and the remaining nodes be non-key nodes. Consider the condition for the set to be successful and use the Principle of Inclusion-Exclusion to handle these conditions.

You might need to calculate the following: $$$n$$$ vertices form a set of disjoint cycles without self-loops. If there are $$$k$$$ cycles, the contribution is $$$(-1)^k$$$. Find the sum of contributions over all possible configurations.

The answer is $$$1-n$$$, which you can try to prove.

Use the Binomial Theorem to simplify the sum.

#include <bits/stdc++.h>
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)
#define CUP(i, l, r) for (int i = (l); i < (r); ++ i)
#define fi first
#define se second
#define pb emplace_back
#define mems(x, v) memset((x), (v), sizeof(x))
#define memc(x, y) memcpy((x), (y), sizeof(x))
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define ppc(x) __builtin_popcount(x)
#define ctz(x) __builtin_ctz(x)
#define clz(x) __builtin_clz(x)
using namespace std;
namespace math {
	typedef long long LL;
	template <class T> T qpow(T a, LL b) { if (!b) return {1}; T rs = a; b --; for (; b; b >>= 1, a = a * a) if (b & 1) rs = rs * a; return rs; }
	LL mul(LL a, LL b, LL p) { LL rs = a * b - LL(1.L * a * b / p) * p; rs %= p; if (rs < 0) rs += p; return rs; }
	template <unsigned P = 0> struct mint {
		unsigned v; static unsigned mod; mint() = default;
		template <class T> mint(T x) { x %= (int)getmod(), v = x < 0 ? x + getmod() : x; }
		constexpr static unsigned getmod() { if (P > 0) return P; else return mod; }
		static void setmod(unsigned m) { mod = m; }
		mint operator + () const { return *this; }
		mint operator - () const { return mint(0) - *this; }
		mint inv() const { return assert(v), qpow(*this, getmod() - 2); }
		int val() const { return v; }
		mint &operator += (const mint &q) { if (v += q.v, v >= getmod()) v -= getmod(); return *this; }
		mint &operator -= (const mint &q) { if (v -= q.v, v >= getmod()) v += getmod(); return *this; }
		mint &operator *= (const mint &q) { v = 1ull * v * q.v % getmod(); return *this; }
		mint &operator /= (const mint &q) { return *this *= q.inv(); }
		friend mint operator + (mint p, const mint &q) { return p += q; }
		friend mint operator - (mint p, const mint &q) { return p -= q; }
		friend mint operator * (mint p, const mint &q) { return p *= q; }
		friend mint operator / (mint p, const mint &q) { return p /= q; }
		friend bool operator == (const mint &p, const mint &q) { return p.v == q.v; }
		friend bool operator != (const mint &p, const mint &q) { return p.v != q.v; }
		friend bool operator < (const mint &p, const mint &q) { return p.v < q.v; }
		friend bool operator > (const mint &p, const mint &q) { return p.v > q.v; }
		friend bool operator <= (const mint &p, const mint &q) { return p.v <= q.v; }
		friend bool operator >= (const mint &p, const mint &q) { return p.v >= q.v; }
		friend istream &operator >> (istream &is, mint &a) { LL x; is >> x, a = x; return is; }
		friend ostream &operator << (ostream &os, const mint &a) { os << a.v; return os; }
	};
	template <> unsigned mint<0>::mod = 998244353;
	template <typename MI>
	struct Comb {
		#define P MI::getmod()
		vector<MI> fc, ifc;
		void init(int n) {
			fc.resize(n + 1), ifc.resize(n + 1), fc[0] = 1;
			REP(i, 1, n) fc[i] = fc[i - 1] * i;
			ifc[n] = fc[n].inv();
			DEP(i, n, 1) ifc[i - 1] = ifc[i] * i;
		}
		MI operator () (LL n, LL m) {
			if (m > n || m < 0 || n < 0) return 0;
			if (n < P && m < P) { assert(n < SZ(fc)); return fc[n] * ifc[m] * ifc[n - m]; }
			return (!n ? 1 : (*this)(n / P, m / P) * (*this)(n % P, m % P));
		}
		#undef P
	};
	namespace Z {
		const int mod = 998244353;
		using MI = mint<mod>; using math::qpow; Comb<MI> C;
		MI fac(int x) { assert(x >= 0 && x < SZ(C.fc)); return C.fc[x]; }
		MI ifc(int x) { assert(x >= 0 && x < SZ(C.ifc)); return C.ifc[x]; }
		MI inv(int x) { assert(x && x < SZ(C.fc)); return C.ifc[x] * C.fc[x - 1]; }
		MI sab(int x, int y) { return (!y ? !x : C(x + y - 1, y - 1)); }
	}
}
namespace Milkcat {
	using namespace math::Z;
	typedef long long LL;
	typedef pair<LL, LL> pii;
	const int N = 1e7 + 5;
	int n, m, t, v[N]; MI g[N];
	void sieve(int n, int k, MI* f) {
		vector<int> p; fill_n(v + 1, n, 0), f[1] = 1;
		REP(i, 2, n) {
			if (!v[i]) p.pb(i), f[i] = qpow((MI)i, k);
			for (int j : p) {
				if (i * j <= n) f[i * j] = f[i] * f[j], v[i * j] = 1;
				if (i * j > n || i % j == 0) break;
			}
		}
	}
	MI slv2(int n, int m) {
		MI rs = 0;
		REP(i, 0, n - m)
			rs += g[n - i - 1] * C(n - m, i) * (i & 1 ? -1 : 1);
		return rs * (n - 1);
	}
	int main() {
		cin >> t, C.init(1e6);
		while (t --) {
			cin >> n >> m, sieve(n, n - 1, g);
			cout << slv2(n, m) * C(n, m) << '\n';
		}
		return 0;
	}
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int T = 1;
	while (T --) Milkcat::main();
	return 0;
}

Notice that the problem can be transformed as follows: the $$$i$$$-th edge appears during the time interval $$$[\mathrm{low}_i, w_i]$$$. For each vertex, compute the maximum value of the departure time plus the weight of the destination vertex.

Consider doing the transitions from back to front.

We only need to support the following operations:

• Add and delete edges;
• Query the maximum value in a connected component;
• Take the max of all weights in a connected component with a given number.

Consider modifying the dynamic graph connectivity approach.

#include<bits/stdc++.h>
#define cint const int
#define uint unsigned int
#define cuint const unsigned int
#define ll long long
#define cll const long long
#define ull unsigned long long
#define cull const unsigned long long
using namespace std;
namespace FastIO
{
    const int BUF_SIZE=1<<20;
    char in_buf[BUF_SIZE],out_buf[BUF_SIZE];
    char* in_ptr=in_buf+BUF_SIZE;
    char* out_ptr=out_buf;
    char get_char()
    {
        if(in_ptr==in_buf+BUF_SIZE)
        {
            in_ptr=in_buf;
            fread(in_buf,1,BUF_SIZE,stdin);
        }
        return *in_ptr++;
    }
    void put_char(char c)
    {
        if(out_ptr==out_buf+BUF_SIZE)
        {
            fwrite(out_buf,1,BUF_SIZE,stdout);
            out_ptr=out_buf;
        }
        *out_ptr++=c;
    }
    struct Flusher
    {
        ~Flusher()
        {
            if(out_ptr!=out_buf)
            {
                fwrite(out_buf,1,out_ptr-out_buf,stdout);
            }
        }
    } flusher;
}
#define getchar FastIO::get_char
#define putchar FastIO::put_char
inline int read()
{
    int x=0;
    bool zf=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            zf=0;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return zf?x:-x;
}
void print(cint x)
{
    if(x==0)
    {
        putchar('0');
        return;
    }
    char buf[12];
    int len=0,y=x;
    if(y<0)
    {
        putchar('-');
        y=-y;
    }
    while(y)
    {
        buf[len++]=(y%10)+'0';
        y/=10;
    }
    while(len--)
    {
        putchar(buf[len]);
    }
}
inline void princh(cint x,const char ch)
{
    print(x);
    putchar(ch);
}
cint N=5e5,M=5e5,H=20;
int n,m;
int val[N+1];
int eu[M+1],ev[M+1],low[M+1],lim[M+1];
int tl[M+1],tr[M+1];
struct dx{
    int idx,val;
}c[M<<1|1];
struct edge{
    int u,v,l,r;
};
vector<edge>E,EL[H+1],ER[H+1];
struct info{
    int t,u;
}mdf[M+1];
int tag[N+(M<<2|1)],mx[N+(M<<2|1)];
int fa[N+(M<<2|1)];
int tot;
int top[N+(M<<2|1)];
int head[N+(M<<2|1)];
struct et{
    int to,nxt;
}ve[M<<2|1];
int ct;
inline void add_edge(cint u,cint v)
{
    ve[++ct]={v,head[u]};
    head[u]=ct;
    ve[++ct]={u,head[v]};
    head[v]=ct;
}
inline int newv()
{
    ++tot;
    tag[tot]=-1;
    mx[tot]=fa[tot]=0;
    return tot;
}
struct stck{
    int a[N+1],t;
    inline void clear(){t=0;}
    inline int top(){return a[t];}
    inline void pop(){--t;}
    inline void push(cint x){a[++t]=x;}
    inline bool empty(){return (t==0);}
}st;
void dfs(cint u)
{
    top[u]=u;
    st.clear();
    st.push(u);
    while(!st.empty())
    {
        cint s=st.top();
        st.pop();
        for(int i=head[s];i;i=ve[i].nxt)
        {
            cint v=ve[i].to;
            if(top[v])continue;
            top[v]=u;
            st.push(v);
        }
    }
}
void update(cint h,cint l,cint r,vector<edge>&E,int m,cint vl,cint vr)
{
    if(E.empty())
    {
        for(int i=1;i<=m;++i)
        {
            tag[mdf[i].u]=max(tag[mdf[i].u],mx[mdf[i].u]+c[l].val);
        }
        return;
    }
    cint mid=l+r>>1;
    EL[h].clear();
    ER[h].clear();
    for(int i=vl;i<=vr;++i)
    {
        head[i]=top[i]=fa[i]=0;
    }
    ct=0;
    for(edge &e:E)
    {
        if(e.l<=l&&e.r>=r)
        {
            add_edge(e.u,e.v);
        }
        else
        {
            if(e.l<=mid)EL[h].push_back(e);
            if(e.r>mid)ER[h].push_back(e);
        }
    }
    for(int i=vl;i<=vr;++i)
    {
        if(!top[i])dfs(i);
    }
    if(l==r)
    {
        for(int i=vl;i<=vr;++i)mx[top[i]]=max(mx[top[i]],mx[i]);
        for(int i=1;i<=m;++i)
        {
            cint u=top[mdf[i].u];
            tag[u]=max(tag[u],mx[u]+c[l].val);
        }
        for(int i=vl;i<=vr;++i)
        {
            tag[i]=max(tag[i],tag[top[i]]);
            mx[i]=max(mx[i],mx[top[i]]);
        }
        return;
    }
    cint tmp=tot;
    for(edge &e:ER[h])
    {
        cint u=top[e.u],v=top[e.v];
        if(!fa[u])fa[u]=newv();
        if(!fa[v])fa[v]=newv();
        e.u=fa[u];
        e.v=fa[v];
    }
    int pm=0;
    for(int i=1;i<=m;++i)
    {
        info &p=mdf[i];
        if(p.t>mid)
        {
            cint u=top[p.u];
            if(!fa[u])fa[u]=newv();
            p.u=fa[u];
            swap(p,mdf[++pm]);
        }
    }
    for(int i=vl;i<=vr;++i)
    {
        cint u=fa[top[i]];
        if(u)mx[u]=max(mx[u],mx[i]);
    }
    update(h+1,mid+1,r,ER[h],pm,tmp+1,tot);
    for(int i=vl;i<=vr;++i)
    {
        cint u=fa[top[i]];
        if(u)mx[i]=max(mx[i],mx[u]),tag[i]=max(tag[i],tag[u]);
    }
    tot=tmp;
    for(int i=vl;i<=vr;++i)fa[i]=0;
    for(edge &e:EL[h])
    {
        cint u=top[e.u],v=top[e.v];
        if(!fa[u])fa[u]=newv();
        if(!fa[v])fa[v]=newv();
        e.u=fa[u];
        e.v=fa[v];
    }
    for(int i=pm+1;i<=m;++i)
    {
        info &p=mdf[i];
        cint u=top[p.u];
        if(!fa[u])fa[u]=newv();
        p.u=fa[u];
        swap(p,mdf[i-pm]);
    }
    pm=m-pm;
    for(int i=vl;i<=vr;++i)
    {
        cint u=fa[top[i]];
        if(u)mx[u]=max(mx[u],mx[i]);
    }
    update(h+1,l,mid,EL[h],pm,tmp+1,tot);
    for(int i=vl;i<=vr;++i)
    {
        cint u=fa[top[i]];
        if(u)mx[i]=max(mx[i],mx[u]),tag[i]=max(tag[i],tag[u]);
    }
    tot=tmp;
}
void solve()
{
    tag[0]=-1;
    tot=n=read();
    m=read();
    for(int i=1;i<=n;++i)val[i]=read(),tag[i]=-1,mx[i]=val[i];
    for(int i=1;i<=m;++i)
    {
        eu[i]=read(),ev[i]=read(),lim[i]=read(),low[i]=read();
        c[i]={i,lim[i]};
        c[i+m]={i+m,low[i]};
    }
    sort(c+1,c+(m<<1|1),[&](dx p,dx q){return (p.val==q.val?p.idx>q.idx:p.val<q.val);});
    for(int i=1;i<=(m<<1);++i)
    {
        if(c[i].idx>m)tl[c[i].idx-m]=i;
        else tr[c[i].idx]=i;
    }
    E.clear();
    for(int i=1;i<=m;++i)
    {
        E.push_back({eu[i],ev[i],tl[i],tr[i]});
        mdf[i]={tr[i],eu[i]};
    }
    if(m)update(0,1,m<<1,E,m,1,n);
    for(int i=1;i<=n;++i)princh(tag[i]," \n"[i==n]);
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    int T=read();
    while(T--)solve();
    return 0;
}

Consider the case where $$$l_i=0$$$.

Just Consider the most straightforward DP approach, and then try to find some patterns.

Try transforming the modulo $$$2$$$ counting DP into a game and solve it.

You should already know the answer for $$$l_i=0$$$; try using the Principle of Inclusion-Exclusion to count.

Enumerate which element is strictly greater than half of the total sum.

You should already know the $$$O(nm/w)$$$ algorithm. Consider that, under modulo $$$2$$$, we have $$$(1+x^k)^2=1+x^{2k}$$$.

#include <bits/stdc++.h>
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)
#define CUP(i, l, r) for (int i = (l); i < (r); ++ i)
#define fi first
#define se second
#define pb emplace_back
#define mems(x, v) memset((x), (v), sizeof(x))
#define memc(x, y) memcpy((x), (y), sizeof(x))
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define ppc(x) __builtin_popcount(x)
#define ctz(x) __builtin_ctz(x)
#define clz(x) __builtin_clz(x)
using namespace std;
namespace Milkcat {
	typedef long long LL;
	typedef pair<LL, LL> pii;
	const int N = 2e6 + 5, M = 2e5 + 5;
	int n, m, rs, d, p, q, l[N], r[N], c[M];
	bitset<M> f;
	int val(int x) { x -= d; return (x >= 0 && x <= m ? f[x] : 0); }
	int main() {
		cin >> n;
		REP(i, 1, n)
			cin >> l[i] >> r[i], m = max(m, r[i]);
		REP(i, 1, n) {
			if (!l[i]) d = min(d + r[i], (int)1e9);
			else d = min(d + l[i] - 1, (int)1e9), c[r[i] - l[i] + 1] ++;
		}
		f = 1;
		REP(i, 1, m) {
			if (i * 2 <= m) c[i * 2] += c[i] >> 1;
			if (c[i] & 1) f ^= f << i;
		}
		REP(i, 2, m) f[i] = f[i] ^ f[i - 2];
		REP(i, 1, n) {
			if (!l[i]) rs ^= val(r[i] * 2 - 2), p ^= r[i] & 1;
			else rs ^= val(l[i] + r[i] - 1 - 2), q += ((l[i] & 1) == (r[i] & 1) ? 1 : 2);
		}
		cout << (rs ^ (!q ? !p : (q < 2))) << '\n';
		REP(i, 1, m) c[i] = 0;
		m = rs = d = p = q = 0;
		return 0;
	}
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int T = 1; cin >> T;
	while (T --) Milkcat::main();
	return 0;
}

Starting in August 2026, AtCoder will begin licensing user-submitted source code to AI companies for use as AI training data.

The licensed data will include not only submissions made after the start of the program, but also source code that has already been submitted in the past. However, any submission for which AI training has been explicitly opted out will not be included.

In connection with this change, we have updated our Terms of Service and Privacy Policy. We believe this data licensing program is necessary to ensure that AtCoder can continue providing programming contests free of charge in the future. At the same time, we do not believe that users should be required to allow their submissions to be used for AI training simply in order to participate in contests.

For this reason, we have introduced an opt-out setting for AI training use that applies to all submissions, as well as a separate opt-out setting that can be configured on a per-submission basis.

We have also provided a one-month grace period during which users can review and update their preferences.

If you do not want your submitted source code to be used for AI training or included in the licensing program, please make sure to update your settings before the grace period ends. For instructions on how to change your settings, please see the following page:

How to Opt Out of AI Training (Japanese) - AtCoderInfo (https://info.atcoder.jp/overview/about/ai-training-opt-out)

AtCoder will continue pursuing new initiatives to ensure that our programming contests remain free for everyone.

Thank you, as always, for your continued support of AtCoder.

https://atcoder.jp/settings/deny_learning