Let's view it as when monsters $$$x$$$ and $$$y$$$ fight, their health changes into $$$\max(x-y,0)$$$ and $$$\max(y-x,0)$$$ respectively. So any monster with $$$0$$$ health is considered dead. Therefore, a player loses when the health of his monsters are all $$$0$$$.

Notice that $$$\max(x-y,0)=x-\min(x,y)$$$ and $$$\max(y-x,0)=y-\min(x,y)$$$. Therefore, after each step, the sum of the health of monsters decrease by the same amount for both players.

Therefore, we only need to know $$$\sum a_i$$$ and $$$\sum b_i$$$ to determine who wins. If $$$\sum a_i > \sum b_i$$$, Tsondu wins. Else if $$$\sum a_i < \sum b_i$$$, Tenzing wins. Else, it is a draw.

#include <iostream>

using namespace std;

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n, m, a[50], b[50];
        long long sumA = 0, sumB = 0;
        cin >> n >> m;
        for (int i = 0; i < n; i++)
            cin >> a[i], sumA += a[i];
        for (int i = 0; i < m; i++)
            cin >> b[i], sumB += b[i];
        if (sumA > sumB) cout << "Tsondu\n";
        if (sumA < sumB) cout << "Tenzing\n";
        if (sumA == sumB) cout << "Draw\n";
    }
}

Observe the bitwise OR: if a bit of the knowledge changes to $$$1$$$, it will never become $$$0$$$.

It tells us, if a book has difficulty rating $$$y$$$, and $$$x|y \neq x$$$, Tenzing will never read this book because it will change a $$$0$$$ bit in $$$x$$$ to $$$1$$$.

We called a number $$$y$$$ valid if $$$x|y=x$$$. For each sequence, we can find a longest prefix of it such that all numbers in this prefix are valid. Find the bitwise OR of the three prefix and check whether it equals to $$$x$$$.

Time complexity: $$$O(n)$$$ per test case.

A naive approach is to enumerate the prefixes of the three stacks, which is an enumeration of $$$n^3$$$. For each stack, the bitwise OR of the prefix has at most $$$31$$$ different values (including empty prefix), because the bitwise OR of the prefix is non-decreasing, and each change will increase the number of 1s in binary. Since the number of 1s in binary cannot exceed $$$30$$$, it can be changed at most 30 times. Therefore, the enumeration is reduced to $$$\min(n,31)^3$$$. In the worst case, the time complexity is $$$O(\sum n * 31^2)$$$.

#include <iostream>

using namespace std;

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n, x, a[100000];
        cin >> n >> x;
        int s = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < n; j++) cin >> a[j];
            for (int j = 0; j < n; j++) {
                if ((x | a[j]) != x) break;
                s |= a[j];
            }
        }
        if (s == x) cout << "YES\n";
        else cout << "NO\n";
    }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n, x, ai;
        cin >> n >> x;
        vector<int> pre[3];
        for (int i = 0; i < 3; i++) {
            int s = 0;
            pre[i].push_back(s);
            for (int j = 0; j < n; j++) {
                cin >> ai;
                if ((s | ai) != s)
                    s |= ai, pre[i].push_back(s);
            }
        }
        bool ans = 0;
        for (int A : pre[0]) for (int B : pre[1]) for (int C : pre[2])
            ans |= (A | B | C) == x;
        cout << (ans ? "YES\n" : "NO\n");
    }
}

Let us write down the original index of each range we delete.

Firstly, it is impossible to delete ranges $$$(a,c)$$$ and $$$(b,d)$$$ where $$$a<b<c<d$$$.

Secondly, if we delete ranges $$$(a,d)$$$ and $$$(b,c)$$$ where $$$a<b<c<d$$$, we must have deleted range $$$(b,c)$$$ before deleting range $$$(a,d)$$$. Yet, the effect of deleting range $$$(b,c)$$$ and then $$$(a,d)$$$ is the same as only deleting $$$(a,d)$$$.

Therefore, we can assume that in an optimal solution, the ranges we delete are all disjoint. Therefore, we want to find some disjoint range $$$[l_1,r_1],[l_2,r_2],...,[l_m,r_m]$$$ such that $$$a_{l_i}=a_{r_i}$$$ and $$$\sum (r_i-l_i+1)$$$ is maximized.

We can write a DP. $$$dp_i$$$ denotes the minimum number of points we do not delete when considering the subarray $$$a[1\ldots i]$$$. We have $$$dp_i=\min(dp_{i-1}+1,\min\{dp_j|a_{j+1}=a_i,j+1<i\})$$$.

