The optimal sequence of operations is very simple.

The optimal sequence of operations is adding $$$k-1$$$ 1-s into the set each time, at the same time decreasing $$$n$$$ by $$$k-1$$$. This implies that the answer is $$$\lceil \frac{n-1}{k-1}\rceil$$$.

t = (int)(input())
for _ in range(t):
    n, k = map(int, input().split())
    print((n - 1 + k - 2) // (k - 1))

"Most sequences" can be transformed into $$$[1]$$$. Conditions for a sequence to be un-transformable is stringent.

Find several simple substrings that make the string transformable.

We list some simple conditions for a string to be transformable:

• If 111 exists somewhere (as a substring) in the string, the string is always transformable.
• If 11 appears at least twice in the string, the string is always transformable.
• If the string both begins and ends with 1, it is always transformable.
• If the string begins or ends with 1 and 11 exists in the string, it is always transformable.

These can be found by simulating the operation for short strings on paper.

Contrarily, if a string does not meet any of the four items, it is always not transformable. This can be proved using induction (as an exercise).

Observe that the number of 1 never increases in an operation. We can change a continuous segment of zeros into one zero. After that, it suffices to check that the number of occurences of 1 is larger than the number of occurences of 0.

t = (int)(input())
for _ in range(t):
    n = (int)(input())
    a = input()
    ok = 0
    if a.count("111") >= 1:
        ok = 1
    if a.count("11") >= 2:
        ok = 1
    if a.count("11") >= 1 and (a[0] == "1" or a[-1] == "1"):
        ok = 1
    if a[0] == "1" and a[-1] == "1":
        ok = 1
    if ok:
        print("Yes")
    else:
        print("No")

The answer is a simple construction.

The maximum length for $$$2^k-1\ (k>1)$$$ is $$$k+1$$$.

It's obvious that the answer only depends on the popcount of $$$n$$$. Below, we assume $$$n=2^k-1$$$. If $$$k=1$$$, it is shown in the samples that the length is $$$1$$$.

Otherwise, the maximum sequence length for $$$2^k-1$$$ is $$$k+1$$$. This can be achived by $$$a_i=n-2^{i-1}\ (1\le i\le k),a_{k+1}=n$$$.

t = (int)(input())
for _ in range(t):
    n = (int)(input())
    a = []
    for i in range(62, -1, -1):
        x = 1 << i
        if ((x & n) == x) and (x != n):
            a.append(n - x)
    a.append(n)
    print(len(a))
    for i in a:
        print(i, end=" ")
    print("")

Formulate the problem.

Some variables can't be large.

Suppose monster $$$i$$$ is killed in round $$$b_i$$$. Then, the total health decrement is the sum of $$$a_i\times b_i$$$. The "independent set" constraint means that for adjacent vertices, their $$$b$$$-s must be different.

Observation: $$$b_i$$$ does not exceed $$$\lfloor \log_2 n\rfloor+1$$$. In this problem, $$$b_i\le 19$$$ always holds for at least one optimal $$$a_i$$$.

By dp, we can find the answer in $$$O(n\log n)$$$ or $$$O(n\log^2 n)$$$, depending on whether you use prefix/suffix maximums to optimize the taking max part.

Bonus: Find a counterexample for $$$b_i\le 18$$$ when $$$n=300000$$$. (Pretest 2 is one case)

Note that $$$b_x\le \deg x$$$. By carefully handing the dp transitions, we can achieve a $$$O(\sum \deg_x)=O(n)$$$ solution.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll a[300005], f[300005][24], smn[30];
vector<int> g[300005];
void dfs(int x, int fa) {
	for (int i = 1; i <= 22; i++) f[x][i] = i * a[x];
	for (int y : g[x]) {
		if (y == fa) continue;
		dfs(y, x);
		ll tt = 8e18;
		smn[23] = 8e18;
		for (int i = 22; i >= 1; i--) {
			smn[i] = min(smn[i + 1], f[y][i]);
		}
		for (int i = 1; i <= 22; i++) {
			f[x][i] += min(tt, smn[i + 1]);
			tt = min(tt, f[y][i]);
		}
	}
}
void Solve() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1, x, y; i < n; i++) {
		cin >> x >> y;
		g[x].push_back(y), g[y].push_back(x);
	}
	dfs(1, 0);
	cout << *min_element(f[1] + 1, f[1] + 23) << '\n';
	for (int i = 1; i <= n; i++) {
		g[i].clear();
		memset(f[i], 0, sizeof(f[i]));
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int t;
	cin >> t;
	while (t--) Solve();
}

Formulate the problem on a cartesian tree.

Find a clever bruteforce. Calculate the time complexity carefully.

Build the cartesian tree of $$$a$$$. Let $$$lc_x,rc_x$$$ respectively be $$$x$$$'s left and right children.

Consider a vertex $$$x$$$. If we delete it, what would happen to the tree? Vertices that are on the outside of $$$x$$$'s subtree will not be affected. Vertices inside the subtree of $$$x$$$ will "merge". Actually, we can see that, only the right chain of $$$x$$$'s left child ($$$lc_x\to rc_{lc_x}\to rc_{rc_{lc_x}}\to \dots$$$) and the left chain of $$$x$$$'s right child will merge in a way like what we do in mergesort.

