Even Dimensions: If $$$n$$$ or $$$m$$$ is even, the grid can be perfectly tiled using only $$$1 \times 2$$$ I-Beams, making the answer YES.Thin Grids: If $$$n=1$$$ or $$$m=1$$$ (and the other is odd), the C-Core module cannot fit physically as it requires a $$$2 \times 3$$$ footprint, leaving an odd area that $$$1 \times 2$$$ beams cannot fill (NO).Small Odd Grids ($$$3 \times 3$$$): Although the area is 9, placing a $$$2 \times 3$$$ footprint C-Core in a $$$3 \times 3$$$ space creates geometric obstructions that prevent the remaining 4 cells from forming two valid $$$1 \times 2$$$ blocks (NO).Large Odd Grids: For all other odd $$$n, m \ge 3$$$, there is sufficient "maneuvering room" to place one C-Core such that the remaining even area is contiguous and tileable by I-Beams (YES).

#include <bits/stdc++.h>
using namespace std;
 #define ll long long int
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
    while (t--) {
     ll n,m; cin>>n>>m;
     if(n%2==0 || m%2==0) cout<<"YES"<<"\n";
     else if(n==1 || m==1) cout<<"NO"<<"\n";
     else if(n==3 && m==3) cout<<"NO"<<"\n";
      else cout<<"YES"<<"\n";
    }
}

The problem requires finding integers $$$a$$$ and $$$b$$$ such that $$$ax + b = y$$$ under the constraints $$$b \gt 0$$$ and $$$a \gt 2b$$$. By substituting $$$b = y - ax$$$ into the second inequality, we derive $$$a \gt 2(y - ax)$$$, which simplifies to $$$a(2x + 1) \gt 2y$$$, or $$$a \gt \frac{2y}{2x + 1}$$$. To find the smallest valid integer $$$a$$$, we calculate $$$a = \lfloor \frac{2y}{2x + 1} \rfloor + 1$$$. Once $$$a$$$ is determined, we calculate the corresponding $$$b = y - ax$$$; if $$$b$$$ remains strictly positive ($$$ax \lt y$$$), the pair $$$(a, b)$$$ is a valid solution, otherwise, no such pair exists because increasing $$$a$$$ further would only decrease $$$b$$$ into non-positive values. Since $$$x$$$ and $$$y$$$ can reach $$$10^{14}$$$, the product $$$a \cdot x$$$ can exceed the capacity of a 64-bit integer, necessitating the use of __int128 for overflow-safe intermediate calculations.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void solve() {
    ll x, y;
   cin>>x>>y;
    ll a = (2 * y) / (2 * x + 1) + 1;
    if ((__int128)a * x < (__int128)y) {
        ll b = y - (ll)a * x;
        cout << a << " " << b << endl;
    } 
    else {
        cout << -1 << endl;
    }
}

 

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

}

The goal is to find the maximum integer $$$R$$$ (similar to the H-index) such that at least $$$R$$$ servers have $$$R$$$ or more requests, leveraging the fact that the input is already sorted. By picking an index $$$i$$$, we know there are exactly $$$n - i$$$ servers with at least $$$requests[i]$$$ requests; therefore, we seek the largest $$$R$$$ where $$$R \le n - i$$$ and $$$R \le requests[i]$$$. Since the "count of servers" $$$(n-i)$$$ decreases as $$$i$$$ increases, while the "request value" $$$requests[i]$$$ increases, the optimal $$$R$$$ occurs at the intersection of these two constraints. The binary search efficiently locates the leftmost index $$$mid$$$ where $$$requests[mid] \ge (n - mid)$$$, allowing us to identify the maximum possible $$$R$$$ as $$$n - left$$$ in $$$O(\log n)$$$ time.

#include <bits/stdc++.h>
using namespace std;
 
int reliabilityLevel(vector<long long int>& requests) {
    
    long long int n = requests.size();
    long long int left = 0, right = n - 1;
 
    while(left <= right) {
 
        long long int mid = left + (right - left)/2;
       long long int servers = n - mid;
 
        if(requests[mid] >= servers)
            right = mid - 1;
        else
            left = mid + 1;
    }
 
    return n - left;
}
 
int main() {
   long long int t;
   cin>>t;
   while(t--){
      long long int n;
       cin>>n;
       vector <long long int> a(n);
       for(int i=0;i<n;i++){
           cin>>a[i];
       }
    //vector<int> requests = {0,1,3,5,6,8};
 
    cout << reliabilityLevel(a)<<"\n";
   }
 
}

To solve "The Gateway of 21," we use dynamic programming to find the longest subsequence that forms a number divisible by 21 while respecting the "no leading zeros" rule. We maintain a DP table of size $$$3 \times 7$$$ to track the maximum length of a subsequence for every possible combination of remainders modulo 3 and modulo 7. As we iterate through the string, a non-zero digit can either start a new sequence or extend an existing one by updating the remainders $$$( (rem3 + digit) \pmod 3, (rem7 \times 10 + digit) \pmod 7 )$$$, whereas a '0' is tracked separately as a potential single-digit solution since it cannot lead a multi-digit number. The final answer is the total string length minus the maximum length found in the dp[0][0] state (or length 1 if only a '0' is available); if no such subsequence exists, we return -1.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--){
    string s;
    if(!(cin >> s)) return 0;
    int n = (int)s.size();
 
    int dp_nz[3][7];
    for(int i=0;i<3;i++) for(int j=0;j<7;j++) dp_nz[i][j] = -1;
 
    int has_zero = 0;
 
    for(char ch : s) {
        int d = ch - '0';
 
        int new_dp[3][7];
        for(int i=0;i<3;i++) for(int j=0;j<7;j++) new_dp[i][j] = dp_nz[i][j];
        int new_has_zero = has_zero;
 
        if(d == 0) {
            new_has_zero = max(new_has_zero, 1);
        } else {
            int r3 = d % 3;
            int r7 = d % 7;
            new_dp[r3][r7] = max(new_dp[r3][r7], 1);
        }
 
        for(int r3 = 0; r3 < 3; ++r3) {
            for(int r7 = 0; r7 < 7; ++r7) {
                if(dp_nz[r3][r7] == -1) continue;
                int nr3 = (r3 + d) % 3;
                int nr7 = (r7 * 10 + d) % 7;
                new_dp[nr3][nr7] = max(new_dp[nr3][nr7], dp_nz[r3][r7] + 1);
            }
        }
 
        for(int i=0;i<3;i++) for(int j=0;j<7;j++) dp_nz[i][j] = new_dp[i][j];
        has_zero = new_has_zero;
    }
 
    int best = -1;
    if(dp_nz[0][0] != -1) best = max(best, dp_nz[0][0]);
    if(has_zero) best = max(best, 1);
 
    if(best <= 0) cout << -1 << '\n';
    else cout << (n - best) << '\n';
}
    return 0;
}

This problem is a classic application of Graph Theory on a 2D grid. To solve it, we must transform the geometric representation of houses and workers into a bipartite graph.

1. The Core Insight: Bipartite Mapping

Each house at coordinates $$$(x, y)$$$ represents a "connection" between a specific row and a specific column. Since a worker can only be assigned to a row or a column, we can model this as follows:

a. Set $$$U$$$ (Left Side): All unique $$$x$$$-coordinates (representing rows).

b. Set $$$V$$$ (Right Side): All unique $$$y$$$-coordinates (representing columns).

c. Edges: For every house at $$$(x_i, y_i)$$$, draw an edge connecting node $$$x_i$$$ in $$$U$$$ to node $$$y_i$$$ in $$$V$$$.

1. Problem Transformation: The goal is to select the minimum number of rows ($$$x$$$-nodes) or columns ($$$y$$$-nodes) such that every house (edge) is "covered" (connected to at least one selected node). In graph theory, this is known as the Minimum Vertex Cover problem.

2. Kőnig's Theorem: A fundamental theorem in graph theory, Kőnig's Theorem, states that in any bipartite graph, the number of vertices in a minimum vertex cover is exactly equal to the number of edges in a maximum matching. Maximum Matching: The largest set of edges that do not share any common vertices. Why it works: Finding the minimum number of workers (Vertex Cover) is mathematically equivalent to finding the maximum number of independent houses that cannot be serviced by the same row or column (Matching).

3. The Algorithm: Hopcroft-Karp: While a simple DFS-based matching algorithm works for smaller constraints, this problem has $$$N = 2 \times 10^5$$$. We use the Hopcroft-Karp Algorithm to efficiently find the maximum matching.

Step 1: Coordinate Compression. Since $$$x$$$ and $$$y$$$ can be up to $$$10^9$$$, we map them to smaller integers ($$$1$$$ to $$$N$$$) using sorting and lower_bound. This makes the graph manageable.

Step 2: BFS Phase. The algorithm uses a Breadth-First Search to find the shortest "augmenting paths" (paths that start and end at unmatched nodes and alternate between matched and unmatched edges).

Step 3: DFS Phase. A Depth-First Search then travels along these shortest paths to flip the edges (unmatched becomes matched), increasing the total matching count.

Step 4: Iteration. This continues until no more augmenting paths can be found.

1. Complexity & Conclusion

The time complexity of Hopcroft-Karp is $$$O(E\sqrt{V})$$$, where $$$E$$$ is the number of houses and $$$V$$$ is the number of unique coordinates. Given $$$N = 2 \times 10^5$$$, this algorithm is significantly faster than the standard $$$O(VE)$$$ approaches, allowing it to pass within the time limit. The final "Maximum Matching" value returned is our answer.

#include <bits/stdc++.h>
using namespace std;
 
struct Dinic {
    struct Edge {
        int to, cap, flow, rev;
    };
    vector<vector<Edge>> adj;
    vector<int> level, ptr;
 