This dp can be calculated in $$$O(n)$$$ since we can store for each $$$x$$$ what the minimum $$$dp_j$$$ which satisfy $$$a_{j+1}=x$$$.

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        const int N = 200000 + 5;
        int n, a[N], dp[N], buc[N];
        cin >> n;
        dp[0] = 0;
        for (int i = 1; i <= n; i++) buc[i] = 0x3f3f3f3f;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            dp[i] = min(dp[i - 1] + 1, buc[a[i]]);
            buc[a[i]] = min(buc[a[i]], dp[i - 1]);
        }
        cout << n - dp[n] << '\n';
    }
}

Consider the restrictions on $$$u$$$, $$$v$$$, and $$$y$$$ as a weighted edge between $$$u$$$ and $$$v$$$ with weight $$$y$$$. Obviously, the final answer will not exceed the shortest path from $$$1$$$ to $$$n$$$.

One possible approach to construct the solution is to start with the set $$${1}$$$ and add vertices one by one. If $$$i$$$ is added to the set at time $$$T_i$$$, then we need to ensure that $$$|T_u-T_v|\leq y$$$ for any edge between $$$u$$$ and $$$v$$$ in the set. This can be modeled as a system of difference constraints problem and solved using shortest path algorithms.

To be more specific, we can add vertices in increasing order of their distances from $$$1$$$. The time for each set can be calculated as the difference between the distances from $$$1$$$ to the two adjacent vertices in the sorted order.

#include <bits/stdc++.h>

using namespace std;

int n, m;
long long dis[100][100];

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> n >> m;
    memset(dis, 0x3f, sizeof dis);
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w, u--, v--;
        dis[u][v] = dis[v][u] = w;
    }
    for (int i = 0; i < n; i++) dis[i][i] = 0;
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    if (dis[0][n - 1] > 1e18)
        cout << "inf", exit(0);
    int ord[100];
    iota(ord, ord + n, 0);
    sort(ord + 1, ord + n, [](int a, int b) {
        return dis[0][a] < dis[0][b];
    });
    string s(n, '0');
    vector<pair<string, int>> ans;
    for (int i = 0; i < n - 1; i++) {
        int u = ord[i], v = ord[i + 1];
        s[u] = '1';
        ans.emplace_back(s, dis[0][v] - dis[0][u]);
        if (v == n - 1) break;
    }
    cout << dis[0][n - 1] << ' ' << ans.size() << '\n';
    for (auto [s, t] : ans)
        cout << s << ' ' << t << '\n';
}

Observe that all triangles will be disjoint, if two triangle were not disjoint, we can merge them together to such that the cost used is less. Therefore, we can consider doing DP.

The oblique side of the triangle is a segment on the line $$$y=k-x$$$. Therefore, we use the interval $$$[L,R]$$$ to represent the triangle with the upper left corner at $$$(L,k-L)$$$ and the lower right corner at $$$(R,k-R)$$$.

First, suppose that all points will generate costs. After covering points with a triangle, the costs can be reduced. Let $$$f(L,R)$$$ represent the sum of costs of points covered by triangle $$$[L,R]$$$ minus $$$A\times (R-L)$$$. We need to find several intervals $$$[l_1,r_1],[l_2,r_2],\cdots,[l_m,r_m]$$$ without common parts and maximize $$$\sum f(l_i,r_i)$$$.

Let $$$dp_i$$$ represent the maximum value of $$$\sum f(l_i,r_i)$$$ when considering the prefix $$$[1,i]$$$. There are two transitions:

• If $$$i$$$ is not covered by any interval, then $$$dp_i\leftarrow dp_{i-1}$$$.
• If $$$i$$$ is covered by interval $$$[j+1,i]$$$, then $$$dp_i\leftarrow dp_j+f(j+1,i)$$$.

Enumerate from small to large for $$$i$$$, maintain $$$g_j=dp_j+f(j+1,i)$$$. When $$$i-1\rightarrow i$$$, $$$g$$$ will change as follows:

• Subtract $$$A$$$ from $$$g_{0\dots i-1}$$$.
• For each point $$$(x,k-i)$$$, add the cost of the point to $$$g_{0\dots x}$$$.

$$$g$$$ needs to support interval addition and global maximum value (assuming that illegal positions are 0), which can be achieved using a segment tree.

Time complexity is $$$O((n+k)\log k)$$$.