Now, if we merge the chains by bruteforce (use sorting or std::merge), the time complexity is $$$O(n)$$$! It's easy to see that each vertex will only be considered $$$O(1)$$$ times.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pr;
int n, a[500005], st[500005], c[500005][2], top, sz[500005];
ll ans[500005], atv[500005], sum;
void dfs1(int x) {
	sz[x] = 1;
	for (int i = 0; i < 2; i++)
		if (c[x][i]) dfs1(c[x][i]), sz[x] += sz[c[x][i]];
	sum += (atv[x] = (sz[c[x][0]] + 1ll) * (sz[c[x][1]] + 1ll) * a[x]);
}
void dfs2(int x, ll dlt) {
	ll val = sum - dlt - atv[x];
	vector<int> lr, rl;
	vector<pr> ve;
	int y = c[x][0];
	while (y) lr.push_back(y), val -= atv[y], y = c[y][1];
	y = c[x][1];
	while (y) rl.push_back(y), val -= atv[y], y = c[y][0];
	{
		int i = 0, j = 0;
		while (i < lr.size() || j < rl.size()) {
			if (j >= rl.size() || (i < lr.size() && j < rl.size() && a[lr[i]] < a[rl[j]])) {
				ve.push_back(pr(lr[i], 0));
				i++;
			} else {
				ve.push_back(pr(rl[j], 1));
				j++;
			}
		}
	}
	// cout << x << ' ' << val << '\n';
	int cursz = 0;
	for (int i = (int)ve.size() - 1; i >= 0; i--) {
		int p = ve[i].first, q = ve[i].second;
		// cout << "I:" << i << ' ' << cursz << '\n';
		val += (cursz + 1ll) * (sz[c[p][q]] + 1ll) * a[p];
		cursz += sz[c[p][q]] + 1;
	}
	ans[x] = val;
	for (int i = 0; i < 2; i++)
		if (c[x][i]) dfs2(c[x][i], dlt + 1ll * (sz[c[x][i ^ 1]] + 1) * a[x]);
}
void Solve() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	st[top = 0] = 0;
	for (int i = 1; i <= n; i++) {
		while (top && a[st[top]] > a[i]) top--;
		c[i][0] = c[st[top]][1], c[st[top]][1] = i;
		st[++top] = i;
	}
	int rt = st[1];
	sum = 0, dfs1(rt), dfs2(rt, 0);
	for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
	cout << '\n';
	for (int i = 0; i <= n; i++) c[i][0] = c[i][1] = 0;
}
int main() {
	int t;
	scanf("%d", &t);
	while (t--) Solve();
}

We can use dp to calculate the number of permutations of $$$1\sim n$$$ with $$$i$$$ prefix maximums and $$$j$$$ ascents, $$$f(n,i,j)$$$: consider where 1 is inserted, we will have a $$$O(n^3)$$$ dp that finds $$$f(n,i,j)$$$ for all suitable $$$(n,i,j)$$$-s.

For suffix maximums, (the number of permutations of $$$1\sim n$$$ with $$$i$$$ prefix maximums and $$$j$$$ ascents, $$$g(n,i,j)$$$, we can just reverse some dimension of $$$f$$$).

To calculate the answer, consider the position of $$$n$$$. Suppose it's $$$p$$$. The the answer is

Let $$$u(x,y)=\sum_{i}f(x,i,y)a_{i+1}$$$, $$$v(x,y)=\sum_{z}g(x,i,y)b_{i+1}$$$ (both of these are calculated in $$$O(n^3)$$$), then the answer is

By seeing $$$u$$$ and $$$v$$$ as 2D polynomials, this can be calculated with 2D FFT in $$$O(n^2\log n)$$$.

#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int Power(int x, int y) {
	int r = 1;
	while (y) {
		if (y & 1) r = 1ll * r * x % mod;
		x = 1ll * x * x % mod, y >>= 1;
	}
	return r;
}
namespace Conv_998244353 {

const int g = 3, invg = ((mod + 1) % 3 == 0 ? (mod + 1) / 3 : (2 * mod + 1) / 3);
int wk[1050005], ta[1050005], tb[1050005];
void DFT(int *a, int n) {
	for (int i = n >> 1; i; i >>= 1) {
		int w = Power(g, (mod - 1) / (i << 1));
		wk[0] = 1;
		for (int j = 1; j < i; j++) wk[j] = 1ll * wk[j - 1] * w % mod;
		for (int j = 0; j < n; j += (i << 1)) {
			for (int k = 0; k < i; k++) {
				int x = a[j + k], y = a[i + j + k], z = x;
				x += y, (x >= mod && (x -= mod)), a[j + k] = x;
				z -= y, (z < 0 && (z += mod)), a[i + j + k] = 1ll * z * wk[k] % mod;
			}
		}
	}
}
void IDFT(int *a, int n) {
	for (int i = 1; i < n; i <<= 1) {
		int w = Power(invg, (mod - 1) / (i << 1));
		wk[0] = 1;
		for (int j = 1; j < i; j++) wk[j] = 1ll * wk[j - 1] * w % mod;
		for (int j = 0; j < n; j += (i << 1)) {
			for (int k = 0; k < i; k++) {
				int x = a[j + k], y = 1ll * a[i + j + k] * wk[k] % mod, z = x;
				x += y, (x >= mod && (x -= mod)), a[j + k] = x;
				z -= y, (z < 0 && (z += mod)), a[i + j + k] = z;
			}
		}
	}
	for (int i = 0, inv = Power(n, mod - 2); i < n; i++) a[i] = 1ll * a[i] * inv % mod;
}
vector<int> conv(vector<int> A, vector<int> B) {
	for (auto &i : A) i %= mod;
	for (auto &i : B) i %= mod;
	int sa = A.size(), sb = B.size();
	vector<int> ret(sa + sb - 1);
	int len = 1;
	while (len < ret.size()) len <<= 1;
	for (int i = 0; i < len; i++) ta[i] = tb[i] = 0;
	for (int i = 0; i < sa; i++) ta[i] = A[i];
	for (int i = 0; i < sb; i++) tb[i] = B[i];
	DFT(ta, len), DFT(tb, len);
	for (int i = 0; i < len; i++) ta[i] = 1ll * ta[i] * tb[i] % mod;
	IDFT(ta, len);
	for (int i = 0; i < ret.size(); i++) ret[i] = ta[i];
	return ret;
}

} // namespace Conv_998244353
vector<int> conv(vector<int> A, vector<int> B) {
	return Conv_998244353::conv(A, B);
}
int n, a[705], b[705], c[705], f[705][705], u[705][705], v[705][705];
int ny[705], jc[705];
void upd(int &x, int y) { x += y, (x >= mod && (x -= mod)); }
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];
	for (int i = 0; i < n; i++) cin >> c[i];
	f[0][0] = jc[0] = ny[0] = 1;
	for (int i = 1; i <= n; i++) {
		jc[i] = 1ll * jc[i - 1] * i % mod, ny[i] = Power(jc[i], mod - 2);
	}
	vector<int> A(500000), B(500000);
	for (int i = 0; i <= n; i++) {
		for (int j = i; j >= 0; j--) {
			for (int k = i; k >= 0; k--) {
				if (!f[j][k]) continue;
				// cout << i << ' ' << j << ' ' << k << ' ' << f[j][k] << '\n';
				upd(u[i][k], 1ll * f[j][k] * a[j + 1] % mod);
				upd(v[i][k], 1ll * f[j][k] * b[j + 1] % mod);
				upd(f[j + 1][k + (i != 0)], f[j][k]);
				upd(f[j][k + 1], 1ll * f[j][k] * (i - (i != 0) - k) % mod);
				f[j][k] = 1ll * f[j][k] * (k + (i != 0)) % mod;
			}
		}
		if (i > 0) reverse(v[i], v[i] + i);
		for (int j = 0; j <= i; j++) {
			if (i) A[703 * i + j] = 1ll * u[i][j] * ny[i] % mod;
			B[703 * i + j] = 1ll * v[i][j] * ny[i] % mod;
		}
	}
	A = conv(A, B);
	for (int i = 1; i <= n; i++) {
		int ans = 0;
		for (int y = 0; y <= i - 1; y++) {
			ans = (ans + 1ll * u[0][0] * v[i - 1][y] % mod * c[y]) % mod;
		}
		for (int j = 0; j < i; j++) {
			ans = (ans + 1ll * A[703 * (i - 1) + j] * jc[i - 1] % mod * c[j + 1]) % mod;
		}
		cout << ans << ' ';
	}
}