    Dinic(int n) : adj(n), level(n), ptr(n) {}
 
    void addEdge(int from, int to, int cap) {
        adj[from].push_back({to, cap, 0, (int)adj[to].size()});
        adj[to].push_back({from, 0, 0, (int)adj[from].size() - 1});
    }
 
    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        level[s] = 0;
        queue<int> q;
        q.push(s);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (auto& edge : adj[v]) {
                if (edge.cap - edge.flow > 0 && level[edge.to] == -1) {
                    level[edge.to] = level[v] + 1;
                    q.push(edge.to);
                }
            }
        }
        return level[t] != -1;
    }
 
    int dfs(int v, int t, int pushed) {
        if (pushed == 0 || v == t) return pushed;
        for (int& cid = ptr[v]; cid < adj[v].size(); ++cid) {
            auto& edge = adj[v][cid];
            int tr = edge.to;
            if (level[v] + 1 != level[tr] || edge.cap - edge.flow == 0) continue;
            int push = dfs(tr, t, min(pushed, edge.cap - edge.flow));
            if (push == 0) continue;
            edge.flow += push;
            adj[tr][edge.rev].flow -= push;
            return push;
        }
        return 0;
    }
 
    int max_flow(int s, int t) {
        int flow = 0;
        while (bfs(s, t)) {
            fill(ptr.begin(), ptr.end(), 0);
            while (int pushed = dfs(s, t, 1e9)) {
                flow += pushed;
            }
        }
        return flow;
    }
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    int n;
    cin >> n;
 
    vector<int> xs(n), ys(n);
    vector<int> vx, vy;
    for (int i = 0; i < n; i++) {
        cin >> xs[i] >> ys[i];
        vx.push_back(xs[i]);
        vy.push_back(ys[i]);
    }
 
    sort(vx.begin(), vx.end());
    vx.erase(unique(vx.begin(), vx.end()), vx.end());
    sort(vy.begin(), vy.end());
    vy.erase(unique(vy.begin(), vy.end()), vy.end());
 
    int nx = vx.size();
    int ny = vy.size();
    
   
    int S = 0, T = nx + ny + 1;
    Dinic dinic(T + 1);
 
    for (int i = 0; i < nx; i++) dinic.addEdge(S, i + 1, 1);
    for (int i = 0; i < ny; i++) dinic.addEdge(nx + i + 1, T, 1);
 
    for (int i = 0; i < n; i++) {
        int r = lower_bound(vx.begin(), vx.end(), xs[i]) - vx.begin() + 1;
        int c = lower_bound(vy.begin(), vy.end(), ys[i]) - vy.begin() + 1 + nx;
        dinic.addEdge(r, c, 1);
    }
 
    cout << dinic.max_flow(S, T) << endl;
 
    return 0;
}

$$$1.$$$ Understanding the Core Constraint

The most important rule in this problem is the relationship between the energy $$$a_i$$$ and its "bit power" (popcount). We need:

$$$\sum a_i = m$$$ $$$\bigoplus \text{popcount}(a_i) = k$$$ The target XOR value $$$k$$$ is small ($$$k \le 31$$$), which suggests we should look at the binary representation of $$$k$$$ itself to construct our initial set of crystals.

$$$2.$$$ Construction Strategy: The "Power of Two" Approach

A clever way to satisfy the XOR condition is to pick numbers whose popcounts are themselves powers of two. If $$$k$$$ has a 1 at the $$$i$$$-th bit (representing $$$2^i$$$), we can include a crystal whose popcount is exactly $$$2^i$$$.

Step 1: Satisfying $$$k$$$. For every bit $$$i$$$ set in $$$k$$$, we create a crystal $$$a_i = 2^{2^i} - 1$$$. Example: If the $$$0$$$-th bit of $$$k$$$ is set ($$$2^0=1$$$), we create a number with popcount 1, like $$$(1 \ll 1) - 1 = 1$$$. Example: If the $$$2$$$-nd bit of $$$k$$$ is set ($$$2^2=4$$$), we create a number with popcount 4, like $$$(1 \ll 4) - 1 = 15$$$ (binary 1111).

Step 2: Calculating the Deficit. Let $$$x$$$ be the sum of these initial crystals. We calculate the remaining energy needed: $$$d = m - x$$$.

$$$3.$$$ Handling the Remainder ($$$d$$$)

We need to add $$$d$$$ to our sum without changing the XOR sum of the popcounts. The XOR sum remains unchanged if we add crystals in pairs with the same popcount, because $$$P \oplus P = 0$$$. If $$$d \lt 0$$$: Our initial construction exceeded $$$m$$$. This specific greedy approach fails (Output -1). If $$$d = 0$$$: We are done. The initial crystals sum perfectly to $$$m$$$. If $$$d$$$ is even and $$$d \ge 2$$$: We can simply add two crystals, each being $$$d/2$$$. Since they are identical, their popcounts are identical, and $$$pop(d/2) \oplus pop(d/2) = 0$$$. If $$$d$$$ is odd: This is trickier. We can't just split $$$d$$$ into two equal integers. Instead, we use a small constant set like $$${1, 2, (d-3)/2, (d-3)/2}$$$. $$$1$$$ and $$$2$$$ both have a popcount of 1. $$$1 \oplus 1 = 0$$$. The two $$$(d-3)/2$$$ values are identical, so their XOR contribution is 0.The sum is $$$1 + 2 + \frac{d-3}{2} + \frac{d-3}{2} = 3 + d - 3 = d$$$.

$$$4.$$$ Edge Cases and Adjustments

The $$$d=1$$$ case: If $$$d=1$$$, we can't use the pair strategy. The code attempts to "absorb" the 1 into an existing crystal. If we have a crystal $$$a[0]=1$$$ (popcount 1), we change it to $$$2$$$ (also popcount 1). The sum increases by 1, but the XOR sum is preserved. The $$$-1$$$ condition: If $$$d$$$ is negative, or if $$$d=1$$$ but we have no suitable crystal to increment, we output -1.

Summary of Complexity

Time Complexity: $$$O(T \log K)$$$ per test case to iterate through bits of $$$K$$$. Given $$$K \le 31$$$, this is effectively $$$O(1)$$$ relative to $$$M$$$. Space Complexity: $$$O(N)$$$ to store the sequence of crystals.

#include <iostream>
#include <vector>
 
using namespace std;
 
int main(){
	cin.tie(0) -> sync_with_stdio(0);
	int T; cin >> T;
	while(T--){
		int m, k; cin >> m >> k;
		vector<int> a;
		int x = 0;
		for(int i = 0; i<5; i++){
			if(k&(1 << i)){
				a.push_back((1 << (1 << i)) - 1);
				x += a.back();
			}
		}
 
		int d = m - x;
		vector<int> b;
		int flag = 0; 
		if(d < 0){
			flag = 1;
		}else if(d >= 2){
			if(d%2 == 0){
				b = {d/2, d/2};
			}else{
				b = {1, 2, (d-3)/2, (d-3)/2};
			}
		}else if(d == 0){
			b = {};
		}else{
			if(a[0] == 1){
				a[0] = 2;
			}else{
				flag = -1;
			}
		}
 
		if(flag){
			cout << "-1\n";
		}else{
			cout << a.size() + b.size() << "\n";
			for(int i : a) 
				cout << i << " ";
			for(int i : b)
				cout << i << " " ;
			cout << "\n";
		}
	}
}

1. Symmetry and Linearity of Expectation

Let $$$I_{i,j}$$$ be an indicator variable that is 1 if $$$S_{i} \gt S_{j}$$$ and 0 otherwise. The expected number of inversions is:

$$$E[inversions]=E[\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}I_{ij}]=\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}P(S_{i} \gt S_{j})$$$

Because every bot performs an independent random walk on the same graph starting from the same vertex, the random variables $$$S_{1},...,S_{N}$$$ are independent and identically distributed (i.i.d.). Therefore, the probability $$$P(S_{i} \gt S_{j})$$$ is identical for all pairs. There are exactly $$$\binom{N}{2}$$$ such pairs: $$$E[inversions] = \frac{N(N-1)}{2} \cdot P(S_1 \gt S_2)$$$

By symmetry of the identical distributions, $$$P(S_{1} \gt S_{2})=P(S_{1} \lt S_{2})$$$. Since the sum of all mutually exclusive outcomes must be 1:

$$$2\cdot P(S_{1} \gt S_{2})+P(S_{1}=S_{2})=1\Rightarrow P(S_{1} \gt S_{2})=\frac{1-P(S_{1}=S_{2})}{2}$$$

We have reduced the problem from tracking multiple bots to finding the probability that two independent bots tie, which allows us to calculate the probability distribution for just a single bot.

1. Graph Distances and the Transition Matrix

First, run a Breadth-First Search (BFS) from vertex 1 to find $$$D[u]$$$, the shortest path distance from vertex 1 to every vertex $$$u$$$. Next, construct the transition matrix $$$T$$$ for a single bot.

Let $$$T_{v,u}$$$ be the probability of transitioning from $$$u$$$ to $$$v$$$. If there is an edge between $$$u$$$ and $$$v$$$, $$$T_{v,u}=deg(u)^{-1}$$$ (mod 998244353). Otherwise, $$$T_{v,u}=0$$$.

Let $$$P_{0}$$$ be the initial state column vector of size $$$M$$$, where $$$P_{0}[1]=1$$$ and all other entries are 0. The state vector after $$$K$$$ steps is:

$$$P_{K}=T^{K}\times P_{0}$$$

Because $$$K\le10^{18}$$$, this is computed using binary matrix exponentiation in $$$O(M^{3}log~K)$$$ time.

1. Computing the Tie Probability