Please first understand the approach in the tutorial. A triangle $$$[L, R]$$$ can cover a point $$$(x, y)$$$ iff $$$L\le x$$$ and $$$k-y\le R$$$. Therefore, point $$$(x,y)$$$ can be regarded as interval $$$[x,k-y]$$$. Now the problem is transformed into one where some intervals $$$[l,r]$$$ have a cost of $$$w$$$, and you can place some non-overlapping intervals. If $$$[l,r]$$$ is not included in any placed interval, then you need to pay a cost of $$$w$$$. Further transformation: you can pay a cost of $$$A$$$ to cover $$$[i,i+1]$$$, and for an interval $$$[l,r]$$$ with a cost of $$$w$$$, if interval $$$[l,r]$$$ is not completely covered, then you need to pay a cost of $$$w$$$. Try to use minimum cut to solve this problem:

• First establish a bipartite graph with $$$n$$$ left nodes representing the points in the original problem and $$$k$$$ right nodes representing intervals $$$[i,i+1]$$$.
• The source node is connected to each left node with an edge capacity equal to the node's cost.
• Each right node is connected to the sink node with an edge capacity of $$$A$$$.
• For each left node representing interval $$$[l,r]$$$, it is connected to right nodes $$$l,l+1,l+2,...,r-1$$$ with an edge capacity of infinity.

According to the maximum flow minimum cut theorem, let's consider how to find the maximum flow of this graph.

This is basically a maximum matching problem of a bipartite graph. Each left node can match an interval on the right side, and each node has matching frequency restriction. A greedy algorithm: First sort all intervals in increasing order of the right endpoint, then consider each interval in turn and match it with positions within the interval from left to right. Specifically, let $$$cnt_i$$$ represent how many times the $$$i$$$-th point on the right side can still be matched. Initially, $$$cnt_{0\dots k-1}=A$$$. For each interval $$$[l,r]$$$ that can be matched at most $$$w$$$ times, each time find the smallest $$$i$$$ in $$$[l,r-1]$$$ such that $$$cnt_i\ne 0$$$, and match $$$\min(cnt_i,w)$$$ times with $$$i$$$.

Use a Disjoint Set Union to query the smallest $$$i\ge l$$$ such that $$$cnt_i\ne 0$$$. The time complexity is $$$O(n\alpha(n))$$$.

The Method of Four Russians can also be used to achieve $$$O(n)$$$ time complexity. Divide the sequence into blocks of $$$64$$$, use bit operations and __builtin_ctzll for searching within the block, and use Disjoint Set Union to skip blocks where $$$cnt_i$$$ is all $$$0$$$. In this way, the union operation only needs $$$O(\frac n{\log n})$$$ times and the find operation only needs $$$O(n)$$$ times. It can be proved that in this case, the time complexity of Disjoint Set Union is $$$O(n)$$$ instead of $$$O(n\alpha(n))$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 2e5 + 8, M = 1 << 18;
 
int n, k, A, c[M << 1][2], dp[N];
vector<pair<int, int>> p[N];
 
void insert(int i, int v) {
    for (i += M; i; i >>= 1) c[i][0] = v, v = max(v, c[i ^ 1][0]);
}
void add(int i, int v) {
    for (i += M + 1; i > 1; i >>= 1) {
        int v1 = i & 1 ? v : 0;
        c[i ^ 1][0] += v1, c[i ^ 1][1] += v1;
        c[i >> 1][0] = max(c[i][0], c[i ^ 1][0]) + c[i >> 1][1];
    }
}
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> n >> k >> A;
    int sum = 0;
    while (n--) {
        int x, y, w;
        cin >> x >> y >> w;
        p[k - y].emplace_back(x, w);
        sum += w;
    }
    for (int i = 1; i <= k; i++) {
        add(i - 1, -A);
        for (auto [x, w] : p[i]) add(x, w);
        dp[i] = max(dp[i - 1], c[1][0]);
        insert(i, dp[i]);
    }
    cout << sum - dp[k] << '\n';
}

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 8;

int n, k, A, cnt[N], pa[N];
vector<pair<int, int>> v[N];

int find(int x) {
    return !pa[x] ? x : pa[x] = find(pa[x]);
}
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> n >> k >> A;
    while (n--) {
        int x, y, w;
        cin >> x >> y >> w;
        v[k - y].emplace_back(x, w);
    }
    for (int i = 0; i < k; i++) cnt[i] = A;
    int ans = 0;
    for (int r = 1; r <= k; r++)
        for (auto [l, w] : v[r])
            while (l < r) {
                int tmp = min(w, cnt[l]);
                ans += tmp, cnt[l] -= tmp, w -= tmp; 
                if (!cnt[l]) l = pa[l] = find(l + 1);
                if (!w) break;
            }
    cout << ans << '\n';
}

#include <bits/stdc++.h>