#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353, N = 705;
int n, a[N + 5], b[N + 5], c[N + 5], f[N + 5][N + 5], u[N + 5][N + 5], v[N + 5][N + 5],
    C[N + 5][N + 5];
int g[N + 5], h[N + 5], t[N + 5][N + 5], p[N + 5][N + 5], ny[N + 5], o[N + 5];
void upd(int &x, int y) { x += y, (x >= mod && (x -= mod)); }
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];
	for (int i = 0; i < n; i++) cin >> c[i];
	f[0][0] = ny[1] = ny[0] = 1;
	for (int i = 0; i <= n; i++) {
		C[i][0] = 1;
		for (int j = 1; j <= i; j++) C[i][j] = (C[i &mdash; 1][j] + C[i &mdash; 1][j &mdash; 1]) % mod;
	}
	for (int i = 2; i <= n; i++) ny[i] = 1ll * ny[mod % i] * (mod &mdash; mod / i) % mod;
	for (int i = 2; i <= n; i++) ny[i] = 1ll * ny[i &mdash; 1] * ny[i] % mod;
	for (int i = 0; i < n; i++) {
		for (int j = i; j >= 0; j--) {
			for (int k = i; k >= 0; k--) {
				if (!f[j][k]) continue;
				// cout << i << ' ' << j << ' ' << k << ' ' << f[j][k] << '\n';
				upd(u[i][k], 1ll * f[j][k] * a[j + 1] % mod);
				upd(v[i][k], 1ll * f[j][k] * b[j + 1] % mod);
				upd(f[j + 1][k + (i != 0)], f[j][k]);
				upd(f[j][k + 1], 1ll * f[j][k] * (i &mdash; (i != 0) &mdash; k) % mod);
				f[j][k] = 1ll * f[j][k] * (k + (i != 0)) % mod;
			}
		}
		if (i > 0) reverse(v[i], v[i] + i);
	}
	for (int x = 1; x <= n; x++) {
		for (int i = 0; i < n; i++) {
			g[i] = h[i] = 0;
			for (int j = i; j >= 0; j--) {
				g[i] = (1ll * g[i] * x + u[i][j]) % mod;
				h[i] = (1ll * h[i] * x + v[i][j]) % mod;
			}
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= i; j++) {
				upd(t[i][x], 1ll * g[j &mdash; 1] * h[i &mdash; j] % mod * C[i &mdash; 1][j &mdash; 1] % mod *
				                 (j > 1 ? x : 1) % mod);
			}
		}
	}
	p[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < i; j++) p[i][j] = p[0][j], o[j] = 0;
		for (int j = 0; j <= i; j++) {
			if (j != i) {
				for (int k = i &mdash; 1; k >= 0; k--) {
					upd(p[j][k + 1], p[j][k]);
					p[j][k] = 1ll * p[j][k] * (mod &mdash; i) % mod;
				}
			}
			if (!j) continue;
			int s = 1ll * t[i][j] * ny[j &mdash; 1] % mod * ny[i &mdash; j] % mod;
			if ((i &mdash; j) & 1) s = mod &mdash; s;
			for (int k = 0; k < i; k++) {
				upd(o[k], 1ll * s * p[j][k] % mod);
			}
		}
		int ans = 0;
		for (int k = 0; k < i; k++) {
			ans = (ans + 1ll * o[k] * c[k]) % mod;
		}
		cout << ans << ' ';
	}
}

How many operations will we perform?