After computing $$$P_{K}$$$, the value $$$P_{K}[u]$$$ gives the probability that a single bot ends at vertex $$$u$$$. We group these probabilities by the final distance. Let $$$prob[d]$$$ be the probability that a bot ends at a vertex with distance $$$d$$$:

$$$prob[d] = \sum_{u \text{ where } D[u]=d} P_K[u]$$$

The probability that two independent bots tie is the sum of the probabilities that they both end up at the same distance:

$$$P(S_{1}=S_{2})=\sum_{d}(prob[d])^{2}$$$

Finally, we substitute $$$P(S_{1}=S_{2})$$$ back into our symmetry formula to find $$$P(S_{1} \gt S_{2})$$$, multiply by $$$\binom{N}{2}$$$ (mod 998244353), and print the result.

Time Complexity: $$$O(M^{3}log~K+E)$$$ Space Complexity: $$$O(M^{2})$$$

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
 
ll md = 998244353;
 
ll pwr(ll b, ll p) {
    ll r = 1;
    while(p) {
        if(p & 1) r = r * b % md;
        b = b * b % md;
        p >>= 1;
    }
    return r;
}
 
vvl mul(vvl a, vvl b, int m) {
    vvl c(m, vl(m, 0));
    for(int i = 0; i < m; ++i)
        for(int k = 0; k < m; ++k)
            for(int j = 0; j < m; ++j)
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % md;
    return c;
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll n, k, m, e;
    cin >> n >> k >> m >> e;
    vector<vl> g(m);
    vl d(m, 0), c(m, -1);
    for(int i = 0; i < e; ++i) {
        int u, v; cin >> u >> v; --u; --v;
        g[u].push_back(v); g[v].push_back(u);
        d[u]++; d[v]++;
    }
    queue<int> q;
    q.push(0); c[0] = 0;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(int v : g[u]) if(c[v] == -1) {
            c[v] = c[u] + 1;
            q.push(v);
        }
    }
    vvl t(m, vl(m, 0)), r(m, vl(m, 0));
    for(int i = 0; i < m; ++i) r[i][i] = 1;
    for(int i = 0; i < m; ++i)
        for(int j : g[i]) t[j][i] = pwr(d[i], md - 2);
    while(k) {
        if(k & 1) r = mul(r, t, m);
        t = mul(t, t, m);
        k >>= 1;
    }
    map<int, ll> p;
    for(int i = 0; i < m; ++i)
        if(c[i] != -1) p[c[i]] = (p[c[i]] + r[i][0]) % md;
    ll s = 0;
    for(auto x : p) s = (s + x.second * x.second) % md;
    ll x = (1 - s + md) % md * pwr(2, md - 2) % md;
    ll y = (n % md) * ((n - 1) % md) % md * pwr(2, md - 2) % md;
    cout << x * y % md << "\n";
    return 0;
}

To solve this problem, we must shift our perspective from iterating over permutations to isolating the contribution of the first element, $$$P_{1}$$$.

Observation 1: The First Element's Impact

If we fix $$$P_{1}=x$$$, how many inversions does it create? Since $$$x$$$ is at the very front of the array, every element smaller than $$$x$$$ will appear after it. There are exactly $$$x-1$$$ such elements. Therefore, setting $$$P_{1}=x$$$ immediately contributes exactly $$$x-1$$$ inversions.

Observation 2: The Remaining Subproblem

The remaining $$$N-1$$$ elements must form a permutation of length $$$N-1$$$. For the entire permutation to have exactly $$$K$$$ inversions, the remaining $$$N-1$$$ elements must internally contain exactly $$$K-(x-1)$$$ inversions.

Let $$$I(n,k)$$$ be the number of permutations of length $$$n$$$ with $$$k$$$ inversions. The answer is given by:

$$$Ans=\sum_{x=1}^{min(N,K+1)}x\cdot I(N-1,K-x+1)$$$

Observation 3: Shifting to Generating Functions

Since $$$N\le10^{9}$$$, an $$$O(N\cdot K)$$$ DP to compute $$$I(n,k)$$$ will Time Limit Exceed (TLE). We must view this summation as the convolution of two sequences: the sequence of weights $$$W_{x}=x$$$, and the sequence of inversion counts $$$I(N-1,k)$$$. This naturally leads us to multiply their generating functions and extract the $$$K$$$-th coefficient in $$$O(K\sqrt{K})$$$ time using partition math.

Deep Mathematical Proof

Lemma 1. The generating function for the number of inversions in a permutation of length $$$n$$$ is:

$$$I_{n}(q)=\sum_{k=0}^{\infty}I(n,k)q^{k}=\prod_{i=1}^{n}\frac{1-q^{i}}{1-q}$$$

Proof. We can construct a permutation of length $$$n$$$ by inserting the element $$$i$$$ (from $$$i=1$$$ to $$$n$$$) into a permutation of length $$$i-1$$$. When inserting the element $$$i$$$ (which is currently the maximum element), we can place it in $$$i$$$ different positions. If placed at the very end, it creates 0 inversions. If placed one spot before the end, it creates 1 inversion, and so on, up to $$$i-1$$$ inversions. Thus, the insertion of element $$$i$$$ contributes a factor of $$$(1+q+q^{2}+\cdot\cdot\cdot+q^{i-1})=\frac{1-q^{i}}{1-q}$$$. Since these choices are independent, we multiply these factors for all $$$i$$$.

Theorem 1. The final answer is the coefficient of $$$q^{K}$$$ in the polynomial $$$G(q)=A(q)\cdot B(q)\cdot C(q)$$$ where:

$$$A(q)=\prod_{i=1}^{N-1}(1-q^{i})$$$

$$$B(q)=\frac{1}{(1-q)^{N+1}}$$$

$$$C(q)=1-(N+1)q^{N}+Nq^{N+1}$$$

Proof. The total sum is the coefficient of $$$q^{K}$$$ in the product of the inversion generating function $$$I_{N-1}(q)$$$ and the weight generating function $$$W(q)=\sum_{x=1}^{N}xq^{x-1}$$$.

$$$W(q) = \frac{d}{dq} \left( \frac{1-q^{N+1}}{1-q} \right) = \frac{1-(N+1)q^{N}+Nq^{N+1}}{(1-q)^{2}}$$$

Multiplying $$$W(q)$$$ by $$$I_{N-1}(q)$$$: $$$G(q)=\left(\frac{1}{(1-q)^{N-1}}\prod_{i=1}^{N-1}(1-q^{i})\right)\cdot\frac{1-(N+1)q^{N}+Nq^{N+1}}{(1-q)^{2}}$$$

Grouping the denominators yields $$$A(q)\cdot B(q)\cdot C(q)$$$.

Computing $$$A(q)$$$ in $$$O(K\sqrt{K})$$$

If $$$N-1\ge K$$$: $$$A(q)$$$ is simply the expansion of Euler's function $$$\phi(q)=\prod_{i=1}^{\infty}(1-q^{i})$$$. By Euler's Pentagonal Number Theorem, $$$\phi(q)=\sum_{m=-\infty}^{\infty}(-1)^{m}q^{m(3m-1)/2}$$$. We only need terms up to $$$q^{K}$$$, requiring $$$O(\sqrt{K})$$$ terms.

If $$$N-1 \lt K$$$: We use the identity: $$$\prod_{i=1}^{N-1}(1-q^{i})=\phi(q)\cdot\prod_{i=N}^{\infty}\frac{1}{1-q^{i}}$$$. The term $$$\prod_{i=N}^{\infty}\frac{1}{1-q^{i}}$$$ is the generating function for integer partitions where all parts are strictly $$$\ge N$$$. Since the minimum part size is $$$N$$$, any partition of $$$k\le K$$$ can have at most $$$K/N$$$ parts. We use DP where $$$dp[i][j]$$$ is the number of partitions of $$$j$$$ into exactly $$$i$$$ parts, each $$$\ge N$$$: $$$dp[i][j]=dp[i][j-i]+dp[i-1][j-N]$$$

Since $$$N\le\sqrt{K}$$$ in this branch, $$$i\le\sqrt{K}$$$, ensuring the $$$O(K\sqrt{K})$$$ state space is optimal.

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 998244353;
 
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}
 
long long modInverse(long long n) {
    return power(n, MOD - 2);
}
 
const int MAXK = 100005;
long long fact[MAXK], invFact[MAXK];
 
void precompute() {
    fact[0] = 1; invFact[0] = 1;
    for (int i = 1; i < MAXK; i++) fact[i] = (fact[i - 1] * i) % MOD;
    invFact[MAXK - 1] = modInverse(fact[MAXK - 1]);
    for (int i = MAXK - 2; i >= 1; i--) invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
}
 
long long nCr_small(long long n, long long r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}
 