struct IO {
    static const int inSZ = 1 << 17;
    char inBuf[inSZ], *in1, *in2;
    inline __attribute((always_inline))
    int read() {
        if(__builtin_expect(in1 > inBuf + inSZ - 32, 0)) {
            auto len = in2 - in1;
            memcpy(inBuf, in1, len);
            in1 = inBuf, in2 = inBuf + len;
            in2 += fread(in2, 1, inSZ - len, stdin);
            if(in2 != inBuf + inSZ) *in2 = 0;
        }
        int res = 0;
        unsigned char c = *in1++;
        while(res = res * 10 + (c - 48), (c = *in1++) >= 48);
        return res;
    }
    IO() {
        in1 = inBuf;
        in2 = in1 + fread(in1, 1, inSZ, stdin);
    }
} IO;
inline int read() { return IO.read(); }

using namespace std;

const int N = 2e5 + 8, N2 = N / 64 + 8;

int n, k, A, pts[N][3], buc[N], LW[N][2];
int cnt[N], pa[N2], Rp[N];
uint64_t mask[N2];

int find(int x) {
    return pa[x] < 0 ? x : pa[x] = find(pa[x]);
}

int main() {
    n = read(), k = read(), A = read();
    for (int i = 0; i < n; i++) {
        pts[i][1] = read();
        pts[i][0] = k - read();
        pts[i][2] = read();
        buc[pts[i][0]]++;
    }
    for (int i = 1; i <= k; i++) buc[i + 1] += buc[i];
    for (int i = 0; i < n; i++) {
        int t = --buc[pts[i][0]];
        memcpy(LW[t], pts[i] + 1, 8);
    }
    for (int i = 0; i < k; i++) cnt[i] = A;
    memset(mask, 0xff, sizeof mask);
    memset(pa, -1, sizeof pa);
    iota(Rp, Rp + N2, 0);
    int ans = 0;
    for (int r = 1; r <= k; r++)
        for (int i = buc[r]; i < buc[r + 1]; i++) {
            int l = LW[i][0], w = LW[i][1];
            ans += w;
            int lb = Rp[find(l >> 6)], rb = r >> 6;
            auto S0 = mask[lb];
            if (lb == l >> 6) S0 &= ~0ULL << (l & 63);
            while (lb < rb) {
                auto S = S0;
                for (; S; S &= S - 1) {
                    int p = lb * 64 + __builtin_ctzll(S);
                    int tmp = min(w, cnt[p]);
                    cnt[p] -= tmp, w -= tmp;
                    if (!w) break;
                }
                mask[lb] ^= S0 ^ S;
                if (!w) break;
                int nxt = find(lb + 1);
                if (!mask[lb]) {
                    lb = find(lb);
                    if (pa[nxt] > pa[lb]) swap(nxt, lb), Rp[nxt] = Rp[lb];
                    pa[nxt] += pa[lb], pa[lb] = nxt;
                }
                lb = Rp[nxt], S0 = mask[lb];
            }
            if (w != 0 & lb == rb) {
                S0 &= (1ULL << (r & 63)) - 1;
                auto S = S0;
                for (; S; S &= S - 1) {
                    int p = lb * 64 + __builtin_ctzll(S);
                    int tmp = min(w, cnt[p]);
                    cnt[p] -= tmp, w -= tmp;
                    if (!w) break;
                }
                mask[lb] ^= S0 ^ S;
            }
            ans -= w;
        }
    cout << ans << '\n';
}

Let $$$root$$$ be the centroid of all black vertices and $$$size_i$$$ be the number of black vertices in the subtree of node $$$i$$$.

Then the value is $$$\sum_{i\neq root} k-2\cdot size_i=(n-1)\cdot k-2\cdot\sum_{i\neq root} size_i$$$.

Consider painting node $$$i$$$ black, the total contributio to all of its ancestors is $$$2\cdot depth_i$$$, where $$$depth_i$$$ is the distance from $$$root$$$ to $$$i$$$.

Since we want to maximize the value, we can greedily select the node with the smallest $$$depth_i$$$.

But how do we ensure that $$$root$$$ is the centroid after selecting other black vertices? We can simply take the maximum of all possible $$$root$$$ because if a node is not the centroid, some edges will have a negative weight, making it worse than the optimal answer.

Enumerate all possible $$$root$$$ and use BFS to add vertices based on their distance to $$$root$$$. The complexity is $$$O(n^2)$$$.

#include <bits/stdc++.h>

using namespace std;

const int N = 5000 + 8;

int n, ans[N];
vector<int> G[N];

