When Asmit needs exactly i operations to collect K blue balls, it means that the K blue balls are divided into i groups by the red balls. Let’s consider how to form such combinations as follows.

1. First, arrange the red balls in a row — there are N − K red balls.
2. Among the spaces between red balls (including the two ends), choose i positions to place the blue balls. The number of ways to choose these positions is

1. For each selection, determine how to distribute the K blue balls among the i chosen gaps, ensuring that each gap has at least one ball. The number of ways to do this is.

(*)

Therefore, for each i, the answer is

To compute the combinations, you can use the formula

or precompute factorials and modular inverses. However, since N ≤ 200000 in this problem, it is sufficient to use Pascal’s triangle via dynamic programming, where

(*) When arranging K balls and choosing i − 1 dividers from the K − 1 gaps between them, the balls are split into i groups. Each group contains at least one ball, and the total number of balls remains K.

#include <bits/stdc++.h>
using namespace std;
#define int long long
int mod = 1e9+7;

int binpowmod(int a, int b, int mod){
    if(b == 0) return 1;
    int x = binpowmod(a, b/2, mod);
    if(b%2) return (((x*x)%mod)*a)%mod;
    else return (x*x)%mod;
}

int binpow(int a, int b){
    if(b == 0) return 1;
    int x = binpow(a, b/2);
    if(b%2) return x*x*a;
    else return x*x;
}

int modinverse(int a, int mod){
    return binpowmod(a, mod-2, mod);
}


void solve(){
    int n,k;
    cin>>n>>k;
    int curr = n-k+1;
    cout<<curr<<'\n';
    for(int i=2; i<=k; i++){
        if(i > min(n-k+1, k)){
            cout<<"0\n";
            continue;
        }
        else{
            int temp = (((((k-i+1)%mod)*((n-k-i+2)%mod))%mod)*((modinverse(i-1,mod)*modinverse(i,mod))%mod))%mod;
            temp = (curr*temp)%mod;
            cout<<temp<<'\n';
            curr = temp;
        }
    }
}
int32_t main(){
    int t=1;
    while(t--){
        solve();
    }    
}

Consider a permutation of strictly decreasing numbers. This arrangement always produces the minimum possible value.

If we plot a graph with the indices on the x-axis and the permutation values on the y-axis, the index graph is strictly increasing. Observing all circular rotations of the permutation, the graph forms two broken decreasing sequences:

From this, we can conclude that the index graph intersects the permutation graph at most twice.

By further observation: 1.For permutations of odd length, the intersection occurs only once. 2.For permutations of even length, the intersection occurs twice.

TL;DR: If n is even, there are 2 intersections; if n is odd, there is 1 intersection.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t; cin >> t;
    while(t--) {
        long long n; cin >> n;
        n%2 == 0 ? cout << "2\n" : cout << "1\n";
    }
    return 0;
}

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

vector<vector<int>> rotate90(int n, const vector<vector<int>> &a)
{
    int ar, ac, br, bc;
    vector<vector<int>> b(n, vector<int>(n));
    for (ar = 0; ar < n; ++ar)
    {
        bc = ar;
        br = n - 1;
        for (ac = 0; ac < n; ++ac)
        {
            b[br][bc] = a[ar][ac];
            --br;
        }
    }
    return b;
}