int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    
    precompute();
    
    long long N; int K;
    cin>>N>>K;
 
    if (K == 0) { cout << 1 << "\n"; return 0; }
    if (N == 1) { cout << (K == 0 ? 1 : 0) << "\n"; return 0; }
 
    long long n = N - 1;
    vector<long long> A(K + 1, 0);
 
    if (n >= K) {
        A[0] = 1;
        for (int k = 1; ; k++) {
            int p1 = k * (3 * k - 1) / 2, p2 = k * (3 * k + 1) / 2;
            if (p1 > K && p2 > K) break;
            long long sign = (k % 2 == 1) ? -1 : 1;
            if (p1 <= K) A[p1] = (A[p1] + sign + MOD) % MOD;
            if (p2 <= K) A[p2] = (A[p2] + sign + MOD) % MOD;
        }
    } else {
        int THRESHOLD = sqrt(K) + 2;
        if (n <= THRESHOLD) {
            A[0] = 1;
            for (int i = 1; i <= n; i++)
                for (int j = K; j >= i; j--)
                    A[j] = (A[j] - A[j - i] + MOD) % MOD;
        } else {
            vector<long long> P_inf(K + 1, 0); 
            P_inf[0] = 1;
            for (int k = 1; ; k++) {
                int p1 = k * (3 * k - 1) / 2, p2 = k * (3 * k + 1) / 2;
                if (p1 > K && p2 > K) break;
                long long sign = (k % 2 == 1) ? -1 : 1;
                if (p1 <= K) P_inf[p1] = (P_inf[p1] + sign + MOD) % MOD;
                if (p2 <= K) P_inf[p2] = (P_inf[p2] + sign + MOD) % MOD;
            }
            
            int max_parts = K / (n + 1) + 1;
            vector<vector<long long>> dp(max_parts + 1, vector<long long>(K + 1, 0));
            dp[0][0] = 1;
            
            vector<long long> H(K + 1, 0); 
            H[0] = 1;
            
            for (int i = 1; i <= max_parts; i++) {
                for (int j = 0; j <= K; j++) {
                    if (j >= i) dp[i][j] = (dp[i][j] + dp[i][j - i]) % MOD;
                    if (j >= n + 1) dp[i][j] = (dp[i][j] + dp[i - 1][j - (n + 1)]) % MOD;
                    H[j] = (H[j] + dp[i][j]) % MOD;
                }
            }
            
            // The O(K*sqrt(K)) optimization block
            for (int j = 0; j <= K; j++) {
                if (P_inf[j] == 0) continue; 
                for (int i = j; i <= K; i++) {
                    A[i] = (A[i] + P_inf[j] * H[i - j]) % MOD;
                }
            }
        }
    }
 
    vector<long long> C_base(K + 1, 0);
    C_base[0] = 1; 
    long long N_mod = N % MOD;
    for (int y = 1; y <= K; y++) {
        long long num = (y + N_mod) % MOD;
        long long den = modInverse(y);
        C_base[y] = C_base[y - 1] * num % MOD * den % MOD;
    }
 
    long long ans = 0;
    for (int m = 0; m <= K; m++) {
        int y = K - m;
        long long C_y = C_base[y];
        if (N <= K) {
            if (y >= N) C_y = (C_y - (N_mod + 1) * nCr_small(y, N) % MOD + MOD) % MOD;
            if (y >= N + 1) C_y = (C_y + N_mod * nCr_small(y - 1, N) % MOD) % MOD;
        }
        ans = (ans + A[m] * C_y) % MOD;
    }
    
    cout << ans << "\n";
    return 0;
}

In this case any $$$a[i] \gt =b[i]$$$ for all $$$(1 \lt =i \lt =n)$$$, you can easily make a[i]%b[i]==0 by decreasing the value of a[i] or increase the value of b[i] with cost 0, and otherwise the cost is the absolute difference between a[i] and b[i].

#include <bits/stdc++.h>
 
using namespace std;
 
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define testcase int t; cin>>t; for(int i=0;i<t;i++)
 
#define ll long long int
ll lcm(ll a, ll b) {
    return (a / __gcd(a, b)) * b;
}
 
 
void solved(){
	/*start*/
    ll n;
    cin>>n;
    vector <ll> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    vector <ll> b(n);
    for(int i=0;i<n;i++){
        cin>>b[i];
    }
    ll cnt=0;
    for(int i=0;i<n;i++){
        if(a[i]<b[i]){
            cnt+=(b[i]-a[i]);
        }
    }
    cout<<cnt<<"\n";
	/*end*/
}
 
int main(){
	faster
	testcase 
	solved();
}

In this, to minimise the number of string h, we will count the total difference between s and p in characters, then we can make exactly (extra_char_left_count+k-1)/k using ceil for the last few characters left;

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
	ll t;
	cin>>t;
	while(t--){
	    ll n,m,k;
	    cin>>n>>m>>k;
	    string s,p;
	    cin>>s>>p;
	    int l=0,i=0;
	    while(l<m&&i<n){
	        if(s[i]==p[l]){
	            l++;
	        }
	        i++;
	    }
	    if(l==m){
	        cout<<(n-m+k-1)/k<<"\n";
	    }
	    else{
	        cout<<"-1\n";
	    }
	}
	
}

Inside each group, if the most frequent value $$$mx$$$ is less than or equal to half the group size $$$sz$$$, you can pair almost everyone. If $$$mx \gt sz/2$$$, you are forced to have $$$sz - 2(sz - mx)$$$ leftovers of that specific value. Globally, the same principle applies: the maximum inter-group pairs you can form is limited by the "gap" between the total leftovers and the most dominant leftover value.

The total answer is the sum of local pairs plus these budgeted global pairs. This ensures you only "buy" matches that are physically possible to form given the leftover value constraints.

#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#endif
#define int long long
#define pii pair<int, int>
const int INF = 1e18;
const int MOD = 1e9 + 7;
 
void solve() {
    int n , k , c;
   cin >> n >> k >> c;
 
    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];
    }
 
    map<int, map<int, int>> m;
    for (int i=0;i<n;i++) {
        m[b[i]][a[i]]++;
    }
 
    int ans = 0;
    int tot = 0;
    int g_mx = 0;
    map<int, int> rem;
 
    for (auto it : m) {
        map<int, int> &group = it.second;
        
        int sz = 0;
        int mx = 0;
        int dom = -1;
 
        for (auto c_it : group) {
            int cnt = c_it.second;
            int cl = c_it.first;
            sz += cnt;
            if (cnt > mx) {
                mx = cnt;
                dom = cl;
            }
        }
 
        if (mx > sz / 2) {
            int p = sz - mx;
            ans += p;
            int r = sz - (2 * p);
            rem[dom] += r;
            tot += r;
        } 
        else {
            ans += sz / 2;
            if (sz % 2 != 0) {
                tot += 1;
            }
        }
    }
 
    for (auto r_it : rem) {
        if (r_it.second > g_mx) {
            g_mx = r_it.second;
        }
    }
 
    int can_p = tot / 2;
    if (tot - g_mx < can_p) {
        can_p = tot - g_mx;
    }
 
    int bud_p = (c / k) * 2;
 
    int paid = can_p;
    if (bud_p < paid) {
        paid = bud_p;
    }
 
    cout << ans + paid << '\n';
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
 
    return 0;
}

1. The Supermask Principle: For any chosen bitwise AND sum $$$S$$$, the largest possible subsequence we can form consists of all integers $$$x \in [l, r]$$$ such that $$$x \text{ AND } S = S$$$. Adding any such $$$x$$$ to our set does not decrease the bitwise AND sum, meaning the condition $$$S \ge k$$$ remains satisfied while the length $$$m$$$ increases. Thus, the problem is equivalent to finding an $$$S \ge k$$$ that maximizes the count of its supermasks in the range.

2. The Candidate Space Proof: We do not need to check every $$$S \in [k, r]$$$. We only need to check $$$k$$$ itself and the set of "bit-minimal" integers greater than $$$k$$$. These are formed by: Picking a bit $$$i$$$ that is unset ($$$0$$$) in $$$k$$$. Setting bit $$$i$$$ to $$$1$$$ and clearing all bits $$$j \lt i$$$ to $$$0$$$. Any other value $$$S' \gt k$$$ that is not one of these candidates will be a supermask of either $$$k$$$ or one of these candidates. Since a supermask of $$$S'$$$ is also a supermask of any value $$$S \subset S'$$$, the count of supermasks for our candidates will always be greater than or equal to the count for any arbitrary $$$S'$$$.

3. Combinatorial Counting: For a fixed mask $$$S$$$, the number of integers $$$x \le N$$$ that satisfy $$$x \text{ AND } S = S$$$ can be calculated in $$$O(\log N)$$$ using a digit-based approach. If $$$S$$$ has $$$b$$$ bits set, and we are considering a range of $$$W$$$ bits, there are $$$W - b$$$ "free" bits. The number of ways to fill these bits such that the result is $$$\le N$$$ follows a standard combinatorial path: at any bit position $$$i$$$ where $$$N$$$ has a $$$1$$$ and $$$S$$$ has a $$$0$$$, we can set that bit to $$$0$$$ and freely choose all subsequent "free" bits below it ($$$2^f$$$ combinations).

Conclusion: By testing only $$$O(\log r)$$$ candidate masks and using the inclusion-exclusion principle $$$(\text{count}(r) - \text{count}(l-1))$$$, we efficiently find the global maximum length in $$$O(\log^2 r)$$$ time.

#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#include <C:/Users/ajiit/Desktop/Future/Coding/Problem Solving/debug.cpp>
#endif
#define int long long
#define pii pair<int, int>
const int INF = 1e18;
const int MOD = 957483783; 
 
int calc(int n, int x) {
    if (x > n) return 0;
 
    int f = 0;
    for (int i=0;i<=60;i++) {
        if ((x >> i) & 1) continue;
        else f++;
    }
    
    int res = 0;
    for (int i=60;i>=0;i--) {
        int nb = (n >> i) & 1;
        int xb = (x >> i) & 1;
        
        if (!xb) {
            f--;
            if (nb) res += (1LL << f);
        } 
        else {
            if (!nb) return res;
        }
    }
    return res + 1;
}
 
void solve() {
    int l , r , k;
    cin >> l >> r >> k;
    
    vector<int> v;
    v.push_back(k);
    
    for (int i=0;i<=60;i++) {
        if ((k >> i) & 1) continue;
        else {
            int m = ~((1LL << i) - 1);
            int cur = (k | (1LL << i)) & m;
            if (cur <= r) v.push_back(cur);
        }
    }
    
    int ans = 0;
    for (int x : v) {
        if (x > r) continue;
        int cnt = calc(r, x) - calc(l - 1, x);
        ans = max(ans, cnt);
    }
    
    cout << ans % MOD << '\n';
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
 
    return 0;
}