void bfs(int u) {
    static int q[N], dis[N];
    memset(dis, -1, sizeof dis);
    q[1] = u, dis[u] = 0;
    for (int l = 1, r = 2; l < r; l++) {
        u = q[l];
        for (int v : G[u]) if (dis[v] < 0)
            dis[v] = dis[u] + 1, q[r++] = v;
    }
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += dis[q[i]]; 
        ans[i] = max(ans[i], (n - 1) * i - sum * 2);
    }
}
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v, u--, v--;
        G[u].push_back(v), G[v].push_back(u);
    }
    for (int i = 0; i < n; i++) bfs(i);
    for (int i = 0; i <= n; i++)
        cout << ans[i] << ' ';
}

Before starting to solve this problem, let's establish two basic properties:

• For two completely independent random variables $$$x_1,x_2$$$, we have $$$E(x_1x_2) = E(x_1)E(x_2)$$$.
• For $$$(a+b)\times (c+d)$$$, we have $$$E((a+b)\times (c+d)) = E(ac) + E(ad) + E(bc) + E(bd)$$$.

Returning to this problem, let $$$x_{i,j}$$$ be a random variable: its value is $$$v$$$ when the $$$i$$$-th operation sets $$$a_j$$$ to $$$a_j + v$$$, otherwise it is $$$0$$$.

Then note that the answer is the expected value of $$$\prod_{i=1}^{n}(a_i+\sum_{j=1}^{m}x_{j,i})$$$.

Applying the second property above to split the product, each term is a product of some $$$a_i$$$ and $$$x$$$.

Specifically, each term has $$$n$$$ factors, and for each $$$i\in [1,n]$$$, either $$$a_i$$$ is one of its factors, or some $$$x_{j,i}$$$ is one of its factors.

Let's investigate the expectation of a specific term. Note that if $$$i_1\lt i_2$$$, then $$$E(x_{j,i_1}\times x_{j,i_2}) = E(x_{j,i_1})\times v$$$, that is, if $$$x_{j,i_1}$$$ is $$$0$$$ then the whole product is $$$0$$$, and if $$$x_{j,i_1}$$$ is $$$v$$$ then $$$x_{j,i_2}$$$ must be $$$v$$$.

Therefore, for all the $$$x$$$ factors in a term, we categorize them by the first index, i.e. we group all $$$x_{j,...}$$$ into category $$$j$$$. For each category, we only need to focus on the first variable. If it's $$$v$$$, then the remaining variables take value $$$v$$$, otherwise the result is $$$0$$$. Note that the variables in different categories are completely independent (because their values are determined by operations in two different rounds), so the expected product of the variables in two categories can be split into the product of the expected products of the variables within each category.

Our goal is to compute the expected sum of all the terms, which can be nicely combined with DP:

Let $$$dp(i,j)$$$ be the value that we have determined the first $$$i$$$ factors of each term and there are $$$j$$$ categories that have appeared at least once (if adding the variable at position $$$i+1$$$ brings contribution $$$v$$$, otherwise the contribution is $$$\frac{i+1}{n}\times v$$$). The transition can be easily calculated with $$$O(1)$$$, depending on whether to append $$$a_{i+1}$$$ or $$$x_{...,i+1}$$$ to each term, and if it's the latter, we discuss whether the variable belongs to one of the $$$j$$$ categories that have appeared or the other $$$m-j$$$ categories. The time complexity is $$$O(n\times \min(n,m))$$$.

#include <bits/stdc++.h>

using namespace std;

const int N = 5000 + 8, P = 1e9 + 7;

int n, m, v, a[N], coef[N], dp[N][N];

long long Pow(long long a, int n) {
    long long r = 1;
    while (n) {
        if (n & 1) r = r * a % P;
        a = a * a % P, n >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> n >> m >> v;
    for (int i = 1; i <= n; i++) cin >> a[i];
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        auto coef = i * Pow(n, P - 2) % P * v % P;
        for (int j = 0; j < i; j++) {
            dp[i][j + 1] = dp[i - 1][j] * coef % P * (m - j) % P;
            dp[i][j] = (dp[i][j] + dp[i - 1][j] * (a[i] + 1LL * j * v % P)) % P;
        }
    }
    int ans = 0;
    for (int i = 0; i <= n; i++)
        (ans += dp[n][i]) %= P;
    cout << ans << '\n';
}

Ignoring time complexity for now, how do we calculate the answer? The first step is to enumerate which variables are $$$<0.5$$$ and which variables are $$$>0.5$$$.

Sort all variables $$$x_i$$$ by $$$\min(x_i,1-x_i)$$$ and enumerate the sorted result (referring to the permutation).

Suppose no variable equals $$$0.5$$$, because the probability of being equal to $$$0.5$$$ is $$$0$$$, variables less than $$$0.5$$$ are called white vertices, and those greater than $$$0.5$$$ are called black vertices. Each black and white coloring is equiprobable, so we can calculate the probability that satisfies all conditions for each black and white coloring, and then take the average.