Suppose we can only perform exactly one operation. In this case the answer is $$$S=\max_{1\le i\le n}(a_i\mathrm{\ or\ }z)$$$. In fact, we can prove that this is the answer.

Define $$$a_i'$$$ as the value of $$$a_i$$$ after some operations.

It suffices to prove the answer will never exceed $$$S$$$. Note that $$$z$$$ will always become a submask of itself after any number of operations, so $$$a_i$$$ will always be a submask of $$$(a_i\mathrm{\ or\ }z)$$$ after any number of operations. This leads to the conclusion that $$$a_i'\le (a_i\mathrm{\ or\ }z)$$$ for all $$$i$$$. Thus $$$\max_{1\le i\le n} a_i'\le \max_{1\le i\le n}(a_i\mathrm{\ or\ }z)=S$$$.

Time complexity is $$$O(n)$$$.

How many operations will we perform?

How to check if the array can be destroyed in $$$0$$$ or $$$1$$$ operations?

The answer is at most $$$2$$$, because doing the operation on $$$[1,n]$$$ at most twice will always work. (If the array contains at least one zero, we need $$$2$$$ operations. Otherwise we need $$$1$$$ operation.)

If the array consists of zeroes, the answer is $$$0$$$.

If all non-zero elements form a contiguous segment in the array, the answer is $1$​. To check this, you can find the leftmost and rightmost occurrence of non-zero elements and check if elements in the middle of them are also non-zero.

Otherwise the answer is $$$2$$$.

Time complexity is $$$O(n)$$$.

The operation is reversible. (The two operations are reverses of each other.)

Try to find a middle state, such that we can turn both $$$a$$$ and $$$b$$$ into it.

Call the first operation "expand" and the second operation "shrink".

Keep doing expand on both arrays until we can't do expand anymore, call the resulting arrays $$$a'$$$ and $$$b'$$$. It suffices to check if $$$a'=b'$$$. To implement this, you need to compress contiguous equal numbers.

Proof of why this is necessary and sufficient:

• Sufficiency is obvious, since the operations are reversible. We can do something like $$$a\to a'=b'\to b$$$.

• Necessity: Let $$$f(a)=a'$$$. It suffices to prove that an operation on $$$a$$$ does not affect $$$f(a)$$$. An expand operation obviously doesn't affect $$$f(a)$$$. A shrink operation shrinks $$$a[i,i+m-1]$$$ into one element. When computing $$$f(a')$$$, we will always expand $$$a'_i$$$ at some time, so the result is the same as $f(a)$​.

Time complexity is $$$O((n+k)\log_m V)$$$, where $$$V=\max a_i$$$.

The solution is $$$O(n)$$$. We don't need any data structures.

Instead of trying to construct the shortest path from $$$1$$$ to $$$n$$$, find a "transfer vertex" that we must pass through.

Suppose the maximum element is $$$a_k$$$. Solve recursively for $$$dis(1,k)$$$ and $$$dis(k,n)$$$.

Denote $$$dis(x,y)$$$ as the length of the shortest path between $$$x$$$ and $$$y$$$.

Consider a position $$$i$$$ that $$$a_i=n$$$. Assume $$$i\ne 1$$$ and $$$i\ne n$$$. For a segment that passes $$$i$$$, its maximum element is always $$$a_i$$$. Thus, for $$$x<i<y$$$, $$$x$$$ and $$$y$$$ will never be directly connected by an edge. This means that when going from $$$1$$$ to $$$n$$$, we have to pass $$$i$$$. Let us solve recursively for $$$dis(1,i)$$$ and $$$dis(i,n)$$$. For example, we solve for $$$dis(1,i)$$$.

We already know that $$$a_i=n$$$, so $$$i$$$ is the maximum element in $$$[1,i]$$$. Consider the minimum element in $$$[1,i]$$$, suppose it is $$$a_j\ (j<i)$$$. From similar arguments, we can solve recursively for $$$dis(1,j)$$$ and $$$dis(j,i)$$$. However, note that $$$dis(j,i)$$$ equals to $$$1$$$: since $$$j$$$ and $$$i$$$ are respectively minimum and maximum in $$$[1,i]$$$, they have to be minimum and maximum in $$$[j,i]$$$ as well. So $$$i,j$$$ must be directly connected. Thus, we only need to solve recursively for $$$dis(1,j)$$$.

The process with $$$dis(i,n)$$$ is similar. Note that we will only call $$$dis(l,r)$$$ for $$$l=1$$$ or $$$r=n$$$ (if not, the return value is always 1), so it suffices to pre-compute prefix and suffix minimums and maximums.

The time complexity is $$$O(n)$$$.

Look at the last sample test case. Think of a simple greedy.

Use data structures to simulate the process. How?

We can prove that keep going to the vertex with the largest index is a correct strategy. The proof is left as an exercise :) Hint: try to prove that the path we will visit is the same as the path we visited in solution 1.

Suppose we are at $$$i$$$. We want to find the largest $$$j>i$$$ such that $$$i$$$ and $$$j$$$ are directly connected. WLOG, assume $$$a_{i+1}<a_i$$$. Then, it cannot be the case that $$$a_j>a_i$$$, since none of $$$a_i,a_j$$$ will be $$$mn(i,j)$$$. Thus $$$a_j<a_i$$$. It follows that all $$$i<k<j$$$ satisfies $$$a_k<a_i$$$, otherwise none of $$$a_i,a_j$$$ will be $$$mx(i,j)$$$.

Let $$$r_i$$$ be the largest $$$p$$$, such that for all $$$t\in [i+1,p]$$$, $$$a_t<a_i$$$. From the arguments above we know $$$j\in [i+1,r_i]$$$. $$$r_i$$$ can be pre-computed with a stack, or binary search + some data structures.