The core of this problem lies in recognizing that repeated prefix sums are equivalent to combinations with repetition. Starting from $$$S(0) = [1, 2, 3, \dots]$$$, where the $$$i$$$-th term is $$$S(0)[i] = i = \binom{i}{1}$$$, each subsequent level of prefix sums follows the Hockey-stick Identity:

Applying this property recursively, the $$$i$$$-th term of the $$$k$$$-th sequence is

To find the sum of elements from index $l$ to $$$r$$$, we calculate the prefix sum of $$$S(k)$$$ itself. Summing $$$S(k)[i]$$$ from $$$1$$$ to $$$N$$$ is equivalent to applying the identity once more:

Therefore, the sum from $$$l$$$ to $$$r$$$ is derived using the difference of prefix sums:

Since $$$k, l,$$$ and $$$r$$$ can be as large as $$$10^{18}$$$, and the result is required modulo a prime $$$p$$$, Lucas's Theorem is the optimal tool. It allows us to compute these large binomial coefficients in $$$O(p + q \log_p N)$$$ time by breaking the numbers into their base-$$$p$$$ digits. This approach successfully reduces a complex recursive sequence into a direct combinatorial evaluation.

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define endl "\n"
 
int mod;
 
int ma(int a, int b) {return (a%mod + b%mod + mod) % mod;}
int ms(int a, int b) {return (a%mod - b%mod + mod) % mod;}
int mm(int a, int b) {return (a%mod * b%mod) % mod;}
 
int modexp(int base, int exp) {
    int res = 1;
    base %= mod;
    while(exp) {
        if(exp & 1) res = mm(res, base);
        base = mm(base, base);
        exp >>= 1;
    }
    return res;
}
 
int modinv(int x) {
    return modexp(x, mod-2);
}
 
void solve()
{
    int q;
    cin >> mod >> q;
 
    // Precompute factorials only up to mod-1
    vector<int> fact(mod), invfact(mod);
 
    fact[0] = 1;
    for(int i = 1; i < mod; i++)
        fact[i] = mm(fact[i-1], i);
 
    invfact[mod-1] = modinv(fact[mod-1]);
    for(int i = mod-2; i >= 0; i--)
        invfact[i] = mm(invfact[i+1], i+1);
 
    auto comb = [&](int n, int r) -> int {
        if(n < 0 || r < 0 || r > n) return 0;
        return mm(fact[n], mm(invfact[n-r], invfact[r]));
    };
 
    auto lucas = [&](int n, int r) -> int {
        int ans = 1;
        while(n > 0 || r > 0) {
            ans = mm(ans, comb(n % mod, r % mod));
            n /= mod;
            r /= mod;
        }
        return ans;
    };
 
    while(q--) {
        int k,l,r;
        cin >> k >> l >> r;
 
        int right = lucas(r + k + 1, k + 2);
        int left  = lucas(l + k, k + 2);
 
        cout << ms(right, left) << endl;
    }
}
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    solve();
}

The problem asks us to find the largest integer $$$y$$$ such that $$$x = a^y$$$ for some integer $$$a$$$. Since $$$x \le 10^{18}$$$ and $$$a \ge 2$$$, the maximum possible value for $$$y$$$ is $$$\lfloor \log_2(10^{18}) \rfloor \approx 60$$$. This small range for $$$y$$$ allows us to iterate through all possible exponents in descending order, from 60 down to 1. For a fixed exponent $$$i$$$, we need to determine if there exists an integer $$$a$$$ such that $$$a^i = x$$$. Because the function $$$f(a) = a^i$$$ is monotonically increasing for $$$a \ge 1$$$, we can efficiently check for the existence of $$$a$$$ using binary search in the range $$$[2, \sqrt[i]{x}]$$$.To prevent integer overflow during the calculation of $$$a^i$$$, we use a safe multiplication check ($$$t \gt \text{inf}/m$$$) before updating the product. The first (largest) $$$i$$$ that satisfies the condition $$$a^i = x$$$ is our answer. This approach runs in $$$O(\log(\text{max_exponent}) \cdot \log(\sqrt[i]{x}))$$$, which easily passes within the time limit given the constraints.

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define endl "\n"
 
bool TestCases = false;
int inf = 1e18;
 
bool check(int i,int n) {
    if(i==1) return true;
    int l = 2;
    int r = 1e9;
    while(l<=r) {
        int m = (l+r)/2;
        int t = 1;
        bool ok = true;
        for(int j=1;j<=i;j++) {
            if(t>inf/m) {
                ok = false; break;
            }
            t*=m;
            if(t>n) {
                ok = false; break;
            }
        }
        if(!ok) {
            r = m-1;
        }else if(t==n) {
            return true;
        }else {
            l = m+1;
        }
    }
    return false;
}
 
void solve()
{
    int n; cin>>n;
    for(int i=60;i>0;i--) {
        if(check(i,n)) {
            cout<<i;
            return;
        }
    }
}
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int t = 1;
    if(TestCases)
    {
        cin >> t;
    }
 
    while(t--)
    {
        solve();
    }
}

The game can be divided into two states based on the total sum:

1. Initial Sum is Even: Alice and Bob are locked into moves that maintain parity. An odd number must be replaced by an odd divisor, and an even number must be replaced by an even divisor. We calculate the Grundy value $$$G(u)$$$ for each number $$$u$$$ by considering only these "parity-preserving" divisors. The game then follows the Sprague-Grundy Theorem, where Alice wins if $$$G(a_1) \oplus G(a_2) \oplus \dots \oplus G(a_n) \neq 0$$$.

2. Initial Sum is Odd: Alice's first move must be parity-flipping to make the sum even. She must find an even $$$a[i]$$$ and replace it with an odd divisor $$$v$$$ such that the resulting game state (now with an even sum) is a losing position for Bob. This is possible if there exists some $$$a[i]$$$ and its odd divisor $$$v$$$ such that $$$G(v) = \text{XOR_sum} \oplus G(a[i])$$$. If no such move exists, Alice cannot even make a legal first move and loses immediately.

By precomputing Grundy values using a memoized $$$O(N \log N)$$$ sieve and checking these conditions, we determine the winner in $$$O(N + \sum \text{divisors})$$$ per test case.

#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#include <C:/Users/ajiit/Desktop/Future/Coding/Problem Solving/debug.cpp>
#endif
#define int long long
#define pii pair<int, int>
const int INF = 1e18;
const int MOD = 1e9 + 7;
const int MAXN = 1000005;
 
vector<int> divs[MAXN];
int memo[MAXN];
 
void pre() {
    for (int i = 1; i < MAXN; ++i) {
        for (int j = 2 * i; j < MAXN; j += i) {
            divs[j].push_back(i);
        }
    }
    memset(memo, -1, sizeof(memo));
}
 
int get_grundy(int u) {
    if (memo[u] != -1) return memo[u];
    
    int mask = 0;
    for (int v : divs[u]) {
        if (u % 2 != 0) {
            mask |= (1LL << get_grundy(v));
        } else {
            if (v % 2 == 0) {
                mask |= (1LL << get_grundy(v));
            }
        }
    }
    
    int g = 0;
    while ((mask >> g) & 1) g++;
    return memo[u] = g;
}
 
void solve() {
    int n;
    cin >> n;
 
    vector<int> a(n);
    int par = 0;
    int xr = 0;
    
    for (int i=0;i<n;i++) {
        cin >> a[i];
        par = (par + a[i]) % 2;
        xr ^= get_grundy(a[i]);
    }
 
    if (par == 0) {
        if (xr > 0) cout << "Alice\n";
        else cout << "Bob\n";
    } 
    else {
        bool ok = false;
        for (int x : a) {
            if (x % 2 == 0) {
                int target = xr ^ get_grundy(x);
                for (int v : divs[x]) {
                    if (v % 2 != 0) {
                        if (get_grundy(v) == target) {
                            ok = true;
                            break;
                        }
                    }
                }
            }
            if (ok) break;
        }
 
        if (ok) cout << "Alice\n";
        else cout << "Bob\n";
    }
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    pre();
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
 
    return 0;
}

Problem Overview: The problem requires us to deduce the hidden triangulation of a convex $$$N$$$-gon by querying the number of diagonals intersected by a given line segment. Given a query limit of $$$4000$$$ for $$$N \le 1000$$$, an $$$O(N^2)$$$ approach will fail. We present an $$$O(N)$$$ monotonic stack solution that uses at most $$$2N$$$ queries.

The Logic and Mathematical Proof:

We process vertices from $$$1$$$ to $$$N$$$ in clockwise order, maintaining a stack $$$S = [s_1, s_2, \dots, s_k]$$$ of vertices that form the “exposed” boundary of our discovered triangulation. When we visit vertex $$$i$$$, we check if $$$i$$$ can form a diagonal with $$$s_{k-1}$$$ (the vertex just below the top of the stack). We query the segment $$$(s_{k-1}, i)$$$.

Case 1: Query returns 0. If the segment $$$(s_{k-1}, i)$$$ crosses no diagonals, the region bounded by $$$s_{k-1}, s_k, i$$$ is completely empty. Since the polygon is fully triangulated, $$$\triangle s_{k-1}s_ki$$$ must be a triangle in the hidden triangulation. Furthermore, because diagonals cannot cross, no future vertex $$$j \gt i$$$ can ever connect to $$$s_k$$$ without crossing the newly discovered diagonal $$$(s_{k-1}, i)$$$. Thus, $$$s_k$$$ is “sealed off” and can be permanently popped from the stack.