For two variables less than $$$0.5$$$, the condition of $$$\le 1$$$ is always satisfied, and the condition of $$$\ge 1$$$ is never satisfied. Therefore, we do not need to consider the conditions between same-colored points. The condition between white vertex $$$u$$$ and black vertex $$$v$$$, $$$x_u+x_v\le 1$$$, is satisfied only when $$$x_u\le 1-x_v$$$. Let $$$y_u=\min(x_u,1-x_u)=\begin{cases}x_u&(u\text{ is white})\\1-x_u&(u\text{ is black})\end{cases}$$$, then $$$y_u$$$ can be regarded as a random variable in $$$[0,0.5)$$$, for $$$\le 1$$$ condition, the white vertex's $$$y$$$ must be less than or equal to the black vertex's $$$y$$$, so we add an edge from the white vertex to the black vertex; for $$$\ge 1$$$ condition, we add an edge from the black vertex to the white vertex.

We get a directed graph that restricts the size relationship of $$$y_{1\cdots n}$$$. Suppose that sorting $$$y_{1\cdots n}$$$ from small to large is $$$y_{p_1},y_{p_2},\cdots,y_{p_n}$$$, then each permutation $$$p$$$ is equiprobable, and this $$$p$$$ contributes if and only if it is a topological sort, so the probability that satisfies all conditions is the number of topological sorts divided by $$$n!$$$.

Now the problem has been transformed into a counting problem. For each coloring, count the total number of topological sorts. Now we do not enumerate coloring directly but enumerate topological sorts directly by enumerating a permutation $$$p$$$ such that $$$y_{p_1}<y_{p_2}<\cdots<y_{p_n}$$$ and count the number of colorings that satisfy the conditions. It can be found that $$$\le 1$$$ condition limits variablesin in the front position of $$$p$$$ to be less than $$$0.5$$$, and $$$\ge 1$$$ condition limits variables in the front position of $$$p$$$ to be greater than $$$0.5$$$.

Then we can use bit-mask DP. Let $$$dp_{mask}$$$ represent that we have added all vertices in mask into topological sort. We enumerate new added vertex u for transition. If all variables with $$$\le 1$$$ conditions between it are included in mask, it can be colored black; if all variables with $$$\ge 1$$$ conditions between it are included in mask, it can be colored white.

Time complexit is $$$O(2^nn)$$$.

#include <iostream>
 
const int P = 998244353;
 
long long Pow(long long a, int n) {
    long long r = 1;
    while (n) {
        if (n & 1) r = r * a % P;
        a = a * a % P, n >>= 1;
    }
    return r;
}
inline void inc(int& a, int b) {
    if((a += b) >= P) a -= P;
}
 
int n, m, G[20][2], f[1 << 20];
 
int main() {
    std::cin >> n >> m;
    while (m--) {
        int t, i, j;
        std::cin >> t >> i >> j;
        i--, j--;
        G[i][t] |= 1 << j;
        G[j][t] |= 1 << i;
    }
    f[0] = 1;
    for (int S = 0; S < 1 << n; S++)
        for (int i = 0; i < n; i++) if (~S >> i & 1) {
            if ((G[i][0] | S) == S) inc(f[S | 1 << i], f[S]);
            if ((G[i][1] | S) == S) inc(f[S | 1 << i], f[S]);
        }
    long long t = 1;
    for (int i = 1; i <= n; i++) t = t * i * 2 % P;
    std::cout << f[(1 << n) - 1] * Pow(t, P - 2) % P << '\n';
}

How to solve it if you want to cut exactly $$$m$$$ edges ?

DP+divide and conquer

Add a constraint: "you must cut off $$$m$$$ edges".

Consider enumerating the minimum cut edges from small to large.

Suppose the minimum cut edge chosen is $$$a_1$$$, and the subsequent optimal solution is $$$a_2, a_3, ..., a_m$$$.

If another minimum cut edge is selected: $$$b_1$$$, and the subsequent optimal solution is $$$b_2, b_3, ..., b_m$$$.

Assume that $$$a_i<a_{i+1}, b_i<b_{i+1}, b_1>a_1$$$.

1. It is possible to only adjust $$$b_2,b_3, ..., b_m$$$, so that $$$\forall_{1\leq i\leq m} b_i\geq a_i$$$, and the total cost after adjustment remains unchanged.

The adjustment method is as follows:

Find the smallest $$$i$$$ such that $$$b_i<a_i$$$, and find the first $$$j$$$ such that $$$b_j\geq a_j$$$ after $$$i$$$, if it does not exist, let $$$j=m+1$$$.