Let $$$j_0$$$ be the position of the minimum element in $$$[i+1,r_i]$$$. Obviously $$$j_0$$$ is directly connected with $$$i$$$. For any $$$j_0<k\le r_i$$$, $$$mn(i,k)$$$ will be $$$a_{j_0}$$$, showing that all such $$$k$$$ is not directly connected with $$$i$$$. Thus, $$$j_0$$$ is the desired $$$j$$$.

If we use data structures for range minimum, we get a $$$O(n\log n)$$$ solution, which can easily pass (not sure whether $$$O(n\log^2 n)$$$ ones will pass though, the large constraints were intended to cut those).

However, by building the cartesian tree of the array and doing proper pre-computations, we can optimize this solution to $$$O(n)$$$.

Try to find out the number of operations we do on a specific cell $$$(i,j)$$$, call it $$$f(i,j)$$$.

Write the recurrence formula for $$$f(i,j)$$$. What is $$$f(i,j)$$$?

The answer is the sum of $$$f(i,j)$$$ over all white cells $$$(i,j)$$$. Use some combinatorics formula to speed it up.

Let us find out the number of operations we do on a specific cell $$$(i,j)$$$, call it $$$f(i,j)$$$.

Every operation done on $$$(i-1,j)$$$ will lead to one doll on $$$(i,j)$$$, thus consuming one operation on $$$(i,j)$$$. Similar observation holds for $$$(i,j-1)$$$.

Thus, $$$f(i,j)=f(i,j-1)+f(i-1,j)$$$ (given that $$$(i,j),(i-1,j),(i,j-1)$$$ are all white cells). Note that $$$a$$$ is non-increasing: this means that if $$$(i,j)$$$ is white, $$$(i-1,j),(i,j-1)$$$ will both be white. So we can conclude that $$$f(i,j)=f(i,j-1)+f(i-1,j)$$$ always holds as long as $$$(i,j)$$$ is white.

Another way to see the formula is $$$f(i,j)$$$ is the number of ways to go from $$$(0,0)$$$ to $$$(i,j)$$$, only going down or right by 1 step. This implies that $$$f(i,j)=\binom{i+j}j$$$.

From this, we know that the answer is $$$\sum_{i=0}^n\sum_{j=0}^{a_i-1} \binom{i+j}{i}$$$. With the equation $$$\sum_{i=0}^k\binom{n+i}n=\binom{n+k+1}{n+1}$$$, we know that the answer is $$$\sum_{i=0}^n\binom{i+a_i}{i+1}$$$.

The time complexity is $$$O(n+V)$$$, where $$$V=\max a_i$$$.

The solution does not contain painful casework and deadly implemention.

Suppose we aleady know edge $$$(i,j)$$$ exists in the tree. What can we know from it?

Read the hints first to understand the solution better.

Construct a graph with $$$\binom n2$$$ vertices $$$(1,2),(1,3),\dots,(n-1,n)$$$.

If $$$dis(a,b)=dis(b,c)$$$, link an undirected edge between $$$(a,b)$$$ and $$$(b,c)$$$.

Observe that all edges in the tree form a connected component of size exactly $$$n-1$$$ in the graph!

Find all components of size $$$n-1$$$ and try if all vertices in it form a tree that satisfy the input. There are at most $$$\dfrac n2$$$ such components, so complexity is $$$O(n^4)$$$. Proper pre-computation and the usage of bitsets can reduce the complexity to $$$O(n^4/w)$$$.

What kind of problem is this problem?

Consider the dual.

Consider the case when $$$n=2$$$. Draw the linear programming on a xOy-coordinate. Try to observe what the answer might be.

First we solve the problem with only 1 query on the whole array $$$A$$$.

This is a linear programming problem:

Consider its dual:

Suppose $$$X\le Y$$$. Now we will prove that there exists an optimal solution to the dual problem, in which $$$x_i$$$ can only take three values: $$$1/Y,1/(X+Y),0$$$.

The proof is as follows: It is well-known that an optimal solution to a linear programming problem must lie on a vertex of the "multi-dimensional convex polygon" which the restrictions surround. Thus we are only interested in $$$x_i$$$ that satisfy several "=" restrictions (and the restrictions should really intersect at one point, meaning that those "=" should uniquely determine $$$x$$$). Consider any "sufficient" (that means they uniquely determine $$${x}$$$) subset of them. If one restriction is related to $$$x_p,x_q$$$, we link an undirected edge between $$$p$$$ and $$$q$$$. If one restriction is only related to $$$x_p$$$ (i.e. $$$x_p=0$$$), we link a self-loop on $$$p$$$. "Being sufficient" means that all connected components in the graph has exactly one cycle. However, for an edge $$$(u,v)$$$, we know that either $$$u=v+1$$$ or $$$u=v$$$. This means that all cycles can only be $$$(i\to i+1\to i)$$$ or $$$i\to i$$$. If a cycle is $$$(i\to i+1\to i)$$$, all $$$x_i$$$ in the component are $$$1/(X+Y)$$$; If a cycle is $$$i\to i$$$, all $$$x_i$$$ in the component are $$$1/Y$$$ or $$$0$$$ (not $$$1/X$$$, because it exceeds the constraints).

Thus we can use dp to solve the dual problem. Let $$$dp(i,0/1/2)$$$ be the maximum $$$\sum_{j\le i}A_jx_j$$$ when $$$x_i$$$ is the $$$0/1/2$$$-th candidate above. Transitions are straight-forward.

For multiple queries, the transitions can be written into multiplying matrices, and we can use segment tree to maintain updates.