Case 2: Query returns > 0. If $$$(s_{k-1}, i)$$$ is intersected by a hidden diagonal, that diagonal must originate from $$$s_k$$$ and connect to some future vertex $$$j \gt i$$$. Because the vertices are ordered cyclically on a convex hull, any line segment from $$$i$$$ to a deeper stack element $$$s_m$$$ ($$$m \lt k-1$$$) will also be strictly intersected by this diagonal from $$$s_k$$$. Therefore, $$$i$$$ cannot connect to any deeper stack elements. We halt our backward search, push $$$i$$$ to the stack, and move to the next vertex.

Complexity: Every query either results in popping an element from the stack or breaking the inner loop. Since exactly $$$N$$$ elements are pushed to the stack, there can be at most $$$N$$$ pops and $$$N$$$ loop breaks. Thus, the total number of queries is strictly bounded by $$$2N$$$, effortlessly passing the limit.

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define FOR(i,a,b) for(int i=a; i<b; i++)
using vi=vector<int>;
using vii=vector<vi>;
using vpii=vector<pair<int,int>>;
#define pb push_back
 
int quer(int u, int v) {
    cout<<"? "<<u<<" "<<v<<endl;
    int ans; cin>>ans;
    if (ans==-1) exit(0);
    return ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n; cin>>n;
    vi st; vpii diag;
    st.pb(1); st.pb(2);
    FOR(i,3,n+1) {
        while (st.size()>=2) {
            int top=st.back();
            int pv=st[st.size()-2];
            int cut=0;
            if (pv==1 && i==n) {
              cut=0;
            }
            else {
                cut=quer(pv,i);
            }
            if (cut==0){
                if (!(pv==1 && i==n)){
                    diag.pb({pv,i});
                }
                st.pop_back();
            }
            else {
                break;
            }
        }
        st.pb(i);
    }
    cout<<"!"<<endl;
    FOR(i,0,size(diag)) {
        cout<<diag[i].first<<" "<<diag[i].second<<endl;
    }
    cout<<flush;
}

In this game to win, Alice has to choose one 2 and all 3 in his first chances only otherwises he loses. So, if he have number 2 less than two then he lose otherwise win.

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector <int> a(n);
        int x=0;
        for(int i=0;i<n;i++){
            cin>>a[i];
            if(a[i]==2)x++;
        }
        if(x>=2){
            cout<<"Alice\n";
        }
        else{
            cout<<"Bob\n";
        }
    }
}

To visit every cell exactly once in a $$$3 \times N$$$ grid starting at a corner and ending at the opposite corner, the path must move in a specific "snake" or "zigzag" fashion.In a $$$3 \times N$$$ grid, for every column $$$i$$$ (from $$$2$$$ to $$$N-1$$$), the path has two choices on how to "traverse" that column's height to reach the next section while ensuring no cells are left behind. Since there are $$$N-2$$$ such intermediate columns where these choices matter, we get $$$2 \times 2 \times \dots \times 2$$$ ($$$N-2$$$ times). And for $$$N$$$=$$$1$$$ answer will be 1.

#include <bits/stdc++.h>
using namespace std;
 
static const long long MOD = 1000000007LL;
 
long long modpow(long long a, long long e) {
    long long r = 1 % MOD;
    a %= MOD;
    while (e > 0) {
        if (e & 1) r = (r * a) % MOD;
        a = (a * a) % MOD;
        e >>= 1;
    }
    return r;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T;
    cin >> T;
    while (T--) {
        long long N;
        cin >> N;
        if (N == 1) cout << 1 << "\n";
        else cout << modpow(2, N - 2) << "\n";
    }
    return 0;
}

Kael's Private Pool ($$$K$$$): Numbers divisible by $$$x$$$ but not $$$y$$$. Liora's Private Pool ($$$L$$$): Numbers divisible by $$$y$$$ but not $$$x$$$. The Shared Pool ($$$S$$$): Numbers divisible by both $$$x$$$ and $$$y$$$. Game Strategy: Optimal players will always prioritize the Shared Pool ($$$S$$$). Why? Because every time a player picks from $$$S$$$, they take away a potential move from their opponent while keeping their own "Private Pool" intact for later. The game's outcome depends on who is forced to start picking from their private pool first. Case AnalysisIf $$$|S|$$$ is Even, Kael and Liora will pick an equal number of shared elements. The shared pool neutralizes itself. The winner is simply whoever has the larger private pool. Kael wins if $$$|K| \gt |L|$$$. Liora wins if $$$|L| \geq |K|$$$. If $$$|S|$$$ is Odd, Kael (the first player) gets to take the "extra" shared element. This gives him a +1 advantage in the turn order. Effectively, Kael can win even if his private pool is equal to Liora's. Kael wins if $$$|K| \geq |L|$$$. Liora wins if $$$|L| \gt |K|$$$.

#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#endif
#define int long long
#define pii pair<int, int>
const int INF = 1e18;
const int MOD = 1e9 + 7;

void solve() {
    int n;
    long long x, y;
    cin >> n >> x >> y;

    int kael_moves = 0;
    int liora_moves = 0;
    int common_moves = 0;

    for (int i = 0; i < n; i++) {
        long long val;
        cin >> val;

        bool div_x = (val % x == 0);
        bool div_y = (val % y == 0);

        if (div_x && div_y) {
            common_moves++;
        } else if (div_x) {
            kael_moves++;
        } else if (div_y) {
            liora_moves++;
        }
    }

    if (common_moves % 2 == 0) {
        if (kael_moves > liora_moves) {
            cout << "Kael" << "\n";
        } else {
            cout << "Liora" << "\n";
        }
    } 
    else {
        if (liora_moves > kael_moves) {
            cout << "Liora" << "\n";
        } else {
            cout << "Kael" << "\n";
        }
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

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

    return 0;
}

The goal is to construct an array such that $$$PrefixXor(k) = T$$$ and $$$SuffixAnd(k) = T$$$, with $$$T = 2^{29}$$$. We use high-bit "flags" to ensure all elements are distinct and within the 31-bit integer range.

1. Suffix Construction (AND sum = $$$T$$$) To force the suffix AND to exactly $$$T$$$, every element must have the $$$29^{th}$$$ bit set, and the intersection of all other bits must be $$$0$$$. For $$$n-k=0$$$: $$$a_k = T$$$. For $$$n-k \gt 0$$$: * Set $$$a_k = T \mid 2^{30}$$$ (Anchor bit). Set $$$a_i = T \mid 2^{27} \mid i$$$ for the remaining elements. The bits $$$2^{30}$$$ and $$$2^{27}$$$ are unique to the suffix, ensuring distinctness. At the same time, the inclusion of $$$i$$$ (index) eventually clears all bits except $$$2^{29}$$$ during the AND operation.

2. Prefix Construction (XOR sum = $$$T$$$) We use the property $$$S \oplus (S \oplus T) = T$$$. Fill $$$a_0 \dots a_{k-2}$$$ with unique values: $$$2^{25} \mid (i+1)$$$. Let their XOR sum be $$$S$$$. Set the pivot $$$a_{k-1} = S \oplus T$$$. The $$$2^{25}$$$ flag ensures these values never collide with the suffix.

#include <bits/stdc++.h>

using namespace std;

void solve(){
    int n,k;
    cin>>n>>k;

    const long long T=(1LL<<29);
    const long long P_FLAG=(1LL<<25);
    const long long S_FLAG=(1LL<<27);
    const long long ANCHOR=(1LL<<30);

    vector<long long> a(n);

    if(n-k==1){
        a[k]=T;
    } 
    else{
        a[k]=T|ANCHOR;
        for(int i=k+1;i<n;i++){
            a[i]=T|S_FLAG|(long long)i;
        }
    }

    long long current_xor=0;
    for(int i=0;i<k-1;i++){
        a[i]=P_FLAG|(long long)(i+1);
        current_xor^=a[i];
    }
    
    a[k-1]=T^current_xor;

    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
    }
    cout<<"\n";
}

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

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

Problem Insight The values in the array are small, specifically in the range [1, 30]. This allows us to use bitmask dynamic programming based on prime factorizations. A subsequence is square-free if its product contains no repeated prime factor. Key Observations 1. Each prime factor can appear at most once in the subsequence. 2. Each number greater than 1 can be chosen at most once. 3. If a number x appears cnt[x] times and is selected, it contributes cnt[x] choices. Prime Mask Representation All primes up to 30 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Each number from 2 to 30 is mapped to a 10-bit mask representing its prime factors. Numbers divisible by a square are discarded. Dynamic Programming We define dp(mask, num), where mask represents used prime factors and num is the current number being processed. For each state, we either skip num or take it if its prime mask does not conflict. Handling Number 1 The number 1 has no prime factors and can be chosen any number of times. It contributes a multiplier of 2^{cnt[1]}. Final Answer The final result is dp(0, 30) multiplied by 2^{cnt[1]}, minus 1 to exclude the empty subsequence, taken modulo 10^9 + 7. Complexity Analysis Time Complexity: O(2^10 × 30) Space Complexity: O(2^10 × 30)

#include <bits/stdc++.h>
using namespace std;
 
#define vi vector<int>
#define ll long long
 
const ll mod = 1000000007;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
 
    int prime[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
 
    while (t--) {
        int n;
        cin >> n;
 
        vi nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
 
        unordered_map<int, int> m;
        int ones = 0;
 
        vi dp(1 << 10, 0), tmp;
        dp[0] = 1;
 
        for (int x : nums) {
            if (x % 4 == 0 || x % 9 == 0 || x % 25 == 0) continue;
            if (x == 1) ones++;
            else m[x]++;
        }
 
        for (auto &x : m) {
            int curr_mask = 0;
            for (int i = 0; i < 10; i++) {
                if (x.first % prime[i] == 0)
                    curr_mask |= (1 << i);
            }
 
            tmp.assign(1 << 10, 0);
            for (int mask = 0; mask < (1 << 10); mask++) {
                if ((mask & curr_mask) == 0) {
                    tmp[mask | curr_mask] =
                        (tmp[mask | curr_mask] + (ll)dp[mask] * x.second) % mod;
                }
            }
 
            for (int i = 0; i < (1 << 10); i++) {
                dp[i] = (dp[i] + tmp[i]) % mod;
            }
        }
 
        ll res = 0;
        for (int i = 1; i < (1 << 10); i++) {
            res = (res + dp[i]) % mod;
        }
 
        ll pow2 = 1;
        while (ones--) pow2 = (pow2 * 2) % mod;
 
        res = (res * pow2) % mod;
 
        cout << res << '\n';
    }
 
    return 0;
}