It can be observed that $$$(b_i,b_{i+1},b_{i+2},...,b_{j-1})$$$ can be replaced with $$$(a_i,a_{i+1},a_{i+2},...,a_{j-1})$$$, which is still a valid solution. Moreover, the solution $$$(a_i,a_{i+1},a_{i+2},...,a_{j-1})$$$ can also be replaced with $$$(b_i,b_{i+1},b_{i+2},...,b_{j-1})$$$, because $$$b_{i-1}\geq a_{i-1}$$$ and $$$b_j\geq a_j$$$.

Since $$$a$$$ and $$$b$$$ are both optimal solutions with fixed $$$a_1$$$ and $$$b_1$$$, $$$w_{b_i}+w_{b_{i+1}}+...+w_{b_{j-1}}=w_{a_i}+w_{a_{i+1}}+...+w_{a_{j-1}}$$$. Therefore, replacing $$$(b_i,b_{i+1},b_{i+2},...,b_{j-1})$$$ with $$$(a_i,a_{i+1},a_{i+2},...,a_{j-1})$$$ does not increase the total cost.

Repeat the above adjustment until there is no $$$b_i<a_i$$$.

Similarly, it can be proven that only adjusting $$$a_2,a_3,...,a_m$$$ is feasible, so that $$$\forall_{1\leq i\leq m} b_i\geq a_i$$$, and the total cost after adjustment remains unchanged.

2. If $$$\forall_{1\leq i\leq m} b_i\geq a_i$$$ is already satisfied, it is possible to only adjust $$$b_2,b_3, ..., b_m$$$, so that $$$\forall_{1\leq i<m}a_i\leq b_i\leq a_{i+1}$$$, and the total cost after adjustment remains unchanged. Assume that $$$a_1<b_1\leq a_2$$$.

The adjustment method is as follows:

Find the smallest $$$i$$$ such that $$$b_i> a_{i+1}$$$, and find the first $$$j$$$ such that $$$b_j\leq a_{j+1}$$$ after $$$i$$$ (let $$$a_{m+1}=+\infty$$$).

$$$(b_i,b_{i+1},b_{i+2},...,b_{j-1})$$$ can be replaced with $$$(a_{i+1},a_{i+2},a_{i+3},...,a_{j})$$$, which is still a valid solution. Moreover, the solution $$$(a_{i+1},a_{i+2},a_{i+3},...,a_{j})$$$ can also be replaced with $$$(b_i,b_{i+1},b_{i+2},...,b_{j-1})$$$, because $$$b_{i-1}\leq a_{i}$$$ and $$$b_j\leq a_{j+1}$$$.

Since $$$a$$$ and $$$b$$$ are both optimal solutions with fixed $$$a_1$$$ and $$$b_1$$$, $$$w_{b_i}+w_{b_{i+1}}+...+w_{b_{j-1}}=w_{a_{i+1}}+w_{a_{i+2}}+...+w_{a_j}$$$. Therefore, replacing $$$(b_i,b_{i+1},b_{i+2},...,b_{j-1})$$$ with $$$(a_{i+1},a_{i+2},a_{i+3},...,a_{j})$$$ does not increase the total cost.

Similarly, it can be proven that only adjusting $$$a_2,a_3,...,a_m$$$ is feasible, so that $$$\forall_{1\leq i<m}a_i\leq b_i\leq a_{i+1}$$$, and the total cost after adjustment remains unchanged.

3. If $$$b_1> a_2$$$, it is possible to adjust $$$b_1,b_2,...,b_m$$$, so that $$$b_1\leq a_2$$$, and the total cost does not increase.

The adjustment method is as follows:

Find the smallest $$$j$$$ such that $$$b_j\leq a_{j+1}$$$ (let $$$a_{m+1}=+\infty$$$).

It can be observed that $$$(a_{2},a_{3},a_{4},...,a_{j})$$$ can be replaced with $$$(b_1,b_{2},b_{3},...,b_{j-1})$$$, which is still a valid solution. Moreover, the solution $$$(b_1,b_{2},b_{3},...,b_{j-1})$$$ can also be replaced with $$$(a_{2},a_{3},a_{4},...,a_{j})$$$, because $$$b_j\leq a_{j+1}$$$.

Since $$$a$$$ is the optimal solution with fixed $$$a_1$$$ and $$$b_1$$$, $$$w_{b_1}+w_{b_{2}}+...+w_{b_{j-1}}\geq w_{a_{2}}+w_{a_{3}}+...+w_{a_j}$$$. Therefore, replacing $$$(b_1,b_{2},b_{3},...,b_{j-1})$$$ with $$$(a_{2},a_{3},a_{4},...,a_{j})$$$ does not increase the total cost.