About precision issues: actually we can avoid using floating point numbers completely. Note that all numbers in this problem are fractions with denominator $$$Y(X+Y)$$$. Also note that the answer does not exceed $$$(\sum a_i)/Y$$$. This means that the numerator does not exceed $$$(\sum a_i)\times (X+Y)<10^{18}$$$, so we can use long long-s to only store numerators. If you use double in C++, the relative error of one operation is less than $$$10^{-15}$$$. $$$10^{-15}\times n<10^{-9}$$$, which means that using doubles is also enough.

Complexity: $$$O(n+q\log n)$$$.

Find a way to calculate the maximum product that can be turned into counting.

Use monotonicity to reduce the complexity.

First, we describe a strategy to find the answer for a single subset. If the whole subset is negative, the answer is the product of the $$$K$$$ maximum numbers in it. Otherwise, take $$$K$$$ numbers with the maximum absolute value. If there is an even number of negative numbers in those numbers, we're done. Otherwise, find the smallest positive element and change it to the absolute-value-maximum negative element unchosen, or find the largest negative element and change it to the maximum positive element unchosen. We either do the first change or do the second change.

This gives a direct dp solution. Take all $$$a_i$$$ and sort them into two arrays consisting of positive and negative ones (0 goes to arbitary one), $$$pos$$$ and $$$neg$$$, sorted by absolute values. By calculating $$$fpos(i,k)$$$: the sum of the product of the largest $$$K$$$ numbers of all subsets of $$$pos[1\dots i]$$$ that contain $$$pos_i$$$, and $$$fneg(i,k)$$$ similarly, and $$$gneg(i,k)$$$, the sum of the product of the absolute value smallest $$$K$$$ numbers of all subsets of $$$neg[i\dots |neg|]$$$ that contain $$$neg_i$$$, and enumerating the following, we can solve the original problem in $$$O(n^5)$$$:

• the number of positive elements in the $$$K$$$ numbers with the maximum absolute value in our calculating subset, $$$p$$$.
• the smallest positive element in the $$$K$$$ numbers with the maximum absolute value, $$$pos_i$$$.
• the greatest negative element in the $$$K$$$ numbers with the maximum absolute value, $$$neg_j$$$.
• (if $$$p$$$ is odd) the greatest positive element not in the $$$K$$$ numbers with the maximum absolute value, $$$pos_k$$$.
• (if $$$p$$$ is odd) the smallest negative element not in the $$$K$$$ numbers with the maximum absolute value, $$$pos_l$$$.

The contribution to the answer can be represented as the sum of product of $$$fpos,fneg$$$, and powers of two. I left the details as an exercise.

However, notice that the "enumerating $$$k,l$$$" part has nothing to do with $$$p$$$, so we can pre-calculate the contribution of $$$k,l$$$ for every pair $$$(i,j)$$$, giving an $$$O(n^4)$$$ algorithm.

What's more, for fixed $$$i,j,k$$$, the $$$l$$$-s that we do the first change is a prefix/suffix of all $$$l$$$, and $$$l$$$-s that we do the second change is a prefix/suffix of all $$$l$$$. So with two pointers and prefix sums, we can pre-calculate the contribution of every $$$(i,j)$$$ in $$$O(n^3)$$$, which is fast enough.

You might be afraid that $$$600^3$$$ is too slow for 1.5 seconds. However, the two $$$O(n^3)$$$ parts of the algorithm actually run in $$$O(n\times cntpos\times cntneg)$$$ ($$$cntpos,cntneg$$$ are the number of positive/negative integers in the array), leading to an at most $$$1/4$$$ constant factor. Thus, the algorithm actually runs very fast (less than 0.25 seconds). However for similar constant factor reasons, the $$$O(n^4)$$$ solution only takes about 6.5 seconds on Codeforces, so we had to set a seemingly-tight limit.

The answer is 'yes' if and only if there are exactly $$$n$$$ odd numbers.

#include<bits/stdc++.h>
using namespace std;
int main() {
	int t;
	cin>>t;
	while(t--){
		int n,cnt[2]={0};
		cin>>n;
		for(int i=1,x;i<=n*2;i++)cin>>x,cnt[x%2]++;
		if(cnt[0]==n)puts("Yes");
		else puts("No");
	}
	return 0;
}

What kind of element in the set is important?

If $$$x$$$ is in the set, but $$$x-b$$$ is not, $$$x$$$ is important. Why?

How can we find all important elements?

First check specially if $$$b=1$$$.

Let's consider when $$$n$$$ is in $$$S$$$. The answer is when the smallest number $$$m$$$ in $$$S$$$ that $$$n\ \mathrm{mod}\ b=m\ \mathrm{mod}\ b$$$ is less than $$$n$$$. It's easy to see that a new case of $$$x\ \mathrm{mod}\ b$$$ can only appear when you use $$$\times a$$$ to generate a new element. So the smallest number $$$m$$$ in S that $$$m\ \mathrm{mod}\ b=k$$$ must be a power of $$$a$$$.

Find all powers of a that is smaller than $$$n$$$. If there is one $$$m=a^k$$$ that $$$n\ \mathrm{mod}\ b=m\ \mathrm{mod}\ b$$$, the answer is yes. Otherwise it's no. Time complexity is $$$O(\log n)$$$.

t=(int)(input())
for i in range(t):
    w=input().split()
    n=(int)(w[0])
    a=(int)(w[1])
    b=(int)(w[2])
    if a==1 :
    	if (n-1)%b==0 :
    		print("Yes")
    	else :
    		print("No")
    	
    else :
    	t=1
    	flag=0
    	while t<=n :
    		if t%b==n%b:
    			flag=1
    			break
    		t=t*a
    	if flag==1:
    		print("Yes")
    	else :
    		print("No")

$$$f(n)$$$ is small.

For a given $$$x$$$, when is $$$f(n)$$$ equal to $$$x$$$?