To unlock the vault, the problem translates into a graph reachability game where nodes are crystals and edges exist between numbers sharing a prime factor. Using DSU and Prime Factorization, we group the $$$N$$$ crystals into disjoint components based on their prime divisors. Kael and Liora can only "claim" a component if their base frequency ($$$X$$$ or $$$Y$$$) shares a prime factor with at least one element in that component. Logically, since players prioritize a Tie (Perfect Resonance) over a loss, the result is a Tie if and only if the union of all components reachable by Kael and Liora covers all $$$N$$$ crystals ($$$|Reach_K \cup Reach_L| = N$$$). If a Tie is impossible, the game reduces to a comparison of their maximum potential power: Kael wins if the total size of all components reachable by him is strictly greater than those reachable by Liora ($$$|Reach_K| \gt |Reach_L|$$$); otherwise, Liora wins.

#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#include <C:/Users/ajiit/Desktop/Future/Coding/Problem Solving/debug.cpp>
#endif
#define int long long
#define pii pair<int, int>
const int INF = 1e18;
const int MOD = 1e9 + 7;
 
const int SQ = 32000;
const int MX = 200005;
 
vector<int> mp(SQ + 1, 0);
vector<int> pr;
int arr[MX];
vector<int> fac[MX];
map<int, vector<int>> pos;
int n, x, y;
 
void sieve() {
    if (!pr.empty()) {
        return;
    }
    for (int i = 2; i <= SQ; ++i) {
        if (mp[i] == 0) {
            mp[i] = i;
            pr.push_back(i);
        }
        for (int p : pr) {
            if (p > mp[i] || i * p > SQ) {
                break;
            }
            mp[i * p] = p;
        }
    }
}
 
vector<int> getf(int v) {
    vector<int> f;
    for (int p : pr) {
        if (p * p > v) {
            break;
        }
        if (v % p == 0) {
            f.push_back(p);
            while (v % p == 0) {
                v /= p;
            }
        }
    }
    if (v > 1) {
        f.push_back(v);
    }
    return f;
}
 
vector<bool> bfs(int v) {
    vector<bool> rch(n, false);
    set<int> vis;
    queue<int> q;
    vector<int> sf = getf(v);
    for (int p : sf) {
        if (vis.find(p) == vis.end()) {
            vis.insert(p);
            q.push(p);
        }
    }
    while (!q.empty()) {
        int p = q.front();
        q.pop();
        if (pos.find(p) == pos.end()) {
            continue;
        }
        for (int i : pos[p]) {
            if (!rch[i]) {
                rch[i] = true;
                for (int np : fac[i]) {
                    if (vis.find(np) == vis.end()) {
                        vis.insert(np);
                        q.push(np);
                    }
                }
            }
        }
    }
    return rch;
}
 
void solve() {
    cin >> n >> x >> y;
    pos.clear();
    for (int i = 0; i < n; ++i) {
        fac[i].clear();
    }
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        fac[i] = getf(arr[i]);
        for (int p : fac[i]) {
            pos[p].push_back(i);
        }
    }
    
    vector<bool> r1 = bfs(x);
    vector<bool> r2 = bfs(y);
    
    int k = 0, l = 0, s = 0;
    for (int i = 0; i < n; ++i) {
        if (r1[i] && r2[i]) {
            s++;
        } else if (r1[i]) {
            k++;
        } else if (r2[i]) {
            l++;
        }
    }
 
    if (k + l + s == n) {
        cout << "Tie\n";
        return;
    }
 
    if (k > l) {
        cout << "Kael\n";
    } 
    else {
        cout << "Liora\n";
    }
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    sieve();
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
} 

DP. 2D-DP, with dp[i][j] stating min distance travelled from the initial point to (xi, jth integer in range). Transition is s1s2, if the gap size of the i-1th wall is s1 and the gap of the ith wall is s2. Time Complexity: $$$\sum_{i=1}^{i=n-1} wiw(i+1)$$$, where wi = window size of ith wall.

#include <bits/stdc++.h>
using namespace std;
 
typedef long long               ll;
typedef vector<ll>             vll;
typedef vector<vll>           vvll;
typedef long double             ld;
typedef vector<long double>    vld;
 
ld sq(ld x){
    return (x*x);
}
 
void solve(){
    ll n,tar; cin >>n >>tar;
    vvll ar(n+1, vll (3));
    ar[0] = {0,0,0};
    for(int i=0; i<n; i++){
        for(int j=0; j<3; j++) cin >>ar[i+1][j];
    }
    
    vector<vld> dp(103, vld(n+1, 1e18));
    dp[0][0] = 0;
 
    for(int i=1; i<n+1; i++){
        ld of1 = ar[i-1][1];
        for(ld j=ar[i-1][1]; j<=ar[i-1][2]; j++){
            ld of2 = ar[i][1];
            for(ld k=ar[i][1]; k<=ar[i][2]; k++){
                ld dis = sqrt( sq(k-j) + sq(ar[i][0]-ar[i-1][0]) );
                dp[k-of2][i] = min(dp[k-of2][i], dp[j-of1][i-1]+dis);
            }
        }
    }
 
    ld ans = 1e18;
    for(int i=0; i<103; i++){
        ans = min(ans, dp[i][n]+tar-ar[n][0]);
    }
cout << fixed << setprecision(10) << ans << "\n";\
    
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t;
    cin>>t;
    for(int i=0; i<t; i++){
        solve();
    }
    return 0;
}

1. Mathematical Formulation Let $$$P = [p_{1}, p_{2}, \dots, p_{N}]$$$ be a permutation of the integers $$$1, \dots, N$$$. The problem asks whether we can partition the index set $$${1, \dots, N}$$$ into two disjoint sets $$$J_{1}$$$ and $$$J_{2}$$$ such that: Partition:$$$J_{1} \cup J_{2} = {1, \dots, N}$$$ 2$J_{1} \cap J_{2} = \emptyset$ Strict Chronology: For any $$$k \in {1, 2}$$$ and any $$$i, j \in J_{k}$$$ with $$$i \lt j$$$, we require: $$$p_{i} \lt p_{j}$$$ That is, both induced subsequences must be strictly increasing. Perfect Symmetry:$$$|J_{1}| = |J_{2}| [cite_start]= \frac{N}{2}$$$. Immediate Constraint: If $$$N$$$ is odd, the condition $$$|J_{1}| = |J_{2}|$$$ is impossible. In this case, we immediately output UnBalanced.

2. Structural Decomposition: The permutation can be decomposed into independent subproblems based on its internal structure. Identification of Cut PointsA Cut Point is an index $$$k$$$ such that: $$$max(p_{1}, \dots, p_{k}) \lt min(p_{k+1}, \dots, p_{N})$$$. If such a point exists, the permutation can be split at $$$k$$$. Any increasing subsequence in the prefix can be concatenated with any increasing subsequence in the suffix without violating the ordering constraint. Using all cut points, we decompose $$$P$$$ into independent segments: $$$S_{1}, S_{2}, \dots, S_{m}$$$. Local Greedy Decomposition: For each segment, we determine whether it can be partitioned into two strictly increasing subsequences. Although Dilworth's Theorem applies in general, for $$$k=2$$$ a simpler greedy strategy suffices. Greedy Strategy: Assign all prefix maximums of the segment to subsequence $$$A$$$. Assign all remaining elements to the subsequence $$$B$$$. Subsequence $$$A$$$ is strictly increasing by construction. We explicitly verify that the subsequence $$$B$$$ is also strictly increasing. If not, the segment cannot be decomposed and the answer is UnBalanced. Let the lengths of the two subsequences for segment $$$i$$$ be $$$l_{i,1}, l_{i,2}$$$. We define: $$$b_{i} = min(l_{i,1}, l_{i,2})$$$ (base contribution) $$$w_{i} = |l_{i,1} - l_{i,2}|$$$ (imbalance weight).

3. The Balancing Problem (Subset Sum)Each segment contributes $$$b_{i}$$$ elements to both journals. Let: $$$B_{total} = \sum_{i=1}^{m} b_{i}$$$. The remaining capacity required to reach $$$\frac{N}{2}$$$ is: $$$K = \frac{N}{2} - B_{total}$$$. Each segment contributes an additional weight $$$w_{i}$$$ that must be assigned to exactly one journal. We must determine whether there exists a subset $$$I \subseteq {1, \dots, m}$$$ such that: $$$\sum_{i \in I} w_{i} = K$$$. This is the Subset Sum Problem.

#include<bits/stdc++.h>
using namespace std;
const int N=501000;
// Lucifer_K->
using B=bitset<N>;
 