Combining the above conclusions, we can obtain a solution that must cut off $$$m$$$ edges:

Let $$$a_1=1$$$, find the optimal solution $$$a_1,a_2,a_3,...,a_m$$$.

Then, it can be assumed that all $$$b_i$$$ satisfy $$$a_i\leq b_i\leq a_{i+1}$$$.

A divide-and-conquer algorithm can be used. Let $$$solve((l_1,r_1),(l_2,r_2),(l_3,r_3),...,(l_m,r_m))$$$ represent the optimal solution for all $$$l_i\leq b_i\leq r_i$$$.

If $$$l_1>r_1$$$, then we are done. Otherwise, let $$$x=\lfloor\frac{l_1+r_1}{2}\rfloor$$$, we can use DP to calculate the cost and solution for $$$b_1=x$$$ in $$$O(\sum r_i-l_i+1)$$$ time complexity. Then, recursively calculate $$$solve((l_1,b_1-1),(l_2,b_2),(l_3,b_3),...,(l_m,b_m))$$$ and $$$solve((b_1+1,r_1),(b_2,r_2),(b_3,r_3),...,(b_m,r_m))$$$.

Time complexity analysis: $$$\sum r_i-l_i+1=(\sum r_i-l_i)+m$$$. If the sum of adjacent parts is $$$\leq k$$$, it can be merged, but it is definitely not the optimal solution. Therefore, $$$m\leq 2\lceil\frac{n}{k}\rceil$$$. Assuming that the length of the first segment is $$$r_1-l_1+1=O(k)$$$, the time complexity is $$$O(n\log k+mk)=O(n\log k)$$$.

Finally, we need to calculate the solution for all possible $$$m$$$ and take the $$$\min$$$ as the final answer. After pruning the first edge, if the optimal solution requires cutting off $$$m'$$$ edges, similar to the previous proof, other solutions can be adjusted to satisfy $$$|m-m'|\leq 1$$$ and the total cost does not increase.

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 8;

int n, K, a[N], pre[N * 2];
long long dp[N * 2], ans;

vector<int> trim(vector<int> a, int L, int R) {
    return vector(a.begin() + L, a.end() - R);
}
vector<int> init() {
    static int q[N];
    q[1] = 0;
    for (int i = 1, l = 1, r = 1; i <= n; i++) {
        if (q[l] < i - K) l++;
        dp[i] = dp[q[l]] + a[i], pre[i] = q[l];
        while (l <= r && dp[i] < dp[q[r]]) r--;
        q[++r] = i;
    }
    ans = dp[n];
    vector<int> res;
    for (int i = n; i; i = pre[i]) res.push_back(i);
    res.push_back(0), reverse(res.begin(), res.end());
    return res;
}
vector<int> solve(int first, vector<int> L, vector<int> R) {
    dp[first] = a[first];
    int l = first, r = first;
    long long val; int p;
    auto checkMin = [&](int i) {
        if (dp[i] < val) val = dp[i], p = i;
    };
    for (int i = 0; i < L.size(); i++) {
        val = 1e18, p = 0;
        for (int j = R[i]; j >= L[i]; j--) {
            for (; r >= max(l, j - K); r--) checkMin(r + i);
            dp[j + i + 1] = val + a[j];
            pre[j + i + 1] = p;
        }
        l = L[i], r = R[i];
    }
    val = 1e18, p = 0;
    for (int i = max(L.back(), n - K + first); i <= R.back(); i++)
        checkMin(i + L.size());
    ans = min(ans, val);
    vector<int> res;
    for (int i = L.size(); i; i--) res.push_back(p - i), p = pre[p];
    reverse(res.begin(), res.end());
    return res;
}
void divide(int l, int r, vector<int> L, vector<int> R) {
    if (l > r) return;
    int mid = (l + r) >> 1;
    auto M = solve(mid, L, R);
    divide(l, mid - 1, L, M), divide(mid + 1, r, M, R);
}
void divide(vector<int> p) {
    p.push_back(n), divide(1, p[0], trim(p, 0, 1), trim(p, 1, 0));
}
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> K;
        for (int i = 1; i <= n; i++) cin >> a[i];
        a[0] = a[n];
        auto p = init();
        divide(trim(p, 1, 1));
        divide(solve(0, trim(p, 0, 1), trim(p, 1, 0)));
        if ((p.size() - 2) * K >= n)
            divide(solve(0, trim(p, 1, 2), trim(p, 2, 1)));
        cout << ans << '\n';
    }
}