Enumerate the value of $$$f(i)$$$. Since $$$f(n)=i$$$ means $$$lcm(1,2,...,i-1)\le n$$$, $$$f(n)$$$ will not be too big (less than $$$100$$$). The number of $$$k$$$s such that $$$f(k)=i$$$ is $$$\lfloor n/lcm(1,2,...,i-1)\rfloor -\lfloor n/lcm(1,2,...,i)\rfloor $$$. ($$$k$$$ should be divisible by $$$1\sim i-1$$$ but not $$$i$$$) So the answer is $$$\sum_{i>1} i(\lfloor n/lcm(1,2,...,i-1)\rfloor -\lfloor n/lcm(1,2,...,i)\rfloor )$$$.

We can also write the answer in another form, which is equivalent to the previous form:

#include<bits/stdc++.h>
#define int long long
#define re register
using namespace std;
int t,n;
const int M=1e9+7;
inline int gcd(re int x,re int y){
	return y?gcd(y,x%y):x;
}
inline int LCM(re int x,re int y){
	return x/gcd(x,y)*y;
}
signed main(){
	scanf("%lld",&t);
	while(t--){
		scanf("%lld",&n);
		re int G=1,ans=0;
		for(re int i=1;G<=n;++i){
			G=LCM(G,i);
			if(G>n)break;
			ans+=n/G;
		}
		printf("%lld\n",(ans+n)%M);
	}
}

For each $$$x$$$, count how many $$$B$$$s make the final set contain $$$x$$$.

For each $$$x$$$, count how many $$$B$$$s make the final set contain $$$x$$$.

Let's say we have picked the $$$x$$$ in the $$$I$$$-th operation, call it $$$X$$$. Then, the subsequence we choose must satisfy the following conditions:

• It must contain the $$$i$$$-th operation (otherwise $$$X$$$ won't be added).
• Let $$$s$$$ denote the number of numbers less than $$$X$$$ in the current $$$T$$$. Whenever we meet a - element in $$$S$$$ after the $$$i$$$-th operation, $$$s$$$ should be greater than $$$0$$$.

With those conditions, we can come up with the following dp.

Let $$$f(i,j)$$$ denote the number of subsequences of $$$a[1...i]$$$, that if we maintain $$$T$$$ with the subsequence, $$$s$$$ will become $$$j$$$.

Then we have the following transitions:

• $$$f(i-1,j)\to f(i,j)$$$ (when we don't include the $$$i$$$-th element is $$$S$$$, here $$$i\ne I$$$)
• $$$f(i-1,j)\to f(i,\max(j-1,0))$$$ (here, $$$i<I$$$, and the $$$i$$$-th element of $$$A$$$ is -, so the number of numbers in $$$T$$$ less than $$$x$$$ decreases by one. If there is no such number, $$$s$$$ remains $$$0$$$)
• $$$f(i-1,j)\to f(i,j-1)$$$ (here, $$$i>I$$$, and and the $$$i$$$-th element of $$$A$$$ is -, so the number of numbers in $$$T$$$ less than $$$x$$$ decreases by one.)
• $$$f(i-1,j)\to f(i,j)$$$ (here, the $$$i$$$-th element of $$$A$$$ is + and its $$$x$$$ is greater than $$$X$$$)
• $$$f(i-1,j)\to f(i,j+1)$$$ (here, the $$$i$$$-th element of $$$A$$$ is + and its $$$x$$$ is less than $$$x$$$ or [equal to $$$x$$$ but $i>I$] ) [this is to deal with same elements]

Then we add $$$ans$$$ by $$$X\times \sum_{i\ge 0} f(n,i)$$$.

The time complexity is $$$O(n^3)$$$.

mod=998244353
n=(int)(input())
a=[0 for i in range(n+1)]
for i in range(1,n+1):
	m=input().split()
	if m[0]=="+":
		a[i]=(int)(m[1])
	
ans=0
for t in range(1,n+1):
	if a[t]==0:
		continue
	f=[[0 for i in range(n+2)] for j in range(n+2)]
	f[0][0]=1
	for i in range(1,n+1):
		for j in range(0,i+1):
			if a[i]==0:
				if ((i<=t) or (j>0)):
					f[i][max(j-1,0)]=(f[i][max(j-1,0)]+f[i-1][j])%mod
			else :
				if ((a[i]<a[t]) or ((a[i]==a[t]) and (i<t))):
					f[i][j+1]=(f[i][j+1]+f[i-1][j])%mod
				else :
					f[i][j]=(f[i][j]+f[i-1][j])%mod
			
			if (i!=t) :
				f[i][j]=(f[i][j]+f[i-1][j])%mod
				
			
		
	
	for i in range(0,n+1):
		ans=(ans+f[n][i]*a[t])%mod
	
 
print(ans)

What does lexicographically mean?

Let's first calculate the number of permutation pair $$$(p,q)$$$s (with length $$$i$$$) that $$$p_1<q_1$$$ but $$$inv(p)>inv(q)$$$ ($$$inv(p)$$$ is the number of inversions in $$$p$$$). Call it $$$t_i$$$.

Let's enumerate $$$p_1=j$$$ and $$$q_1=k$$$, then $$$inv(p[2...i])-inv(q[2...i])>k-j$$$. ($$$inv(p)=inv(p[2...i])+j-1,inv(q)=inv(q[2...i])+k-1$$$, with $$$inv(p)>inv(q)$$$ we get the following.)

Precalculate $$$f(i,j)$$$: the number of permutation $$$p$$$s of length $$$i$$$ such that $$$inv(p)=j$$$. Let $$$s(i,j)$$$ be $$$\sum_{k\le j}f(i,k)$$$, then:

$$$f$$$ and $$$s$$$ can be calculated in $$$O(n^4)$$$ or $$$O(n^3)$$$ in the following way: if you insert $$$i$$$ into a permutation of length $$$i-1$$$ after the $$$i-1-p$$$-th element $$$(0\le p\le i-1)$$$, it will bring $$$p$$$ inversions into the permutation. So $$$f(i,j)=\sum_{j-i+1\le k\le j} f(i-1,k)$$$.

After calculating $$$t$$$, calculating the answer it easy. Let $$$ans_i$$$ be the answer for $$$n=i$$$, then

Consider if $$$p_1=q_1$$$. If so, there are $$$i$$$ choices of $$$p_1$$$, and $$$ans_{i-1}$$$ choices of the following $$$n-1$$$ numbers. Otherwise, there are $$$t_i$$$ choices.

Total complexity is $$$O(n^5)$$$, but it can be optimized to $$$O(n^4)$$$ if you consider the difference between $$$j-k$$$ only, and can be optimized to $$$O(n^3\log n)$$$ using FFT with arbitary mod (which we hope can't pass E2!).

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,mod,f[55][2005]={1},s[55][2005]={1},ans[55];
int main(){
	cin>>n>>mod;
	for(int i=1;i<=n*(n-1)/2;i++)s[0][i]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=n*(n-1)/2;j++){
			if(j-i>=0)f[i][j]=(s[i-1][j]-s[i-1][j-i]+mod)%mod;
			else f[i][j]=s[i-1][j];
			s[i][j]=((j?s[i][j-1]:0)+f[i][j])%mod;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			for(int k=j+1;k<=i;k++){
				for(int o=0;o<=(i-1)*(i-2)/2;o++){
					int t=o-(k-j)-1;
					if(t<0)continue;
					ans[i]=(ans[i]+1ll*f[i-1][o]*s[i-1][t]%mod)%mod;
				}
			} 
		}
	}
	for(int i=2;i<=n;i++)ans[i]=(ans[i]+1ll*i*ans[i-1])%mod;
	cout<<ans[n];
}

In E1 we calculated the number of permutation pairs from the number of permutations. Can we calculate the number of permutation pairs directly?

We recommend you to read E1's editorial first.

Let's directly count the number of permutation pairs $$$(p,q)$$$ of length $$$n$$$ with $$$inv(p)-inv(q)=k$$$, instead of counting it indirectly from "the number of permutation $$$p$$$s of length $$$i$$$ such that $$$inv(p)=j$$$.". Call this number $$$f(n,k)$$$.

We have an $$$n^4$$$ transition: $$$f(n,k)=\sum_{|i|<n} f(n-1,k-i)\times (n-|i|)$$$ (Consider where to insert $$$n$$$ in the first and second permutation. If the two places are indices $$$(I,J)$$$, then the delta of $$$inv(p)$$$ is $$$n-I$$$, the other is $$$n-J$$$, so the delta of difference is $$$J-I$$$. In $$$[1,n]$$$ there are $$$n-|J-I|$$$ pairs of integers with difference $$$J-I$$$.)

Let's speed it up. When $$$f(n,k)$$$ moves to $$$f(n,k+1)$$$, it looks like this: ($$$n=4$$$, as an example)

• $$$f(n-1,k-3)\times 1+f(n-1,k-2)\times 2+f(n-1,k-1)\times 3+f(n-1,k)\times 4+f(n-1,k+1)\times 3+f(n-1,k+2)\times 2+f(n-1,k+3)\times 1$$$
• $$$f(n-1,k-2)\times 1+f(n-1,k-1)\times 2+f(n-1,k)\times 3+f(n-1,k+1)\times 4+f(n-1,k+2)\times 3+f(n-1,k+3)\times 2+f(n-1,k+4)\times 1$$$

So with prefix sums $$$s$$$ ($$$s(i,j)=\sum_{k\le j} f(i,k)$$$) we can write $$$f(n,k+1)=f(n,k)-(s(n-1,k)-s(n-1,k-n))+(s(n-1,k+n)-s(n-1,k))$$$.

Note that the second indice of the array might be negative, so we should shift it by $$$130000$$$.

The memory complexity is $$$O(n^3)$$$, so we should only keep two layers of transition to optimize it to $$$O(n^2)$$$ (If implemented well, $$$O(n^3)$$$ memory solutions can also pass.)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int B=130000;
int n,mod,w[2][2*B+5],s[2][2*B+5],ans[505];
int main(){
	cin>>n>>mod;
	w[0][B]=s[0][B]=1;
	for(int i=B;i<=2*B;i++)s[0][i]=1;
	for(int i=1;i<=n;i++){
		int curs=1,I=i&1,J=I^1;
		memset(w[I],0,sizeof(w[I])),memset(s[I],0,sizeof(s[I]));
		for(int u=i*(i-1)/2,j=-u+B;j<=u+B;j++){
			w[I][j]=curs;
			curs=(0ll+curs-s[J][j]+s[J][j-i]+s[J][j+i]-s[J][j]+2ll*mod)%mod;
		}
		for(int j=B-i*(i-1)/2,v=(i+2)*(i+1)/2+B;j<=v;j++)s[I][j]=(s[I][j-1]+w[I][j])%mod;
		for(int j=1;j<i;j++)ans[i]=(ans[i]+1ll*(s[J][(i+1)*i/2+B]-s[J][j+B]+mod)%mod*(i-j))%mod;
	}
	for(int i=2;i<=n;i++)ans[i]=(ans[i]+1ll*i*ans[i-1])%mod;
	cout<<ans[n];
}

#include<bits/stdc++.h>
using namespace std;
int main() {
	puts("2000 2000");
	for(int i=1;i<=2000;i++)cout<<i<<' '<<2000-i+1<<endl; 
	for(int i=1;i<=2000;i++)cout<<90000+i*200<<' '<<992000-i*400+1<<endl; 
}