void solve() {
    int n; cin>>n; 
    vector<int> a(n);
    for (int i=0; i<n; i++) cin>>a[i];
    if(n%2!=0){
       cout<<"UnBalanced\n"; 
       return;
    }
    vector<int> pf=a,sf=a;
    for (int i=1; i<n; i++) pf[i]=max(pf[i],pf[i-1]);
    for (int i=n-2; i>=0; i--) sf[i]=min(sf[i],sf[i+1]);
    vector<int> cps={0};
    for (int i=0; i<n-1; i++) if (pf[i]<sf[i+1]) cps.push_back(i+1);
 
    cps.push_back(n);
    vector<int> wf; int base=0;
    for (int k=0; k<cps.size()-1; k++) {
        int l=cps[k], r=cps[k+1];
        vector<int> s1,s2;
        for (int i=l; i<r; i++)
            if (a[i]==pf[i]) s1.push_back(a[i]);
           else s2.push_back(a[i]);
        for (int i=0; i<(int)s1.size()-1; i++) {
            if (s1[i]>=s1[i+1]) {
                cout<<"UnBalanced\n"; return;
            }
        }
        for (int i=0; i<(int)s2.size()-1; i++) {
            if (s2[i]>=s2[i+1]) {
                cout<<"UnBalanced\n"; return;
            }
        }
        int len1=s1.size(), len2=s2.size();
        base+=min(len1,len2);
        wf.push_back(abs(len1-len2));
    }
    vector<int> cnt(n+1,0);
    for (int i=0; i<wf.size(); i++) cnt[wf[i]]++;
    for (int i=1; i<=n; i++) {
        if (cnt[1]>2) {
            int p=(cnt[i]-1)/2;
            if (2*i<=n) {
                cnt[2*i]+=p;
                cnt[i]-=2*p;
            }
        }
    }
    B dp; dp[0]=1;
    for (int i=1; i<=n; i++) {
        for (int k=0; k<cnt[i]; k++) {
            dp|=dp<<i;
        }
    }
    int ans=(n/2)-base;
    if (ans>=0 && dp[ans]) cout<<"Balanced\n";
    else cout<<"UnBalanced\n";
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin>>t; while(t--) solve();
}

Here is the logic for Problem A. If b==a, then 0 operations are needed; if b-a=1, then no answer exists. And for all the other cases, the answer is possible.

#include <bits/stdc++.h>
 
using namespace std;
#define ll long long int
 
int main(){
    int t;
    cin>>t;
    while(t--){
        ll a,b;
        cin>>a>>b;
        ll x=0,y=(b-a);
        if(y==1){
            cout<<"-1\n";
        }
        else{
            cout<<(y+2)/3<<"\n";
        }     
    }
}

In this, we have to find the prefix sum and, at every index, if it is even, output 0; if it is odd, output 1.

#include <bits/stdc++.h>
 
using namespace std;
#define ll long long int
 
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector <ll> a(n);
        ll x=0;
        for(int i=0;i<n;i++){
            cin>>a[i];
            x+=a[i];
            cout<<x%2;
        }
        cout<<"\n";
        
    }
}

In this, we have to find the repetition of any lowercase alphabet in the power of 2. So we can use a map to count the characters, and then we can see. Let x = number of same characters present in the string. We can check this by doing x&(x-1) (AND operations) for every character total count, or we can also use a loop to count the value of power 2, and we can match at every index.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main(){
    int t;
    cin>>t;
    while(t--){
        string s;
        cin>>s;
        map<char,ll> mp;
        for(int i=0;i<s.length();i++){
            mp[s[i]]++;
        }
        ll x=0;
        for(auto [val,freq]:mp){
            if(freq>0&&((freq)&(freq-1))==0){
                cout<<val;
                x=1;
            }
        }
        if(x==0){
            cout<<"-1";
        }
        cout<<"\n";
    }
}

For minimum points, we have to replaced any elements with a or b; then we only get minimum points. So, We iterate through the string to find contiguous segments (triplets or longer) of the same character., and we need (all same elements/3) changes only.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
 
 
void solved() {
    int n; cin >> n;
    string s; cin >> s;
    long long ans = 0;
    for(int i = 0; i < n; ++i){
        int j = i;
        while(j < n && s[j] == s[i]) j++;
        int cnt = j-i;
        if(cnt >= 3){
            cnt /= 3;
            ans += cnt * 1LL * (int(s[i]) + (s[i] == 'a' ? int('b') : int('a')));
        }
        i = j-1;
    }
    cout << ans << "\n";
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solved();
    }
    return 0;
}

To solve the problem, we use Fermat's little theorem, which states that

when m is a prime and a is not divisible by m. Thus,

which allows us to calculate the answer efficiently.

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

int power(int a, int b, int m) {
    if (b == 0) return 1 % m;
    ll p = power(a, b / 2, m);
    p = p * p % m;
    if (b % 2 == 1) p = p * a % m;
    return p;
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        cout << power(a, power(b, c, 1e9 + 6), 1e9 + 7) << "\n";
    }
}
       

Water flows downstream ($$$1 \to 2 \to \dots$$$). For any prefix of length $$$i$$$, the maximum inflow rate is $$$i$$$ liters/second (using pipes $$$1$$$ to $$$i$$$).To fill the prefix volume $$$S_i$$$ within time $$$t$$$, we must satisfy:

We calculate this requirement for every prefix. maxx is the maximum of these values. This represents the absolute minimum time needed to fill the locks, even if we had infinite pipes available for the rest of the river.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main(){
    int t;
    cin>>t;
    vector <ll> a(t+1);
    ll maxx=0,sum=0;
    for(int i=1;i<=t;i++){
        cin>>a[i];
        sum+=a[i];
        maxx=max(maxx,(sum+i-1)/i);
    }
    ll q;
    cin>>q;
    while(q--){
        ll x;
        cin>>x;
        if(x<maxx){
            cout<<"-1\n";
        }
        else{
            cout<<(sum+x-1)/x<<"\n";
        }
 
    }
}     

1. Maximizing Subset Size (The Sorting Strategy): A key property of XOR is that if $$$A \oplus B = C$$$, the set $$${A, B, C}$$$ is linearly dependent. We can generate the same span using $$${A, B}$$$ (size 2) or $$${C}$$$ (size 1) given that $$$C$$$ is redundant if $$$A$$$ and $$$B$$$ are present. To maximize the subset size, we want to represent any value $$$V$$$ using the maximum number of elements. This is equivalent to prioritizing the insertion of "smaller" (or "atomic") elements into our basis. If a large number can be formed by XORing several smaller numbers, we prefer the smaller numbers because they increase the subset count. Therefore, the first step is to sort the input array $$$a$$$ in ascending order. By processing small numbers first, we fill the basis slots with them. If a larger number comes later and is linearly dependent on the smaller ones, it effectively reduces to zero and is discarded, which is exactly what we want (preserving the count from the smaller numbers).

2. Reconstructing the Subset (Basis Masking): Standard Gaussian elimination destroys the original numbers (e.g., $$$basis[i]$$$ might be $$$a_x \oplus a_y$$$). We need to know exactly which original $$$a_k$$$ values contribute to a specific basis vector. We can maintain the dependency graph using a shadow bitmask. Let's define three arrays: basis[i]: The reduced basis value for the $$$i$$$-th bit.origin[i]: The original input number that first claimed the $$$i$$$-th basis slot.mask[i]: An integer acting as a bitset. If the $$$j$$$-th bit is set in mask[i], it implies that origin[j] contributes to the value stored in basis[i]. Insertion Algorithm: When we try to insert a number val: Let curr_mask = 0. Iterate bits $$$k$$$ from 62 down to 0. If val has bit $$$k$$$ set: If basis[k] is empty: basis[k] = valorigin[k] stores the original number. mask[k] = curr_mask | (1 << k). (The recipe for this slot is the dependencies accumulated so far plus this slot itself). Terminate, If basis[k] is occupied:val ^= basis[k]curr_mask ^= mask[k] (We inherit the dependencies of basis[k]).

3. Final Selection: We perform the standard greedy strategy to find the Maximum XOR. We start with total_xor = 0 and final_mask = 0. Iterating from MSB to LSB: $$ \begin{aligned} &\text{if } (total_xor \oplus basis[i] > total_xor): \ &\quad total_xor \leftarrow total_xor \oplus basis[i] \ &\quad final_mask \leftarrow final_mask \oplus mask[i] \end{aligned} $$The final_mask tells us exactly which indices of the basis (and therefore which origin values) are required. We simply iterate through the bits of final_mask, collect the corresponding origin values, and print them.

#include <bits/stdc++.h>
using namespace std;
 
void fast_io(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
 
int main() {
    fast_io();
    int t;
    cin>>t;
    while(t--){
    int n;
   cin>>n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
 
    vector<long long> basis(64, 0);
    vector<long long> basis_origin(64, 0);
    vector<unsigned long long> basis_mask(64, 0);
 
    for (long long val : a) {
        long long current_val = val;
        unsigned long long current_mask = 0; 
 
        for (int i = 62; i >= 0; i--) {
            if ((current_val >> i) & 1) {
                if (basis[i] == 0) {
                    basis[i] = current_val;
                    basis_origin[i] = val; 
                    basis_mask[i] = current_mask | (1ULL << i); 
                    break;
                } else {
                    current_val ^= basis[i];
                    current_mask ^= basis_mask[i];
                }
            }
        }
    }
 
    long long max_xor = 0;
    unsigned long long final_subset_mask = 0;
 
    for (int i = 62; i >= 0; i--) {
        if ((max_xor ^ basis[i]) > max_xor) {
            max_xor ^= basis[i];
            final_subset_mask ^= basis_mask[i];
        }
    }
 
    vector<long long> result_subset;
    for (int i = 0; i <= 62; i++) {
        if ((final_subset_mask >> i) & 1) {
            result_subset.push_back(basis_origin[i]);
        }
    }
    
    sort(result_subset.begin(), result_subset.end());
 
    cout << max_xor << "\n";
    cout << result_subset.size() << "\n";
    for (int i = 0; i < result_subset.size(); i++) {
        cout << result_subset[i] << (i == result_subset.size() - 1 ? "" : " ");
    }
    cout << "\n";
 
  
    }
}