bool solve(int n, const vector<int> &c, vector<vector<int>> &a)
{
    if (c[0] == c[n - 1])
    {
        int t = 4;
        while (t--)
        {
            for (int i = 0; i < n; ++i)
                a[n - 1][i] = c[i];
            a = rotate90(n, a);
        }
        return true;
    }
    else
    {
        int x = -1;
        for (int i = 1; i < n; ++i)
        {
            if (c[i] == c[0])
                x = i;
        }
        if (x == -1)
            return false;

        int y = -1;
        for (int i = n - 2; i >= 0; --i)
        {
            if (c[i] == c[n - 1])
                y = i;
        }
        if (y == -1)
            return false;

        if (x < y)
            return false;

        int t = 4;
        while (t--)
        {
            for (int i = 0; i < y; ++i)
                a[x][i] = c[i];
            for (int i = y; i <= x; ++i)
                a[n - 1][i] = c[i];
            for (int i = x + 1; i < n; ++i)
                a[n - 1 - y][i] = c[i];
            a = rotate90(n, a);
        }
        return true;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    while (cin >> n)
    {
        if (n == 0)
            break;

        vector<int> c(n);
        for (int i = 0; i < n; ++i)
            cin >> c[i];

        vector<vector<int>> a(n, vector<int>(n, 0));

        if (solve(n, c, a))
        {
            cout << "Yes\n";
            for (int i = 0; i < n; ++i)
            {
                for (int j = 0; j < n; ++j)
                    cout << a[i][j] << " ";
                cout << "\n";
            }
        }
        else
        {
            cout << "No\n";
        }
    }

    return 0;
}

First of all, the answer is no if R != B because there is no perfect matching. To check if there is a perfect matching satisfying the conditions, it is possible to go through all the assignments and check if any of them is good. There are O(R!) assignments and checking each one of them takes O(R2 ). This gives the naive solution and is enough to pass all the tests, but rather difficult to implement. A more elegant O(1) solution is to use the fact that the answer is yes if and only if the number of spaceships and bases are the same. In fact, an assignment whose sum of segment (path) lengths is minimum will not have any intersection. We can prove it by contradiction. Let’s assume that there exists a pair of intersected segments AB, CD, where A and C are spaceships and B, D are bases. If we change the assignment to AD and CB, due to the triangle inequality, the sum of segment lengths will decrease and we obtain a new assignment whose sum of segment lengths is smaller than the minimum value. A contradiction. Therefore, it is guaranteed to have an assignment without intersections as long as the number of spaceships and bases are the same. TL;DR: Just answer YES if R = B and NO otherwise

#include <bits/stdc++.h>
using namespace std;
int main() {
    int r,b; cin >> r >> b;
    for(int i=0;i<r;i++) {
        int x,y; cin >> x >> y;
    }
    for(int i=0;i<b;i++) {
        int x,y; cin >> x >> y;
    }
    r==b ? cout << "Yes" : cout << "No";
    return 0;
}

This problem can be efficiently solved using dynamic programming with prefix sums.

Let $$$Dp[n][is]$$$ represent the number of ways to obtain a total length of n in a k-tree, where

is = 1: there exists at least one edge with length ≥ d

is = 0: all edges have lengths < d

Base Case:

There is exactly one way to make a total length of 0 — by taking no edges, and clearly, no edge can have length ≥ d in this case.

Transition: For each n, we consider all possible first edges of lengths 1 to k. Instead of directly iterating over all possible edge lengths (which would lead to O(nk) complexity), we can use prefix sums to compute transitions efficiently.

Let

Then, the transitions can be written as:

These prefix sums allow us to compute each state in O(1) time, leading to an overall O(n) complexity.

Complexity: Time: O(n) Space: O(n) (can be reduced further to O(1) with rolling sums)

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;

int main() {
    int n, k, d;
    cin >> n >> k >> d;

    vector<long long> dp0(n + 1, 0), dp1(n + 1, 0);
    vector<long long> pref0(n + 1, 0), pref1(n + 1, 0);

    dp0[0] = 1;
    pref0[0] = 1;

    for (int i = 1; i <= n; ++i) {
        int l0 = max(0, i - (d - 1));
        dp0[i] = (pref0[i - 1] - (l0 - 1 >= 0 ? pref0[l0 - 1] : 0) + MOD) % MOD;

        int l1 = max(0, i - k);
        dp1[i] = (pref1[i - 1] - (l1 - 1 >= 0 ? pref1[l1 - 1] : 0) + MOD) % MOD;

        int l2 = max(0, i - k);
        int r2 = i - d;
        if (r2 >= 0)
            dp1[i] = (dp1[i] + pref0[r2] - (l2 - 1 >= 0 ? pref0[l2 - 1] : 0) + MOD) % MOD;

        pref0[i] = (pref0[i - 1] + dp0[i]) % MOD;
        pref1[i] = (pref1[i - 1] + dp1[i]) % MOD;
    }

    cout << dp1[n] % MOD << "\n";
    return 0;
}

To do this efficiently, we can use binary search. Let’s maintain a segment [l, r] that is guaranteed to contain the k-th island. Initially, this segment represents the entire Grand Line.

At each step, we check the middle point: Let $$$m = (l + r) / 2$$$. We query how many warships are there in the segment $$$[l, m]$$$.

From this, we can easily find out how many islands are in $$$[l, m]$$$ since: number of islands = (m — l + 1) — number of warships. If there are at least $$$k$$$ islands in the left half, then we know the $$$k^{th}$$$ island must lie within $$$[l, m]$$$, and we narrow our search to that half. Otherwise, if there are only $$$x \lt k$$$ islands in the left half, we move to the right half $$$[m + 1, r]$$$ and now search for the $$$(k - x)^{th}$$$ island instead.

By continuing this process, the segment keeps shrinking until we pinpoint the exact island where the “One Piece” lies.

This method ensures that Swarn D. Banner can find his destination in $$$O(log n)$$$ queries — well within the limit of 56.

And just like that, with precise navigation and clever reasoning, Banner stretches his arm across the Grand Line and lands directly on the island holding the “One Piece,” ready to take his place as the next Pirate King.

#include <bits/stdc++.h>

using namespace std;

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

void calc(int l, int r, int k) {
    if (l == r) {
        cout << "! " << l << endl;
        return;
    }
    int m = (l + r) / 2;
    cout << "? " << l << " " << m << endl;
    int sum;
    cin >> sum;
    if ((m - l + 1) - sum >= k) {
        calc(l, m, k);
    } else {
        calc(m + 1, r, k - (m - l + 1) + sum);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    calc(1, n, k);
}

To solve this problem, we need to manage a segment tree that stores specific information for each segment of the stones.

Each node in the segment tree should maintain the following values:

• n1: number of calm stones (1’s) in the node’s range.
• n6: number of fierce stones (6’s) in the node’s range.
• n16: length of the longest non-decreasing subsequence (vibe chain) in the node’s range.
• n61: length of the longest non-increasing subsequence in the node’s range.

When Somnath performs a flipflop operation on a range of stones, we simply swap the values: swap(n1, n6) and swap(n16, n61).

This is because flipping calm and fierce stones reverses their nature, so increasing sequences become decreasing ones and vice versa.

When we combine two child nodes to update their parent node, the rules are as follows:

n1(parent) = n1(left_child) + n1(right_child)

n6(parent) = n6(left_child) + n6(right_child)

n16(parent) = max(  n16(left_child) + n6(right_child),  n1(left_child) + n16(right_child),  n1(left_child) + n6(right_child) )

n61(parent) = max(  n61(left_child) + n1(right_child),  n6(left_child) + n61(right_child),  n6(left_child) + n1(right_child) )

This way, every node stores all the necessary information to answer queries efficiently.

For each vibe-check query, the result is the value of n16 for the entire range — representing the length of the longest non-decreasing subsequence of stones at that moment.

Thus, by maintaining these values and properly updating them during flipflop operations, we can efficiently simulate the magical battle between Somnath and Tanish as they manipulate the aura of the mystic stones.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

string s;

struct node
{
    int one, six, Vsix, Vone;
};

vector<node> seg;
vector<bool> lazy;

void upd(int c)
{
    seg[c].one = seg[c << 1].one + seg[c << 1 | 1].one;
    seg[c].six = seg[c << 1].six + seg[c << 1 | 1].six;
    seg[c].Vsix = max({seg[c].one, seg[c].six,
                       seg[c << 1].one + seg[c << 1 | 1].six,
                       seg[c << 1].one + seg[c << 1 | 1].Vsix,
                       seg[c << 1].Vsix + seg[c << 1 | 1].six});
    seg[c].Vone = max({seg[c].one, seg[c].six,
                       seg[c << 1].six + seg[c << 1 | 1].one,
                       seg[c << 1].six + seg[c << 1 | 1].Vone,
                       seg[c << 1].Vone + seg[c << 1 | 1].one});
}

void build(int c, int b, int e)
{
    if (e - b == 1)
    {
        if (s[b] == '1')
        {
            seg[c].one = seg[c].Vsix = seg[c].Vone = 1;
        }
        else
        {
            seg[c].six = seg[c].Vsix = seg[c].Vone = 1;
        }
        return;
    }
    int m = (b + e) >> 1;
    build(c << 1, b, m);
    build(c << 1 | 1, m, e);
    upd(c);
}

void push(int c)
{
    if (lazy[c])
    {
        swap(seg[c << 1].one, seg[c << 1].six);
        swap(seg[c << 1].Vsix, seg[c << 1].Vone);
        swap(seg[c << 1 | 1].one, seg[c << 1 | 1].six);
        swap(seg[c << 1 | 1].Vsix, seg[c << 1 | 1].Vone);
    }
    lazy[c << 1] = lazy[c] ^ lazy[c << 1];
    lazy[c << 1 | 1] = lazy[c] ^ lazy[c << 1 | 1];
    lazy[c] = false;
}

void update(int c, int b, int e, int l, int r)
{
    if (r <= b || l >= e)
    {
        return;
    }
    if (l <= b && r >= e)
    {
        swap(seg[c].one, seg[c].six);
        swap(seg[c].Vsix, seg[c].Vone);
        lazy[c] = !lazy[c];
        return;
    }
    push(c);
    int m = (b + e) >> 1;
    update(c << 1, b, m, l, r);
    update(c << 1 | 1, m, e, l, r);
    upd(c);
}

int main()
{
    cin.tie(nullptr)->ios::sync_with_stdio(false);
    int n, q;
    cin >> n >> q >> s;
    seg.resize(n << 2);
    lazy.resize(n << 2);
    build(1, 0, n);
    while (q--)
    {
        string op;
        cin >> op;
        if (op == "vibe-check")
        {
            cout << seg[1].Vsix << '\n';
        }
        else
        {
            int l, r;
            cin >> l >> r;
            l--;
            update(1, 0, n, l, r);
        }
    }
    return 0;
}