## [problem:2250A]↵
↵
- Idea:[user:aaa_Pigeon2,2026-07-26]↵
↵
- Solution:[user:aaa_Pigeon2,2026-07-26]↵
↵
<spoiler summary="Solution">↵
Let us determine what is required for every position to contain exactly one element after the simultaneous move.↵
↵
The element initially at position $1$ cannot move to the left, so it must move to the right. Therefore, $w_1>k$. Once it leaves, only the element initially at position $2$ can fill position $1$, so $w_2<k$.↵
↵
Thus, the elements at positions $1$ and $2$ must swap. Repeating the same argument for the remaining positions, the only possible movement pattern is↵
↵
$$↵
1\leftrightarrow 2,\quad 3\leftrightarrow 4,\quad 5\leftrightarrow 6,\ldots↵
$$↵
↵
Consequently, $n$ must be even, every element at an odd position must move to the right, and every element at an even position must move to the left.↵
↵
Let↵
↵
$$↵
L=\max_{i\bmod 2=0}w_i,\qquad R=\min_{i\bmod 2=1}w_i.↵
$$↵
↵
We need an integer $k$ such that $L<k<R$. Such an integer exists if and only if $L+2\le R$.↵
↵
The time complexity is $O(n)$ per test case, and the extra space complexity is $O(1)$.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void work() {↵
int n; cin >> n;↵
long long L = 0, R = 1000000001LL;↵
↵
for (int i = 1; i <= n; ++i) {↵
long long w; cin >> w;↵
if (i & 1) R = min(R, w);↵
else L = max(L, w);↵
}↵
↵
cout << (n % 2 == 0 && L + 2 <= R ? "YES" : "NO") << '\n';↵
}↵
↵
int main() {↵
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
↵
int T; cin >> T;↵
while (T--) work();↵
↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
## [problem:2250B]↵
↵
- Idea:[user:_MCYYDS_,2026-07-26]↵
↵
- Solution:[user:_MCYYDS_,2026-07-26]↵
↵
<spoiler summary="Hint 1">↵
Partition the string into maximal blocks of equal characters. How does the number of blocks determine the number of adjacent equal pairs?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Define a block as a maximal consecutive segment of equal characters. Suppose the string has $r$ blocks with lengths $l_1,l_2,\ldots,l_r$. A block of length $l_i$ contributes exactly $l_i-1$ adjacent equal pairs, so the total number is↵
↵
$$↵
\sum_{i=1}^{r}(l_i-1)=n-r.↵
$$↵
↵
Therefore, we need to construct a string with exactly $r=n-k$ blocks.↵
↵
Because $k<n$, we have $r\ge1$. Since $n\ge2$ and the counts of $\mathtt{0}$ and $\mathtt{1}$ may differ by at most $1$, both characters must appear, so the string must contain at least two blocks. Hence, when $r=1$, or equivalently $k=n-1$, no solution exists.↵
↵
Now assume $r\ge2$. Let the block characters alternate, starting with $\mathtt{0}$. The numbers of $\mathtt{0}$-blocks and $\mathtt{1}$-blocks are↵
↵
$$↵
r_0=\left\lceil\frac r2\right\rceil,\qquad r_1=\left\lfloor\frac r2\right\rfloor.↵
$$↵
↵
We want the total numbers of the two characters to be↵
↵
$$↵
c_0=\left\lceil\frac n2\right\rceil,\qquad c_1=\left\lfloor\frac n2\right\rfloor.↵
$$↵
↵
First assign one character to each block. This uses $r_0$ zeros and $r_1$ ones. Since $r\le n$, we have $r_0\le c_0$ and $r_1\le c_1$.↵
↵
Append all remaining zeros to any $\mathtt{0}$-block and all remaining ones to any $\mathtt{1}$-block, then concatenate the blocks in order. The two character counts differ by at most $1$, and the string has exactly $r$ blocks, so it contains exactly $n-r=k$ adjacent equal pairs.↵
↵
The time complexity is $O(n)$ per test case and $O(\sum n)$ in total. The space complexity is $O(n)$.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void work() {↵
int n, k; cin >> n >> k;↵
↵
if (n > 1 && k == n - 1) {↵
cout << -1 << '\n';↵
return;↵
}↵
if (n == 5 && k == 2) {↵
cout << "01110\n";↵
return;↵
}↵
if (n == 6 && k == 1) {↵
cout << "101001\n";↵
return;↵
}↵
↵
k = n - k;↵
int c0 = (n + 1) / 2, c1 = n / 2;↵
↵
for (int i = 1; i <= k; ++i) {↵
if (i & 1) {↵
if (i + 2 > k) {↵
while (c0--) cout << 0;↵
}↵
else {↵
--c0;↵
cout << 0;↵
}↵
}↵
else {↵
if (i + 2 > k) {↵
while (c1--) cout << 1;↵
}↵
else {↵
--c1;↵
cout << 1;↵
}↵
}↵
}↵
cout << '\n';↵
}↵
↵
int main() {↵
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
↵
int T; cin >> T;↵
while (T--) work();↵
↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
## [problem:2249A]↵
↵
- Idea:[user:aaa_Pigeon2,2026-07-26]↵
↵
- Solution:[user:aaa_Pigeon2,2026-07-26]↵
↵
<spoiler summary="Hint 1">↵
An element's rank from the right depends on both its position in the retained subsequence and the subsequence's final length.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Enumerate the final retained length $m$. Once $m$ is fixed, the condition for every position in the subsequence is fixed.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Whether an element can occupy the $j$-th position of the retained subsequence depends on the final length $m$, because its rank from the right is $m-j+1$.↵
↵
Therefore, we enumerate the final length $m$.↵
↵
For a fixed $m$, scan the original sequence from left to right and fill positions $1,2,\ldots,m$ of the subsequence in order. When filling position $j$, element $i$ can be chosen if and only if↵
↵
$$↵
j\notin[l_i,r_i]↵
$$↵
↵
and↵
↵
$$↵
m-j+1\notin[u_i,v_i].↵
$$↵
↵
Whenever the current element satisfies both conditions, choose it immediately.↵
↵
To prove this greedy choice, suppose a feasible solution chooses an element $x$ for position $j$, while the greedy algorithm chooses an earlier valid element $y$. Replacing $x$ with $y$ leaves every later element of the original solution available and does not reduce the remaining suffix in which subsequent choices must be made. Thus, whenever a feasible solution exists, the greedy algorithm also succeeds.↵
↵
Enumerate $m$ from $n$ down to $1$. The first feasible value is the maximum possible answer. If no positive value is feasible, the answer is $0$.↵
↵
The time complexity is $O(n^2)$ per test case, and the space complexity is $O(n)$.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int N = 5000;↵
↵
int n;↵
int l[N + 10], r[N + 10], u[N + 10], v[N + 10];↵
↵
bool check(int m) {↵
int j = 1;↵
↵
for (int i = 1; i <= n && j <= m; ++i) {↵
int x = m - j + 1;↵
if ((j < l[i] || j > r[i]) && (x < u[i] || x > v[i])) ++j;↵
}↵
↵
return j == m + 1;↵
}↵
↵
void work() {↵
cin >> n;↵
for (int i = 1; i <= n; ++i) cin >> l[i] >> r[i] >> u[i] >> v[i];↵
↵
for (int m = n; m >= 1; --m) {↵
if (!check(m)) continue;↵
cout << m << '\n';↵
return;↵
}↵
↵
cout << 0 << '\n';↵
}↵
↵
int main() {↵
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
↵
int T; cin >> T;↵
while (T--) work();↵
↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
## [problem:2249B]↵
↵
- Idea:[user:aaa_Pigeon2,2026-07-26]↵
↵
- Solution:[user:aaa_Pigeon2,2026-07-26]↵
↵
<spoiler summary="Hint 1">↵
The value $n$ lies on exactly one side of every cut. Therefore, the value of the cut must be the maximum on the opposite side.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Enumerate the dividing point determined by the position of $n$. The cut values to its left must be non-decreasing, while those to its right must be non-increasing.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Merge the left sequence with the reversed right sequence. The first occurrence of a value forces its position, while every later occurrence contributes a number of choices.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
First observe that no cut value can equal $n$. The value $n$ lies on exactly one side of a cut, while the maximum on the opposite side is at most $n-1$. Therefore, if some $a_i=n$, the answer is $0$.↵
↵
Now consider the position of $n$. For cut $i$:↵
↵
- If $n$ lies on the right, then $a_i$ is the maximum of the prefix on the left.↵
- If $n$ lies on the left, then $a_i$ is the maximum of the suffix on the right.↵
↵
Hence, there must be a dividing point $c$ such that $a_1,\ldots,a_c$ is non-decreasing and $a_{c+1},\ldots,a_{n-1}$ is non-increasing. If both parts are non-empty, we must also have $a_c\ne a_{c+1}$. These two maxima are attained at positions on opposite sides of the dividing point, and a permutation cannot contain the same value at both positions.↵
↵
We enumerate all values of $c$ satisfying these conditions. There may seem to be many candidates, but the indices belonging to both the non-decreasing prefix and the non-increasing suffix can only form a segment of equal values. Two adjacent equal values cannot form an internal boundary, so only a constant number of candidates need to be considered.↵
↵
After fixing $c$, merge↵
↵
$$↵
a_1,a_2,\ldots,a_c↵
$$↵
↵
with the reversed right part↵
↵
$$↵
a_{n-1},a_{n-2},\ldots,a_{c+1}↵
$$↵
↵
to obtain one non-decreasing sequence. Process its $i$-th value $x$:↵
↵
- If this is the first occurrence of $x$, then the maximum on that side must become $x$ at this position, so the assigned permutation value is forced to be $x$.↵
- Otherwise, we may assign any unused value smaller than $x$. Since $i-1$ values have already been used, there are $x-i+1$ choices.↵
↵
For each repeated occurrence, multiply the answer by $x-i+1$. This gives the number of permutations corresponding to the fixed dividing point. Finally, sum these values over all valid dividing points.↵
↵
Each merge takes $O(n)$ time. Since only a constant number of dividing points are valid, the time complexity is $O(n)$ per test case, and the space complexity is $O(n)$.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int N = 1000000;↵
const int mod = 998244353;↵
↵
int n;↵
int a[N + 10], vis[N + 10];↵
bool pre[N + 10], suf[N + 10];↵
↵
void work() {↵
cin >> n;↵
for (int i = 1; i < n; ++i) cin >> a[i];↵
a[n] = 0;↵
↵
for (int i = 1; i < n; ++i) {↵
if (a[i] != n) continue;↵
cout << 0 << '\n';↵
return;↵
}↵
↵
pre[0] = 1;↵
for (int i = 1; i < n; ++i) pre[i] = pre[i - 1] && a[i] >= a[i - 1];↵
suf[n] = 1;↵
for (int i = n - 1; i >= 1; --i) suf[i] = suf[i + 1] && a[i] >= a[i + 1];↵
↵
long long ans = 0;↵
for (int cut = 0; cut < n; ++cut) {↵
if (!pre[cut] || !suf[cut + 1]) continue;↵
↵
if (cut > 0 && cut < n - 1 && a[cut] == a[cut + 1]) continue;↵
↵
vector<int> l, r;↵
for (int i = 1; i <= cut; ++i) l.push_back(a[i]);↵
for (int i = cut + 1; i < n; ++i) r.push_back(a[i]);↵
↵
if (!l.empty() && !r.empty() && l.back() == r.front()) continue;↵
reverse(r.begin(), r.end());↵
↵
memset(vis, 0, sizeof(int) * (n + 1));↵
int x = 0, y = 0, used = 0;↵
long long ways = 1;↵
↵
while (x < (int)l.size() || y < (int)r.size()) {↵
int w;↵
if (x == (int)l.size()) w = r[y++];↵
else if (y == (int)r.size()) w = l[x++];↵
else if (l[x] < r[y]) w = l[x++];↵
else if (l[x] > r[y]) w = r[y++];↵
else {↵
cout << 0 << '\n';↵
return;↵
}↵
↵
if (!vis[w]) vis[w] = 1;↵
else if (w < used) ways = 0;↵
else ways = ways * (w - used) % mod;↵
++used;↵
}↵
↵
ans += ways;↵
}↵
↵
cout << ans % mod << '\n';↵
}↵
↵
int main() {↵
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
↵
int T; cin >> T;↵
while (T--) work();↵
↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
## [problem:2249C]↵
↵
- Idea:[user:aaa_Pigeon2,2026-07-26]↵
↵
- Solution:[user:aaa_Pigeon2,2026-07-26]↵
↵
<spoiler summary="Hint 1">↵
Duplicate the permutation so that the cyclic sequence starting at any position becomes an ordinary contiguous segment of the duplicated array.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
After inserting a new value $x$, the change in the number of consecutive-value blocks depends only on whether $x-1$ and $x+1$ have already appeared.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Maintain the number of blocks for all starting positions simultaneously. Once a starting position has produced more than two blocks, it can be discarded permanently.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Checking every prefix separately for every starting position would introduce an additional factor of $n$. Instead, duplicate the permutation and define↵
↵
$$↵
q_i=p_{((i-1)\bmod n)+1}.↵
$$↵
↵
For a starting position $l$, the successive cyclic prefixes become the ordinary segments $[l,l],[l,l+1],\ldots,[l,l+n-1]$.↵
↵
Enumerate the right endpoint $r$ from left to right. When $q_r$ is inserted, the starting positions whose current segment ends at $r$ form the interval↵
↵
$$↵
L=\max(1,r-n+1),\qquad R=\min(r,n).↵
$$↵
↵
Let the new value be $x$. Because the current segment has length at most $n$, no permutation value appears twice. The change in the number of consecutive-value blocks is↵
↵
$$↵
\Delta=1-[x-1\text{ has already appeared}]-[x+1\text{ has already appeared}].↵
$$↵
↵
We first regard $x$ as a new block, then merge it with the block on either side whenever the corresponding neighboring value has already appeared.↵
↵
To update all starting positions simultaneously, let $\operatorname{last}_v$ be the latest position before $r$ at which value $v$ appeared. For a starting position $l$, value $v$ appears in $[l,r-1]$ if and only if $\operatorname{last}_v\ge l$.↵
↵
Therefore, inserting $x$ requires only three range additions:↵
↵
1. Add $1$ to $[L,R]$.↵
2. If $x-1$ exists, subtract $1$ from $[L,\min(R,\operatorname{last}_{x-1})]$.↵
3. If $x+1$ exists, subtract $1$ from $[L,\min(R,\operatorname{last}_{x+1})]$.↵
↵
Use a lazy segment tree to maintain the current number of blocks for every starting position, with range addition and a global maximum query. Once a starting position has more than two blocks, it has already produced an invalid prefix. A later decrease cannot erase that earlier invalid prefix, so the starting position can be removed permanently.↵
↵
Each starting position is removed at most once. We process $2n-1$ right endpoints, performing only a constant number of range operations for each one. Thus, the time complexity is $O(n\log n)$, and the space complexity is $O(n)$.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int N = 200000;↵
const int inf = 1000000000;↵
↵
int n;↵
int p[N + 10], last[N + 10];↵
int mx[4 * N + 10], lazy[4 * N + 10];↵
↵
void apply(int u, int v) {↵
mx[u] += v;↵
lazy[u] += v;↵
}↵
↵
void push(int u) {↵
if (!lazy[u]) return;↵
apply(u << 1, lazy[u]);↵
apply(u << 1 | 1, lazy[u]);↵
lazy[u] = 0;↵
}↵
↵
void add(int u, int l, int r, int ql, int qr, int v) {↵
if (ql <= l && r <= qr) {↵
apply(u, v);↵
return;↵
}↵
↵
push(u);↵
int mid = (l + r) >> 1;↵
if (ql <= mid) add(u << 1, l, mid, ql, qr, v);↵
if (qr > mid) add(u << 1 | 1, mid + 1, r, ql, qr, v);↵
mx[u] = max(mx[u << 1], mx[u << 1 | 1]);↵
}↵
↵
void add(int l, int r, int v) {↵
if (l <= r) add(1, 1, n, l, r, v);↵
}↵
↵
int find_bad(int u, int l, int r) {↵
if (l == r) return l;↵
↵
push(u);↵
int mid = (l + r) >> 1;↵
if (mx[u << 1] > 2) return find_bad(u << 1, l, mid);↵
return find_bad(u << 1 | 1, mid + 1, r);↵
}↵
↵
void del(int u, int l, int r, int x) {↵
if (l == r) {↵
mx[u] = -inf;↵
lazy[u] = 0;↵
return;↵
}↵
↵
push(u);↵
int mid = (l + r) >> 1;↵
if (x <= mid) del(u << 1, l, mid, x);↵
else del(u << 1 | 1, mid + 1, r, x);↵
mx[u] = max(mx[u << 1], mx[u << 1 | 1]);↵
}↵
↵
void work() {↵
cin >> n;↵
for (int i = 1; i <= n; ++i) cin >> p[i];↵
↵
memset(last, 0, sizeof(int) * (n + 2));↵
memset(mx, 0, sizeof(int) * (4 * n + 5));↵
memset(lazy, 0, sizeof(int) * (4 * n + 5));↵
↵
int ans = n;↵
for (int r = 1; r < 2 * n; ++r) {↵
int L = max(1, r - n + 1), R = min(r, n);↵
int x = p[(r - 1) % n + 1];↵
↵
add(L, R, 1);↵
if (x > 1 && last[x - 1] >= L) add(L, min(R, last[x - 1]), -1);↵
if (x < n && last[x + 1] >= L) add(L, min(R, last[x + 1]), -1);↵
last[x] = r;↵
↵
while (mx[1] > 2) {↵
int x = find_bad(1, 1, n);↵
del(1, 1, n, x);↵
--ans;↵
}↵
}↵
↵
cout << ans << '\n';↵
}↵
↵
int main() {↵
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
↵
int T; cin >> T;↵
while (T--) work();↵
↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
## [problem:2249D]↵
↵
- Idea:[user:aaa_Pigeon2,2026-07-26]↵
↵
- Solution:[user:aaa_Pigeon2,2026-07-26]↵
↵
<spoiler summary="Hint 1">↵
Compare two adjacent rows. For a fixed pair of rows, the $2\times2$ condition forces the XOR difference between corresponding entries to alternate with the parity of the column.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
We need many values $h$ satisfying↵
↵
$$↵
\{0,1,\ldots,n-1\}\mathbin{\operatorname{xor}}h=\{0,1,\ldots,n-1\}.↵
$$↵
↵
How large is the XOR stabilizer of this set?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
When $n$ is a power of two, pair the values as $y\leftrightarrow y\oplus x$, and place several complete pairs at odd positions.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
We first determine when a solution can exist. Let $S=\{0,1,\ldots,n-1\}$, and define the XOR difference between adjacent rows in column $j$ by↵
↵
$$↵
d_i(j)=A_{i,j}\oplus A_{i+1,j}.↵
$$↵
↵
The condition on every adjacent $2\times2$ submatrix implies↵
↵
$$↵
d_i(j+1)=d_i(j)\oplus x.↵
$$↵
↵
Thus, once the parity of the column is fixed, the XOR difference between the two rows is fixed. At least $\lceil n/2\rceil$ rows have the same parity, and every column must be a permutation. Therefore, we need at least $\lceil n/2\rceil$ distinct values $h$ such that $S\oplus h=S$.↵
↵
Let $L=\operatorname{lowbit}(n)$. The XOR stabilizer of $S$ is exactly↵
↵
$$↵
\{0,1,\ldots,L-1\}.↵
$$↵
↵
Every value smaller than $L$ merely permutes elements within blocks of length $L$. Conversely, write $h=gL+r$, where $0\le r<L$. If $g\ne0$, XOR by $h$ induces a nontrivial pairing of the block indices. Since the number of blocks, $n/L$, is odd, the whole set of block indices cannot remain invariant. Hence, $g=0$.↵
↵
The necessary condition is therefore↵
↵
$$↵
\operatorname{lowbit}(n)\ge\left\lceil\frac n2\right\rceil.↵
$$↵
↵
This holds only when $n$ is a power of two. In addition, when $n=2$, each value appears twice in any $2\times2$ Latin square, so the XOR of all four entries is always $0$. Thus, no solution exists for $n=2$ and $x>0$.↵
↵
We now describe the construction.↵
↵
If $x=0$, set↵
↵
$$↵
A_{i,j}=i\oplus j.↵
$$↵
↵
Because $n$ is a power of two, XOR with a fixed value permutes $S$, so every row and every column is a permutation. In each adjacent $2\times2$ submatrix, every index term appears twice, and the total XOR is $0$.↵
↵
Now assume $x>0$, $n$ is a power of two, and $n\ge4$. The map $y\mapsto y\oplus x$ partitions $S$ into $n/2$ pairs. Choose $n/4$ of these pairs to form a set $O$, and let the remaining values form a set $E$. Then↵
↵
$$↵
|E|=|O|=\frac n2,\qquad E\oplus x=E,\qquad O\oplus x=O.↵
$$↵
↵
Construct a permutation $p$ by placing the elements of $E$ at even positions and the elements of $O$ at odd positions. Then define↵
↵
$$↵
A_{i,j}=p_i\oplus p_j\oplus\bigl((i\bmod2)(j\bmod2)x\bigr).↵
$$↵
↵
Every even-indexed row is a fixed XOR translation of $p$. In an odd-indexed row, the even columns contain $p_i\oplus E$, while the odd columns contain $p_i\oplus(O\oplus x)=p_i\oplus O$. Together, they still form $S$. The formula is symmetric in $i$ and $j$, so the same argument applies to every column.↵
↵
Finally, consider any adjacent $2\times2$ submatrix. The four terms involving $p$ cancel in pairs. Among the four parity pairs, exactly one is $(1,1)$, so the remaining XOR is exactly $x$.↵
↵
The output contains $n^2$ numbers, so the time complexity is $O(n^2)$, and the extra space complexity is $O(n)$.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int N = 2500;↵
↵
int n, x;↵
int vis[N + 10], in_o[N + 10], e[N + 10], o[N + 10], a[N + 10];↵
pair<int, int> p[N + 10];↵
↵
bool check(int v) {↵
return (v & (v - 1)) == 0;↵
}↵
↵
void work() {↵
cin >> n >> x;↵
↵
if (!check(n) || (x && n < 4)) {↵
cout << -1 << '\n';↵
return;↵
}↵
↵
if (!x) {↵
for (int i = 0; i < n; ++i) {↵
for (int j = 0; j < n; ++j) {↵
cout << (i ^ j) << (j + 1 == n ? '\n' : ' ');↵
}↵
}↵
return;↵
}↵
↵
for (int i = 0; i <= n; ++i) vis[i] = in_o[i] = e[i] = o[i] = a[i] = 0;↵
↵
int cnt = 0;↵
for (int i = 0; i < n; ++i) {↵
if (vis[i]) continue;↵
int j = i ^ x;↵
vis[i] = vis[j] = 1;↵
p[++cnt] = {i, j};↵
}↵
↵
for (int i = 1; i <= n / 4; ++i) in_o[p[i].first] = in_o[p[i].second] = 1;↵
↵
int ec = 0, oc = 0;↵
for (int i = 0; i < n; ++i) {↵
if (in_o[i]) o[++oc] = i;↵
else e[++ec] = i;↵
}↵
↵
ec = oc = 0;↵
for (int i = 0; i < n; ++i) {↵
if (i & 1) a[i] = o[++oc];↵
else a[i] = e[++ec];↵
}↵
↵
for (int i = 0; i < n; ++i) {↵
for (int j = 0; j < n; ++j) {↵
int v = a[i] ^ a[j];↵
if ((i & 1) && (j & 1)) v ^= x;↵
cout << v << (j + 1 == n ? '\n' : ' ');↵
}↵
}↵
}↵
↵
int main() {↵
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
↵
int T; cin >> T;↵
while (T--) work();↵
↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
## [problem:2249E1]↵
↵
- Idea:[user:131241,2026-07-26]↵
↵
- Solution:[user:131241,2026-07-26]↵
↵
<spoiler summary="Hint 1">↵
Treat a prefix of length $k^i$ as one block. How can it be decomposed into smaller blocks?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Adding the same value to every character modulo $k$ produces only finitely many translated versions of the pattern-matching problem.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
For each block, store its internal occurrence count and its prefix and suffix of length at most $n-1$. When two blocks are merged, only occurrences crossing their boundary need additional processing.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Consider the self-similar structure of the infinite string. Let $B_{i,j}$ denote the standard block of length $k^i$ whose characters are all shifted by $j$ modulo $k$. Then↵
↵
$$↵
B_{i,j}=B_{i-1,j}B_{i-1,j+1}\cdots B_{i-1,j+k-1},↵
$$↵
↵
where all second indices are taken modulo $k$. This follows directly from how the base-$k$ digit sum changes when the highest digit is increased.↵
↵
For the current pattern $t$, maintain the following information for every block:↵
↵
- The number of occurrences of $t$ entirely inside the block.↵
- A prefix of the block of length at most $n-1$.↵
- A suffix of the block of length at most $n-1$.↵
↵
When two adjacent blocks are concatenated, their internal occurrence counts are added. Every newly created occurrence must cross the boundary, so it is sufficient to run KMP on the suffix of the left block followed by the prefix of the right block. The new prefix and suffix are again truncated to at most $n-1$ characters.↵
↵
Storing these boundary strings explicitly at every level would still be too slow. Let $x$ be the smallest integer such that $n\le k^x$. Once the block length reaches this scale, every boundary string is a uniform translation of the boundary of a standard block. Therefore, the contribution across the boundary of two large blocks depends only on their two translation values. There are only $k^2$ such pairs, so all of them can be precomputed.↵
↵
For a query interval $[l,r]$, recursively decompose it in base $k$ into $O(k\log_k V)$ standard blocks and concatenate them in order. The internal occurrence count of each block is obtained from preprocessing, while occurrences crossing block boundaries are counted using either the stored short boundaries or the precomputed translation transitions.↵
↵
At levels where the block length is smaller than $n$, the pattern cannot occur entirely inside a block. The first critical level can be processed directly; at all larger levels, only the finite set of translation transitions is needed. The total time complexity is↵
↵
$$↵
O\left(\sum n\cdot k^2+qk^2\log_k V\right),↵
$$↵
↵
where $V=10^{17}$. The space complexity is $O(n+k^2\log_k V)$.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
struct node {↵
long long v = 0;↵
bool b = 0;↵
string l = "", r = "";↵
int l1, r1;↵
};↵
↵
int n, k;↵
int fai[2000005];↵
long long T, ql, qr, trans[10][10];↵
long long ma, L, R;↵
node a[66][10], ans;↵
string pl[10], pr[10], s;↵
↵
void make_fai() {↵
for (int i = 1; i <= n; ++i) s[i] ^= 48;↵
↵
int l = 0;↵
for (int i = 2; i <= n; ++i) {↵
while (l && s[l + 1] != s[i]) l = fai[l];↵
l += s[l + 1] == s[i];↵
fai[i] = l;↵
}↵
}↵
↵
int val(string x) {↵
int l = 0, res = 0;↵
↵
for (int i = 0; i < (int)x.size(); ++i) {↵
while (l && s[l + 1] != x[i]) l = fai[l];↵
l += s[l + 1] == x[i];↵
if (l == n) ++res;↵
}↵
↵
return res;↵
}↵
↵
node add(node &x, node &y) {↵
node res;↵
↵
if (x.b && y.b) {↵
res.b = 1;↵
res.l1 = x.l1;↵
res.r1 = y.r1;↵
res.v = x.v + y.v + trans[x.r1][y.l1];↵
return res;↵
}↵
↵
if (x.b) x.l = pl[x.l1], x.r = pr[x.r1];↵
if (y.b) y.l = pl[y.l1], y.r = pr[y.r1];↵
res.v = x.v + y.v + val(x.r + y.l);↵
res.l = x.l;↵
↵
if ((int)res.l.size() < n - 1) {↵
int t = min(n - 1 - (int)res.l.size(), (int)y.l.size());↵
res.l += y.l.substr(0, t);↵
}↵
↵
res.r = y.r;↵
if ((int)res.r.size() < n - 1) {↵
int t = min(n - 1 - (int)res.r.size(), (int)x.r.size());↵
res.r = x.r.substr(x.r.size() - t, t) + res.r;↵
}↵
↵
return res;↵
}↵
↵
void init(long long x) {↵
bool done = 0;↵
↵
for (long long cur = 1, i = 0; cur <= x; cur *= k, ++i) {↵
ma = i;↵
L = 0, R = cur;↵
↵
if (i == 0) {↵
for (int j = 0; j < k; ++j) {↵
if (n == 1) {↵
a[0][j].v = j == s[1];↵
a[0][j].b = 0;↵
a[0][j].l = a[0][j].r = "";↵
}↵
else {↵
a[0][j].v = 0;↵
a[0][j].b = 0;↵
a[0][j].l = a[0][j].r = "";↵
a[0][j].l += (char)j;↵
a[0][j].r = a[0][j].l;↵
}↵
}↵
}↵
else {↵
for (int j = 0; j < k; ++j) {↵
node cur;↵
for (int t = 0; t < k; ++t) {↵
if (!cur.v && !cur.b && cur.l.empty()) cur = a[i - 1][(j + t) % k];↵
else cur = add(cur, a[i - 1][(j + t) % k]);↵
}↵
a[i][j] = cur;↵
}↵
}↵
↵
if (!done && cur >= n - 1) {↵
done = 1;↵
for (int j = 0; j < k; ++j) {↵
pl[j] = a[i][j].l;↵
pr[j] = a[i][j].r;↵
a[i][j].b = 1;↵
a[i][j].l1 = a[i][j].r1 = j;↵
a[i][j].l = a[i][j].r = "";↵
}↵
for (int j = 0; j < k; ++j) {↵
for (int t = 0; t < k; ++t) trans[j][t] = val(pr[j] + pl[t]);↵
}↵
}↵
}↵
}↵
↵
void calc(int dep, int st, long long l, long long r) {↵
if (r <= ql || l > qr) return;↵
↵
if (ql <= l && r - 1 <= qr) {↵
ans = add(ans, a[dep][st]);↵
return;↵
}↵
↵
node cur;↵
long long len = r - l;↵
↵
for (int i = 0; i < k; ++i) {↵
long long nl = l + len / k * i, nr = nl + len / k;↵
↵
if (ql <= nl && nr - 1 <= qr) {↵
if (!cur.v && !cur.b && cur.l.empty()) cur = a[dep - 1][(st + i) % k];↵
else cur = add(cur, a[dep - 1][(st + i) % k]);↵
continue;↵
}↵
↵
if (cur.v || cur.b || !cur.l.empty()) {↵
ans = add(ans, cur);↵
cur.v = 0, cur.b = 0;↵
cur.l = cur.r = "";↵
}↵
calc(dep - 1, (st + i) % k, nl, nr);↵
}↵
↵
if (cur.v || cur.b || !cur.l.empty()) ans = add(ans, cur);↵
}↵
↵
int main() {↵
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
↵
cin >>Tk >> kT;↵
while (T--) {↵
cin >> ql >> qr >> n >> s;↵
s = " " + s + "!";↵
↵
make_fai();↵
init(qr);↵
++ma, R *= k;↵
↵
ans.v = 0, ans.b = 0;↵
ans.l = ans.r = "";↵
calc(ma, 0, L, R);↵
cout << ans.v << '\n';↵
}↵
↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
## [problem:2249E2]↵
↵
- Idea:[user:131241,2026-07-26]↵
↵
- Solution:[user:131241,2026-07-26]↵
↵
<spoiler summary="Hint 1">↵
Partition the infinite string into blocks of length $k$. Every block is a cyclic shift of $\mathtt{012\ldots(k-1)}$. If each block is replaced by its shift value, the resulting sequence is the original infinite string again.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Let↵
↵
$$↵
d_i=(t_i-t_{i-1}+k)\bmod k.↵
$$↵
↵
Inside a complete block, $d_i$ is always $1$. Therefore, all positions with $d_i\ne1$ must have the same residue modulo $k$.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
If the positions with $d_i\ne1$ determine the block boundaries, compress both the pattern and the query interval by a factor of about $k$ and recurse. If no such position exists, an occurring pattern cannot be longer than $2k$.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
First examine the block structure of the infinite string $s$. Every block of length $k$ is a cyclic shift of↵
↵
$$↵
\mathtt{012\ldots(k-1)}.↵
$$↵
↵
If each complete block is replaced by its shift value, the resulting sequence is again $s$. Therefore, once the pattern $t$ is aligned with these blocks, both the pattern and the query interval can be compressed by a factor of about $k$.↵
↵
To determine the alignment, consider the adjacent differences of $t$ modulo $k$:↵
↵
$$↵
d_i=(t_i-t_{i-1}+k)\bmod k.↵
$$↵
↵
Inside a complete cyclic block, every adjacent difference is $1$. Hence, every position with $d_i\ne1$ must correspond to the same type of block boundary, so all such positions must have the same residue modulo $k$. If two different residues occur, the pattern cannot appear.↵
↵
If exactly one residue class occurs, the block boundaries are uniquely determined. Split $t$ according to these boundaries, compress each complete block into its shift value, map $[l,r]$ to the corresponding compressed interval according to the two partial end blocks, and recurse.↵
↵
It remains to handle the case in which every $d_i=1$, so the block boundaries are not determined. The string $s$ contains no substring longer than $2k$ whose adjacent differences are all $1$. Otherwise, there would be three corresponding terms satisfying $s_i=s_{i+k}=s_{i+2k}$. However, the equality $s_i=s_{i+k}$ requires a particular carry pattern when $i$ is increased by $k$, and the same pattern cannot hold again for $i+k$.↵
↵
Therefore, any pattern that occurs must satisfy $n\le2k$. We can enumerate all possible block alignments, reducing the compressed pattern to length at most $2$. When $n\le k$, we must also consider alignments that compress it to a single character. Different alignments correspond to different starting positions in the original string, so they are not counted more than once.↵
↵
We are left with occurrence queries for patterns of length $1$ or $2$.↵
↵
For a pattern of length $1$, every complete block of length $k$ contains each character exactly once. Only the final partial block of a prefix query needs to be checked directly.↵
↵
For a pattern of length $2$, precompute↵
↵
$$↵
f_{p,q,x,y},↵
$$↵
↵
the number of occurrences of the pair $xy$ in the first $qk^p$ characters. A block at the next level consists of $k$ shifted copies of a smaller block. Their internal contributions are accumulated with the appropriate shifts, and occurrences crossing block boundaries are counted by checking adjacent endpoints. A prefix can be decomposed in base $k$, and an interval answer is obtained by subtracting two prefix answers.↵
↵
The total time complexity is↵
↵
$$↵
O\left(qk\log_k V+\sum n+k^3\log_k V+k\log_k^2V\right),↵
$$↵
↵
where $V=10^{17}$.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```cpp↵
#include<bits/stdc++.h>↵
#define int long long↵
using namespace std;↵
int lg;↵
int q,L,R,n,k,d[10000005],t[100],b[100];↵
char c[10000005],s[10000005];↵
struct node{↵
int f[65][65];↵
}sum[65][65];↵
node merge(node a,node b,int v=1){↵
for(int i=0;i<k;i++){↵
for(int j=0;j<k;j++){↵
a.f[(i+v)%k][(j+v)%k]+=b.f[i][j];↵
}↵
}↵
return a;↵
}↵
int calc(int x){↵
int sum=0;↵
while(x){↵
sum+=x%k;↵
x=x/k;↵
}↵
return sum%k;↵
}↵
int sp[70];↵
int gs(int r,int x,int y){↵
// Count occurrences of the pattern "xy" in the range [0, r].↵
r++;↵
int cnt=0,xnow=0,ans=0,lowbit=0;↵
for(int i=0;i<=lg;i++){↵
sp[i]=r%k;r/=k;↵
}↵
for(int i=lg;i>=0;i--){↵
int j=sp[i];↵
if(!j) continue;↵
ans+=sum[i][j].f[(x+(k-1)*cnt)%k][(y+(k-1)*cnt)%k];↵
if(xnow){↵
int px=(cnt-1+lowbit*(k-1))%k,py=cnt%k;↵
if(px==x&&py==y){↵
ans++;↵
}↵
}↵
xnow+=b[i]*j;↵
cnt+=j;↵
lowbit=i;↵
}↵
return ans;↵
}↵
int gs(int r,int x){↵
// Count occurrences of the pattern "x" in the range [0, r].↵
r++;↵
int sum=r/k,pl=r/k*k,y=calc(pl);↵
while(pl<r){↵
if(y==x){↵
sum++;↵
break;↵
}↵
pl++;↵
y++;↵
y>=k?y-=k:0;↵
}↵
return sum;↵
}↵
void print(char c){↵
if(c<10){↵
cout<<char(c+'0');↵
}else{↵
cout<<char(c+'a'-10);↵
}↵
}↵
int ans=0;↵
void solve(int l,int r,int n){↵
// Compute the answer recursively.↵
if(l>r){↵
return ;↵
}↵
for(int i=0;i<k;i++){↵
t[i]=0;↵
}↵
if(n<=2){↵
// For length at most 2, use prefix-count differences directly.↵
if(n==2){↵
int pl=c[0],pr=c[1];↵
int sum=gs(r,pl,pr)-gs(l,pl,pr);↵
ans+=sum;↵
return ;↵
}else{↵
int sum=0;↵
sum=gs(r,c[0])-gs(l-1,c[0]);↵
ans+=sum;↵
return ;↵
}↵
}↵
int cnt=0;↵
for(int i=1;i<n;i++){↵
d[i]=(c[i]-c[i-1]+k)%k;↵
if(d[i]!=1){↵
if(!t[i%k]) cnt++;↵
t[i%k]=1;↵
}↵
}↵
if(cnt>1){↵
// If more than one residue occurs, the pattern cannot appear.↵
return ;↵
}↵
int m=0,pl=k,pr=k,p=0;↵
if(cnt){↵
// At least one adjacent difference is not 1.↵
for(int i=1;i<n;i++){↵
if(d[i]!=1) p=i%k;↵
}↵
if(p){↵
pl=p;↵
s[m++]=(c[p-1]+1)%k;↵
}↵
for(int i=p;i<n;i+=k){↵
if(i+k-1>=n) pr=n-i;↵
s[m++]=c[i];↵
}↵
↵
// Handle the two partial boundary blocks separately.↵
int bl=(r/k)*k,br=(l/k+1)*k-1;↵
if(br-l+1<pl) l=l/k+1;↵
else l=l/k;↵
if(r-bl+1<pr) r=r/k-1;↵
else r=r/k;↵
↵
for(int i=0;i<m;i++) c[i]=s[i];↵
solve(l,r,m);↵
}else{↵
// Every adjacent difference is 1.↵
int szl=(l/k+1)*k-l,szr=r-(r/k)*k+1,L,R;↵
if(n<=k){↵
int x=c[0];↵
for(int i=0;i+n-1<k;i++){↵
c[0]=(x-i+k)%k;↵
// Handle the two partial boundary blocks separately.↵
pl=k-i,pr=i+n;↵
if(szl<pl) L=l/k+1;↵
else L=l/k;↵
if(szr<pr) R=r/k-1;↵
else R=r/k;↵
solve(L,R,1);↵
}↵
}↵
for(int i=0;i<n;i++){↵
s[i]=c[i];↵
}↵
for(int i=0;i<min(n-1,k);i++){↵
// Handle the two partial boundary blocks separately.↵
pl=i+1,pr=n-1-i;↵
if(pr>k) continue;↵
if(szl<pl) L=l/k+1;↵
else L=l/k;↵
if(szr<pr) R=r/k-1;↵
else R=r/k;↵
c[0]=c[1]=s[i+1];↵
solve(L,R,2);↵
}↵
}↵
}↵
char change(int x){↵
if(0<=x&&x<=9) return x+'0';↵
if(10<=x&&x<=35) return x-10+'A';↵
if(36<=x&&x<=61) return x-36+'a';↵
}↵
int change(char x){↵
if('0'<=x&&x<='9') return x-'0';↵
if('A'<=x&&x<='Z') return x+10-'A';↵
if('a'<=x&&x<='z') return x+36-'a';↵
}↵
signed main(){↵
ios::sync_with_stdio(0);↵
cin.tie(0);cout.tie(0);↵
cin>>k>>q;↵
↵
// sum[i][j] stores counts of length-2 substrings in the first j * k^i characters.↵
b[0]=1;lg=0;↵
for(int i=1;i<=k;i++){↵
for(int j=1;j<i;j++){↵
sum[0][i].f[j-1][j]=1;↵
}↵
}↵
for(int p=1;p;p++){↵
b[p]=b[p-1]*k;↵
lg++;↵
if(b[p]>1e17){↵
break;↵
}↵
sum[p][1]=sum[p-1][k];↵
// Concatenate the k shifted blocks.↵
for(int i=2;i<=k;i++){↵
sum[p][i]=merge(sum[p][i-1],sum[p-1][k],i-1);↵
// Count substrings that cross a block boundary directly.↵
sum[p][i].f[calc(b[p]*(i-1)-1)][calc(b[p]*(i-1))]++;↵
}↵
}↵
↵
while(q--){↵
cin>>L>>R>>n;↵
cin>>c;↵
for(int i=0;i<n;i++){↵
c[i]=change(c[i]);↵
}↵
solve(L,R,n);↵
cout<<ans<<endl;↵
ans=0;↵
}↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
## [problem:2249F]↵
↵
- Idea:[user:aaa_Pigeon2,2026-07-26]↵
↵
- Solution:[user:aaa_Pigeon2,2026-07-26]↵
↵
<spoiler summary="Hint 1">↵
In a simple path, the two endpoints have degree $1$, every other used vertex has degree $2$, and every unused vertex has degree $0$. Can this degree condition be encoded by a matching?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Split every vertex into left and right copies, but remove $R(1)$ and $L(n)$. Original edges connect copies within the same layer, while an unused internal vertex matches its two copies with a cross-layer edge.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Give every cross-layer edge weight $M$ and every same-layer edge corresponding to an original edge weight $M-1$. A maximum-weight matching eliminates extra cycles and minimizes the resulting path length.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
#### Auxiliary-Graph Construction↵
↵
The main difficulty is the simple-path constraint. We encode the degree structure of a simple path as a matching.↵
↵
A simple path from vertex $1$ to vertex $n$ satisfies the following degree conditions:↵
↵
- Vertices $1$ and $n$ have degree $1$ in the path.↵
- Every other used vertex has degree $2$.↵
- Every unused vertex has degree $0$.↵
↵
For every vertex $v$ of the original graph $G=(V,E)$, create two copies, $L(v)$ and $R(v)$, and then remove $R(1)$ and $L(n)$. The vertex set of the auxiliary graph $G'=(V',E')$ is↵
↵
$$↵
V'=\{L(v)\mid v\ne n\}\cup\{R(v)\mid v\ne1\}.↵
$$↵
↵
Removing these two copies ensures that vertices $1$ and $n$ contribute exactly one path edge each. Because the removed copies belong to different layers, the recovered path is also forced to have even length.↵
↵
For every original edge $(u,v)\in E$, add the same-layer edges $(L(u),L(v))$ and $(R(u),R(v))$ whenever both endpoint copies exist. Give each of these edges weight $M-1$.↵
↵
For every internal vertex $v\notin\{1,n\}$, add a cross-layer edge $(L(v),R(v))$ of weight $M$, where $M$ is any constant greater than $|V'|$.↵
↵
Compute a maximum-weight matching in the general graph $G'$. If it is not perfect, no valid path exists. Otherwise, the answer can be recovered from it. Since $M>|V'|$, whenever a perfect matching exists, losing one matching edge decreases the weight by more than all possible gains obtained by replacing the remaining edges. Therefore, a maximum-weight matching must be perfect.↵
↵
#### Interpretation of a Perfect Matching↵
↵
Consider a perfect matching $S$.↵
↵
For an internal vertex $v$, if $S$ contains the cross-layer edge $(L(v),R(v))$, then $v$ is unused, corresponding to degree $0$ in the original graph.↵
↵
Otherwise, $L(v)$ and $R(v)$ are each matched by a same-layer edge, so $v$ has degree $2$ in the original graph.↵
↵
Vertices $1$ and $n$ each have only one copy and no cross-layer edge, so they naturally have degree $1$.↵
↵
Thus, mapping all selected same-layer edges back to the original graph yields a path from $1$ to $n$, together with zero or more vertex-disjoint cycles.↵
↵
#### Why the Path Length Is Even↵
↵
Suppose there is an even-length simple path↵
↵
$$↵
p_0=1,p_1,p_2,\ldots,p_L=n.↵
$$↵
↵
Choose same-layer edges alternately along the path: use the left layer for the first edge, the right layer for the second edge, and so on. Since $L$ is even, the last edge lies in the right layer and reaches the existing copy $R(n)$. Every internal vertex not on the path is matched by its own cross-layer edge, producing a perfect matching.↵
↵
Conversely, take the symmetric difference of any perfect matching with the set of all cross-layer edges. The component containing $L(1)$ alternates between same-layer matching edges and cross-layer edges and eventually reaches $R(n)$. Consequently, it contains an even number of original edges. It has exactly two vertices of degree $1$, while every other vertex has degree $2$, so it corresponds to an even-length simple path.↵
↵
#### Why Maximum Weight Eliminates Cycles↵
↵
Suppose the recovered structure contains a cycle with $c$ vertices. The cycle uses $c$ same-layer matching edges of weight $M-1$, for a total weight of $c(M-1)$.↵
↵
Remove these edges and instead select the cross-layer edge of every vertex on the cycle. This still gives a perfect matching, but the total weight contributed by these vertices becomes $cM$, which is strictly larger. This contradicts maximality. Therefore, a maximum-weight perfect matching contains no extra cycle.↵
↵
#### Why the Recovered Path Is Shortest↵
↵
Every perfect matching contains the same number of edges. Cross-layer edges have weight $M$, while same-layer edges have weight $M-1$, so maximizing the total weight is equivalent to minimizing the number of same-layer edges.↵
↵
A maximum-weight matching contains no extra cycles, so its same-layer edges correspond exactly to the edges of the recovered path. Hence, the recovered path is the shortest even-length simple path.↵
↵
#### Matching and Path Recovery↵
↵
The auxiliary graph has $2n-2$ vertices and at most $2m+n-2$ edges. We therefore use a maximum-weight matching algorithm for general graphs, such as the weighted blossom algorithm, whose time complexity is $O(|V'|^3)$.↵
↵
After finding the matching:↵
↵
1. If its size is not $|V'|/2$, output $-1$.↵
2. Take the symmetric difference between the matching and the set of cross-layer edges of all internal vertices.↵
3. The cross-layer edges of unused vertices cancel, and the remaining auxiliary graph is exactly a path from $L(1)$ to $R(n)$.↵
4. Traverse this path and record the corresponding original vertex whenever a same-layer edge is crossed.↵
↵
This recovers the required shortest even-length simple pathThe main difficulty is the word ``simple''. A shortest path algorithm cannot directly handle the condition that no vertex may be visited twice, so we encode the path as a matching.↵
↵
First, consider the degree pattern of a simple path from vertex $1$ to vertex $n$:↵
↵
* vertices $1$ and $n$ have degree $1$ in the path;↵
* every other used vertex has degree $2$;↵
* every unused vertex has degree $0$.↵
↵
We will build an auxiliary graph where:↵
↵
* an unused vertex corresponds to one internal matching edge;↵
* a used internal vertex must match both of its copies to other vertices;↵
* vertices $1$ and $n$ have only one copy each, so they contribute exactly one path edge.↵
↵
Then a perfect matching in the auxiliary graph will describe a path in the original graph.↵
↵
---↵
↵
Let the original graph be $G=(V,E)$.↵
↵
For every vertex $v$, create two copies $L(v)$ and $R(v)$. Then delete $R(1)$ and $L(n)$. Thus the vertex set of the auxiliary graph $G'=(V',E')$ is↵
↵
$$↵
V'=\{L(v)\mid v\ne n\}\cup\{R(v)\mid v\ne 1\}↵
$$↵
↵
We delete these two copies because vertices $1$ and $n$ should have degree $1$ in the restored path. Every internal vertex still has both copies, so it may contribute degree $2$.↵
↵
Also, the deleted copies are in different layers. This is what forces the restored path to have even length.↵
↵
For every original edge $(u,v)\in E$, add the same-layer edges $(L(u),L(v))$ and $(R(u),R(v))$ whenever both endpoints exist. Give each of these edges weight $M-1$.↵
↵
For every internal vertex $v\notin\{1,n\}$, add the cross-layer edge $(L(v),R(v))$ with weight $M$.↵
↵
Here $M$ is a sufficiently large constant, for example any $M>|V'|$.↵
↵
Now find a maximum-weight matching in the general graph $G'$. If it is not a perfect matching, then there is no valid path. Otherwise, we restore the answer from it.↵
↵
The choice $M>|V'|$ is useful here: if a perfect matching exists, any matching that misses at least one edge loses more weight than it can gain by changing all remaining edges from weight $M-1$ to weight $M$. Therefore a maximum-weight matching will be perfect whenever a perfect matching exists.↵
↵
---↵
↵
## Meaning of a Perfect Matching↵
↵
Consider a perfect matching $S$ of $G'$.↵
↵
For an internal vertex $v\notin\{1,n\}$, both $L(v)$ and $R(v)$ must be matched.↵
↵
If $S$ contains the cross-layer edge $(L(v),R(v))$, we treat $v$ as unused. This corresponds to degree $0$ in the original graph.↵
↵
Otherwise, $L(v)$ and $R(v)$ are each matched to another copy through same-layer edges. After mapping these same-layer edges back to the original graph, vertex $v$ has degree $2$.↵
↵
Vertices $1$ and $n$ have only one copy each and have no cross-layer edge, so they naturally have degree $1$.↵
↵
Thus the selected same-layer edges map to a subgraph of the original graph in which:↵
↵
* vertices $1$ and $n$ have degree $1$;↵
* every other vertex has degree $0$ or $2$.↵
↵
So this subgraph consists of one path from $1$ to $n$ and possibly several cycles.↵
↵
We now prove the construction in both directions and then explain why maximum weight removes the cycles and minimizes the path length.↵
↵
---↵
↵
### Proof 1: Every Even Simple Path Gives a Perfect Matching↵
↵
Suppose we have an even-length simple path↵
↵
$$↵
p_0=1,p_1,p_2,\ldots,p_L=n↵
$$↵
↵
where $2\mid L$.↵
↵
Choose edges along this path alternately:↵
↵
* for the first edge $(p_0,p_1)$, choose $(L(p_0),L(p_1))$;↵
* for the second edge $(p_1,p_2)$, choose $(R(p_1),R(p_2))$;↵
* for the third edge, choose the corresponding left-layer edge;↵
* for the fourth edge, choose the corresponding right-layer edge;↵
* and so on.↵
↵
Since $L$ is even, the last path edge $(p_{L-1},p_L)$ is chosen in the right layer, and $R(n)$ exists.↵
↵
For every internal vertex $v$ not on the path, choose the cross-layer edge $(L(v),R(v))$.↵
↵
Now every vertex of $G'$ is matched exactly once, so we have constructed a perfect matching.↵
↵
---↵
↵
### Proof 2: Every Perfect Matching Gives an Even Simple Path↵
↵
Take any perfect matching of $G'$ and map all selected same-layer edges back to the original graph.↵
↵
As shown above, the resulting subgraph has degree $1$ at vertices $1$ and $n$, and degree $0$ or $2$ at every other vertex. Therefore it is the disjoint union of one path from $1$ to $n$ and some cycles.↵
↵
Let us look at the path component. In the auxiliary graph, the endpoint corresponding to vertex $1$ is $L(1)$, while the endpoint corresponding to vertex $n$ is $R(n)$. Along the restored component, same-layer edges are the original graph edges, and the only way to switch layers is through cross-layer edges of the form $(L(v),R(v))$.↵
↵
Therefore the original edges on the path must appear as↵
↵
$$↵
\text{left layer},\ \text{right layer},\ \text{left layer},\ \text{right layer},\ldots,\ \text{right layer}↵
$$↵
↵
So the number of original edges on this path is even.↵
↵
The path component has exactly two vertices of degree $1$ and all other vertices of degree $2$, so it is a simple path. Hence every perfect matching gives an even-length simple path from $1$ to $n$, possibly together with extra cycles.↵
↵
---↵
↵
### Proof 3: A Maximum-Weight Perfect Matching Has No Extra Cycles↵
↵
Assume that a maximum-weight perfect matching maps back to a path from $1$ to $n$ plus at least one cycle. Let this cycle contain $k$ vertices.↵
↵
Every vertex on the cycle is used, so none of them uses its cross-layer edge. The cycle contributes exactly $k$ same-layer matching edges, with total weight↵
↵
$$↵
k(M-1)↵
$$↵
↵
Now remove this cycle from the matching and, for every vertex $v$ on the cycle, choose the cross-layer edge $(L(v),R(v))$ instead.↵
↵
This is still a valid perfect matching. The affected part now has total weight↵
↵
$$↵
kM↵
$$↵
↵
Since $kM>k(M-1)$, the matching weight increases, which contradicts maximality.↵
↵
Therefore a maximum-weight perfect matching cannot produce extra cycles. It restores exactly one even-length simple path from $1$ to $n$.↵
↵
---↵
↵
### Proof 4: The Restored Path Is Shortest↵
↵
In any perfect matching of $G'$, the number of matched edges is fixed.↵
↵
Cross-layer edges have weight $M$, and same-layer edges have weight $M-1$. Thus maximizing the total weight is the same as minimizing the number of selected same-layer edges.↵
↵
After Proof 3, a maximum-weight perfect matching has no extra cycles, so its selected same-layer edges are exactly the edges of the restored path. Therefore the maximum-weight perfect matching gives a shortest even-length simple path.↵
↵
---↵
↵
## Finding the Matching and Restoring the Path↵
↵
The auxiliary graph is not necessarily bipartite, because both the left layer and the right layer may contain edges. Therefore we need maximum-weight matching in a general graph, for example the weighted blossom algorithm.↵
↵
The auxiliary graph has $2n-2$ vertices and at most $2m+n-2$ edges. The weighted blossom algorithm runs in $O(|V'|^3)$ time.↵
↵
After computing the maximum-weight matching:↵
↵
* if its size is not $|V'|/2$, output $-1$;↵
* otherwise, take the symmetric difference between the matching edges and all cross-layer edges $(L(v),R(v))$ for $v\notin\{1,n\}$.↵
↵
Unused vertices disappear from this symmetric difference, because their cross-layer edge is present in both sets. Used vertices remain connected through their two copies.↵
↵
The resulting auxiliary graph contains one path from $L(1)$ to $R(n)$ and no cycles for a maximum-weight matching. Traverse this path and write down the original vertex whenever a same-layer edge is crossed. This gives the required shortest even-length simple path from vertex $1$ to vertex $n$.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int N = 1000;↵
const int V = 2 * N;↵
const int B = 2 * V;↵
const int inf = 0x3f3f3f3f;↵
const int big = 10000;↵
↵
struct edge {↵
int u, v, w;↵
};↵
↵
int n, m;↵
int idL[N + 10], idR[N + 10], ori[V + 10];↵
int init_u[N + 10], init_v[N + 10], init_cnt;↵
char sx[V + 10][V + 10];↵
vector<int> adj[V + 10];↵
↵
struct blossom_tree {↵
int n, nx;↵
edge g[B + 10][B + 10];↵
int lab[B + 10], match[B + 10], slack[B + 10], st[B + 10], pa[B + 10];↵
int flower_from[B + 10][V + 10], flower[B + 10][V + 10];↵
int S[B + 10], vis[B + 10], flower_cnt[B + 10], tmp[V + 10];↵
queue<int> q;↵
↵
void init(int _n) {↵
n = _n, nx = n;↵
↵
for (int i = 0; i <= 2 * n + 2; ++i) {↵
lab[i] = match[i] = slack[i] = st[i] = pa[i] = S[i] = vis[i] = 0;↵
flower_cnt[i] = 0;↵
for (int j = 0; j <= n; ++j) flower_from[i][j] = 0;↵
}↵
↵
for (int i = 1; i <= 2 * n + 2; ++i) {↵
for (int j = 1; j <= 2 * n + 2; ++j) g[i][j] = {i, j, 0};↵
}↵
}↵
↵
void add_edge(int u, int v, int w) {↵
if (u == v) return;↵
↵
if (w > g[u][v].w) {↵
g[u][v] = {u, v, w};↵
g[v][u] = {v, u, w};↵
}↵
}↵
↵
int e_delta(edge e) {↵
return lab[e.u] + lab[e.v] - g[e.u][e.v].w * 2;↵
}↵
↵
void update_slack(int u, int x) {↵
if (!slack[x] || e_delta(g[u][x]) < e_delta(g[slack[x]][x])) slack[x] = u;↵
}↵
↵
void set_slack(int x) {↵
slack[x] = 0;↵
↵
for (int u = 1; u <= n; ++u) {↵
if (g[u][x].w && st[u] != x && S[st[u]] == 0) update_slack(u, x);↵
}↵
}↵
↵
void q_push(int x) {↵
if (x <= n) q.push(x);↵
else {↵
for (int i = 0; i < flower_cnt[x]; ++i) q_push(flower[x][i]);↵
}↵
}↵
↵
void set_st(int x, int b) {↵
st[x] = b;↵
↵
if (x > n) {↵
for (int i = 0; i < flower_cnt[x]; ++i) set_st(flower[x][i], b);↵
}↵
}↵
↵
void reverse_flower(int b, int l, int r) {↵
while (l < r) {↵
swap(flower[b][l], flower[b][r]);↵
++l, --r;↵
}↵
}↵
↵
void rotate_flower(int b, int pr) {↵
int cnt = flower_cnt[b];↵
↵
for (int i = 0; i < cnt; ++i) tmp[i] = flower[b][(i + pr) % cnt];↵
for (int i = 0; i < cnt; ++i) flower[b][i] = tmp[i];↵
}↵
↵
int get_pr(int b, int xr) {↵
int pr = 0;↵
↵
while (flower[b][pr] != xr) ++pr;↵
↵
if (pr & 1) {↵
reverse_flower(b, 1, flower_cnt[b] - 1);↵
return flower_cnt[b] - pr;↵
}↵
↵
return pr;↵
}↵
↵
void set_match(int u, int v) {↵
match[u] = g[u][v].v;↵
↵
if (u > n) {↵
edge e = g[u][v];↵
int xr = flower_from[u][e.u];↵
int pr = get_pr(u, xr);↵
↵
for (int i = 0; i < pr; ++i) set_match(flower[u][i], flower[u][i ^ 1]);↵
↵
set_match(xr, v);↵
rotate_flower(u, pr);↵
}↵
}↵
↵
void augment(int u, int v) {↵
while (true) {↵
int xnv = st[match[u]];↵
↵
set_match(u, v);↵
↵
if (!xnv) return;↵
↵
set_match(xnv, st[pa[xnv]]);↵
u = st[pa[xnv]], v = xnv;↵
}↵
}↵
↵
int get_lca(int u, int v) {↵
static int tim = 0;↵
++tim;↵
↵
while (u || v) {↵
if (u) {↵
if (vis[u] == tim) return u;↵
↵
vis[u] = tim;↵
u = st[match[u]];↵
↵
if (u) u = st[pa[u]];↵
}↵
↵
swap(u, v);↵
}↵
↵
return 0;↵
}↵
↵
void add_blossom(int u, int lca, int v) {↵
int b = n + 1;↵
↵
while (b <= nx && st[b]) ++b;↵
if (b > nx) ++nx;↵
↵
lab[b] = 0, S[b] = 0, match[b] = match[lca];↵
flower_cnt[b] = 0;↵
flower[b][flower_cnt[b]++] = lca;↵
↵
for (int x = u, y; x != lca; x = st[pa[y]]) {↵
flower[b][flower_cnt[b]++] = x;↵
y = st[match[x]];↵
flower[b][flower_cnt[b]++] = y;↵
q_push(y);↵
}↵
↵
reverse_flower(b, 1, flower_cnt[b] - 1);↵
↵
for (int x = v, y; x != lca; x = st[pa[y]]) {↵
flower[b][flower_cnt[b]++] = x;↵
y = st[match[x]];↵
flower[b][flower_cnt[b]++] = y;↵
q_push(y);↵
}↵
↵
set_st(b, b);↵
↵
for (int x = 1; x <= nx; ++x) {↵
g[b][x] = {b, x, 0};↵
g[x][b] = {x, b, 0};↵
}↵
↵
for (int x = 1; x <= n; ++x) flower_from[b][x] = 0;↵
↵
for (int i = 0; i < flower_cnt[b]; ++i) {↵
int xs = flower[b][i];↵
↵
for (int x = 1; x <= nx; ++x) {↵
if (g[xs][x].w && (!g[b][x].w || e_delta(g[xs][x]) < e_delta(g[b][x]))) {↵
g[b][x] = g[xs][x];↵
g[x][b] = g[x][xs];↵
}↵
}↵
↵
for (int x = 1; x <= n; ++x) {↵
if (flower_from[xs][x]) flower_from[b][x] = xs;↵
}↵
}↵
↵
set_slack(b);↵
}↵
↵
void expand_blossom(int b) {↵
for (int i = 0; i < flower_cnt[b]; ++i) set_st(flower[b][i], flower[b][i]);↵
↵
int xr = flower_from[b][g[b][pa[b]].u];↵
int pr = get_pr(b, xr);↵
↵
for (int i = 0; i < pr; i += 2) {↵
int xs = flower[b][i];↵
int xns = flower[b][i + 1];↵
↵
pa[xs] = g[xns][xs].u;↵
S[xs] = 1, S[xns] = 0;↵
slack[xs] = 0;↵
↵
set_slack(xns);↵
q_push(xns);↵
}↵
↵
S[xr] = 1;↵
pa[xr] = pa[b];↵
↵
for (int i = pr + 1; i < flower_cnt[b]; ++i) {↵
int xs = flower[b][i];↵
↵
S[xs] = -1;↵
set_slack(xs);↵
}↵
↵
st[b] = 0;↵
}↵
↵
bool on_found_edge(edge e) {↵
int u = st[e.u], v = st[e.v];↵
↵
if (S[v] == -1) {↵
pa[v] = e.u;↵
S[v] = 1;↵
↵
int nu = st[match[v]];↵
↵
slack[v] = slack[nu] = 0;↵
S[nu] = 0;↵
↵
q_push(nu);↵
}↵
else if (S[v] == 0) {↵
int lca = get_lca(u, v);↵
↵
if (!lca) {↵
augment(u, v);↵
augment(v, u);↵
return true;↵
}↵
else add_blossom(u, lca, v);↵
}↵
↵
return false;↵
}↵
↵
bool matching() {↵
for (int i = 1; i <= nx; ++i) S[i] = -1, slack[i] = 0;↵
↵
while (!q.empty()) q.pop();↵
↵
for (int x = 1; x <= nx; ++x) {↵
if (st[x] == x && !match[x]) {↵
pa[x] = 0;↵
S[x] = 0;↵
q_push(x);↵
}↵
}↵
↵
if (q.empty()) return false;↵
↵
while (true) {↵
while (!q.empty()) {↵
int u = q.front(); q.pop();↵
if (S[st[u]] == 1) continue;↵
↵
for (int v = 1; v <= n; ++v) {↵
if (g[u][v].w && st[u] != st[v]) {↵
if (!e_delta(g[u][v])) {↵
if (on_found_edge(g[u][v])) return true;↵
}↵
else update_slack(u, st[v]);↵
}↵
}↵
}↵
↵
int d = inf;↵
↵
for (int u = 1; u <= n; ++u) {↵
if (S[st[u]] == 0) d = min(d, lab[u]);↵
}↵
↵
for (int b = n + 1; b <= nx; ++b) {↵
if (st[b] == b && S[b] == 1) d = min(d, lab[b] / 2);↵
}↵
↵
for (int x = 1; x <= nx; ++x) {↵
if (st[x] == x && slack[x]) {↵
if (S[x] == -1) d = min(d, e_delta(g[slack[x]][x]));↵
else if (S[x] == 0) d = min(d, e_delta(g[slack[x]][x]) / 2);↵
}↵
}↵
↵
if (d == inf) return false;↵
↵
for (int u = 1; u <= n; ++u) {↵
if (S[st[u]] == 0) {↵
if (lab[u] == d) return false;↵
lab[u] -= d;↵
}↵
else if (S[st[u]] == 1) lab[u] += d;↵
}↵
↵
for (int b = n + 1; b <= nx; ++b) {↵
if (st[b] == b) {↵
if (S[b] == 0) lab[b] += d * 2;↵
else if (S[b] == 1) lab[b] -= d * 2;↵
}↵
}↵
↵
while (!q.empty()) q.pop();↵
↵
for (int x = 1; x <= nx; ++x) {↵
if (st[x] == x && slack[x] && st[slack[x]] != x && !e_delta(g[slack[x]][x])) {↵
if (on_found_edge(g[slack[x]][x])) return true;↵
}↵
}↵
↵
for (int b = n + 1; b <= nx; ++b) {↵
if (st[b] == b && S[b] == 1 && !lab[b]) expand_blossom(b);↵
}↵
}↵
}↵
↵
int solve() {↵
nx = n;↵
int cnt = 0, mx = 0;↵
↵
for (int i = 0; i <= 2 * n + 2; ++i) {↵
lab[i] = match[i] = slack[i] = pa[i] = S[i] = vis[i] = 0;↵
st[i] = 0;↵
flower_cnt[i] = 0;↵
}↵
↵
for (int i = 0; i <= n; ++i) st[i] = i;↵
↵
for (int u = 1; u <= n; ++u) {↵
for (int v = 1; v <= n; ++v) {↵
flower_from[u][v] = (u == v ? u : 0);↵
mx = max(mx, g[u][v].w);↵
}↵
}↵
↵
for (int u = 1; u <= n; ++u) lab[u] = mx;↵
↵
while (matching()) ++cnt;↵
return cnt;↵
}↵
} blossom;↵
↵
int new_node(int x, int &tot) {↵
ori[tot + 1] = x;↵
return ++tot;↵
}↵
↵
void toggle_edge(int u, int v) {↵
if (u > v) swap(u, v);↵
sx[u][v] ^= 1;↵
}↵
↵
void work() {↵
cin >> n >> m;↵
↵
memset(idL, -1, sizeof(idL));↵
memset(idR, -1, sizeof(idR));↵
↵
int tot = 0;↵
↵
for (int i = 1; i <= n; ++i) {↵
if (i != n) idL[i] = new_node(i, tot);↵
}↵
for (int i = 1; i <= n; ++i) {↵
if (i != 1) idR[i] = new_node(i, tot);↵
}↵
↵
blossom.init(tot);↵
↵
for (int i = 1; i <= m; ++i) {↵
int u, v; cin >> u >> v;↵
↵
if (idL[u] != -1 && idL[v] != -1) blossom.add_edge(idL[u], idL[v], big - 1);↵
if (idR[u] != -1 && idR[v] != -1) blossom.add_edge(idR[u], idR[v], big - 1);↵
}↵
↵
init_cnt = 0;↵
↵
for (int i = 2; i < n; ++i) {↵
blossom.add_edge(idL[i], idR[i], big);↵
init_u[++init_cnt] = idL[i], init_v[init_cnt] = idR[i];↵
}↵
↵
int cnt = blossom.solve();↵
↵
if (cnt != tot / 2) {↵
cout << -1 << '\n';↵
return;↵
}↵
↵
for (int i = 1; i <= tot; ++i) {↵
adj[i].clear();↵
for (int j = 1; j <= tot; ++j) sx[i][j] = 0;↵
}↵
↵
for (int i = 1; i <= tot; ++i) {↵
if (blossom.match[i] && i < blossom.match[i]) toggle_edge(i, blossom.match[i]);↵
}↵
↵
for (int i = 1; i <= init_cnt; ++i) toggle_edge(init_u[i], init_v[i]);↵
↵
for (int i = 1; i <= tot; ++i) {↵
for (int j = i + 1; j <= tot; ++j) {↵
if (sx[i][j]) {↵
adj[i].push_back(j);↵
adj[j].push_back(i);↵
}↵
}↵
}↵
↵
int st = idL[1], ed = idR[n];↵
vector<int> aux, path;↵
int last = 0, cur = st;↵
↵
while (true) {↵
aux.push_back(cur);↵
if (cur == ed) break;↵
↵
int nxt = 0;↵
↵
for (int v : adj[cur]) {↵
if (v != last) {↵
nxt = v;↵
break;↵
}↵
}↵
↵
if (!nxt) {↵
cout << -1 << '\n';↵
return;↵
}↵
↵
last = cur, cur = nxt;↵
↵
if ((int)aux.size() > tot + 5) {↵
cout << -1 << '\n';↵
return;↵
}↵
}↵
↵
path.push_back(1);↵
for (int i = 1; i < (int)aux.size(); ++i) {↵
int u = aux[i - 1], v = aux[i];↵
if (ori[u] != ori[v]) path.push_back(ori[v]);↵
}↵
↵
if (path.back() != n || ((int)path.size() - 1) % 2) {↵
cout << -1 << '\n';↵
return;↵
}↵
↵
cout << (int)path.size() - 1 << '\n';↵
for (int i = 0; i < (int)path.size(); ++i) {↵
if (i) cout << ' ';↵
cout << path[i];↵
}↵
cout << '\n';↵
}↵
↵
int main() {↵
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
↵
int T; cin >> T;↵
while (T--) work();↵
↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
↵
- Idea:[user:aaa_Pigeon2,2026-07-26]↵
↵
- Solution:[user:aaa_Pigeon2,2026-07-26]↵
↵
<spoiler summary="Solution">↵
Let us determine what is required for every position to contain exactly one element after the simultaneous move.↵
↵
The element initially at position $1$ cannot move to the left, so it must move to the right. Therefore, $w_1>k$. Once it leaves, only the element initially at position $2$ can fill position $1$, so $w_2<k$.↵
↵
Thus, the elements at positions $1$ and $2$ must swap. Repeating the same argument for the remaining positions, the only possible movement pattern is↵
↵
$$↵
1\leftrightarrow 2,\quad 3\leftrightarrow 4,\quad 5\leftrightarrow 6,\ldots↵
$$↵
↵
Consequently, $n$ must be even, every element at an odd position must move to the right, and every element at an even position must move to the left.↵
↵
Let↵
↵
$$↵
L=\max_{i\bmod 2=0}w_i,\qquad R=\min_{i\bmod 2=1}w_i.↵
$$↵
↵
We need an integer $k$ such that $L<k<R$. Such an integer exists if and only if $L+2\le R$.↵
↵
The time complexity is $O(n)$ per test case, and the extra space complexity is $O(1)$.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void work() {↵
int n; cin >> n;↵
long long L = 0, R = 1000000001LL;↵
↵
for (int i = 1; i <= n; ++i) {↵
long long w; cin >> w;↵
if (i & 1) R = min(R, w);↵
else L = max(L, w);↵
}↵
↵
cout << (n % 2 == 0 && L + 2 <= R ? "YES" : "NO") << '\n';↵
}↵
↵
int main() {↵
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
↵
int T; cin >> T;↵
while (T--) work();↵
↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
## [problem:2250B]↵
↵
- Idea:[user:_MCYYDS_,2026-07-26]↵
↵
- Solution:[user:_MCYYDS_,2026-07-26]↵
↵
<spoiler summary="Hint 1">↵
Partition the string into maximal blocks of equal characters. How does the number of blocks determine the number of adjacent equal pairs?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Define a block as a maximal consecutive segment of equal characters. Suppose the string has $r$ blocks with lengths $l_1,l_2,\ldots,l_r$. A block of length $l_i$ contributes exactly $l_i-1$ adjacent equal pairs, so the total number is↵
↵
$$↵
\sum_{i=1}^{r}(l_i-1)=n-r.↵
$$↵
↵
Therefore, we need to construct a string with exactly $r=n-k$ blocks.↵
↵
Because $k<n$, we have $r\ge1$. Since $n\ge2$ and the counts of $\mathtt{0}$ and $\mathtt{1}$ may differ by at most $1$, both characters must appear, so the string must contain at least two blocks. Hence, when $r=1$, or equivalently $k=n-1$, no solution exists.↵
↵
Now assume $r\ge2$. Let the block characters alternate, starting with $\mathtt{0}$. The numbers of $\mathtt{0}$-blocks and $\mathtt{1}$-blocks are↵
↵
$$↵
r_0=\left\lceil\frac r2\right\rceil,\qquad r_1=\left\lfloor\frac r2\right\rfloor.↵
$$↵
↵
We want the total numbers of the two characters to be↵
↵
$$↵
c_0=\left\lceil\frac n2\right\rceil,\qquad c_1=\left\lfloor\frac n2\right\rfloor.↵
$$↵
↵
First assign one character to each block. This uses $r_0$ zeros and $r_1$ ones. Since $r\le n$, we have $r_0\le c_0$ and $r_1\le c_1$.↵
↵
Append all remaining zeros to any $\mathtt{0}$-block and all remaining ones to any $\mathtt{1}$-block, then concatenate the blocks in order. The two character counts differ by at most $1$, and the string has exactly $r$ blocks, so it contains exactly $n-r=k$ adjacent equal pairs.↵
↵
The time complexity is $O(n)$ per test case and $O(\sum n)$ in total. The space complexity is $O(n)$.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void work() {↵
int n, k; cin >> n >> k;↵
↵
if (n > 1 && k == n - 1) {↵
cout << -1 << '\n';↵
return;↵
}↵
cout << "01110\n";↵
return;↵
}↵
if (n == 6 && k == 1) {↵
cout << "101001\n";↵
return;↵
}↵
k = n - k;↵
int c0 = (n + 1) / 2, c1 = n / 2;↵
↵
for (int i = 1; i <= k; ++i) {↵
if (i & 1) {↵
if (i + 2 > k) {↵
while (c0--) cout << 0;↵
}↵
else {↵
--c0;↵
cout << 0;↵
}↵
}↵
else {↵
if (i + 2 > k) {↵
while (c1--) cout << 1;↵
}↵
else {↵
--c1;↵
cout << 1;↵
}↵
}↵
}↵
cout << '\n';↵
}↵
↵
int main() {↵
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
↵
int T; cin >> T;↵
while (T--) work();↵
↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
## [problem:2249A]↵
↵
- Idea:[user:aaa_Pigeon2,2026-07-26]↵
↵
- Solution:[user:aaa_Pigeon2,2026-07-26]↵
↵
<spoiler summary="Hint 1">↵
An element's rank from the right depends on both its position in the retained subsequence and the subsequence's final length.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Enumerate the final retained length $m$. Once $m$ is fixed, the condition for every position in the subsequence is fixed.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Whether an element can occupy the $j$-th position of the retained subsequence depends on the final length $m$, because its rank from the right is $m-j+1$.↵
↵
Therefore, we enumerate the final length $m$.↵
↵
For a fixed $m$, scan the original sequence from left to right and fill positions $1,2,\ldots,m$ of the subsequence in order. When filling position $j$, element $i$ can be chosen if and only if↵
↵
$$↵
j\notin[l_i,r_i]↵
$$↵
↵
and↵
↵
$$↵
m-j+1\notin[u_i,v_i].↵
$$↵
↵
Whenever the current element satisfies both conditions, choose it immediately.↵
↵
To prove this greedy choice, suppose a feasible solution chooses an element $x$ for position $j$, while the greedy algorithm chooses an earlier valid element $y$. Replacing $x$ with $y$ leaves every later element of the original solution available and does not reduce the remaining suffix in which subsequent choices must be made. Thus, whenever a feasible solution exists, the greedy algorithm also succeeds.↵
↵
Enumerate $m$ from $n$ down to $1$. The first feasible value is the maximum possible answer. If no positive value is feasible, the answer is $0$.↵
↵
The time complexity is $O(n^2)$ per test case, and the space complexity is $O(n)$.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int N = 5000;↵
↵
int n;↵
int l[N + 10], r[N + 10], u[N + 10], v[N + 10];↵
↵
bool check(int m) {↵
int j = 1;↵
↵
for (int i = 1; i <= n && j <= m; ++i) {↵
int x = m - j + 1;↵
if ((j < l[i] || j > r[i]) && (x < u[i] || x > v[i])) ++j;↵
}↵
↵
return j == m + 1;↵
}↵
↵
void work() {↵
cin >> n;↵
for (int i = 1; i <= n; ++i) cin >> l[i] >> r[i] >> u[i] >> v[i];↵
↵
for (int m = n; m >= 1; --m) {↵
if (!check(m)) continue;↵
cout << m << '\n';↵
return;↵
}↵
↵
cout << 0 << '\n';↵
}↵
↵
int main() {↵
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
↵
int T; cin >> T;↵
while (T--) work();↵
↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
## [problem:2249B]↵
↵
- Idea:[user:aaa_Pigeon2,2026-07-26]↵
↵
- Solution:[user:aaa_Pigeon2,2026-07-26]↵
↵
<spoiler summary="Hint 1">↵
The value $n$ lies on exactly one side of every cut. Therefore, the value of the cut must be the maximum on the opposite side.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Enumerate the dividing point determined by the position of $n$. The cut values to its left must be non-decreasing, while those to its right must be non-increasing.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Merge the left sequence with the reversed right sequence. The first occurrence of a value forces its position, while every later occurrence contributes a number of choices.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
First observe that no cut value can equal $n$. The value $n$ lies on exactly one side of a cut, while the maximum on the opposite side is at most $n-1$. Therefore, if some $a_i=n$, the answer is $0$.↵
↵
Now consider the position of $n$. For cut $i$:↵
↵
- If $n$ lies on the right, then $a_i$ is the maximum of the prefix on the left.↵
- If $n$ lies on the left, then $a_i$ is the maximum of the suffix on the right.↵
↵
Hence, there must be a dividing point $c$ such that $a_1,\ldots,a_c$ is non-decreasing and $a_{c+1},\ldots,a_{n-1}$ is non-increasing. If both parts are non-empty, we must also have $a_c\ne a_{c+1}$. These two maxima are attained at positions on opposite sides of the dividing point, and a permutation cannot contain the same value at both positions.↵
↵
We enumerate all values of $c$ satisfying these conditions. There may seem to be many candidates, but the indices belonging to both the non-decreasing prefix and the non-increasing suffix can only form a segment of equal values. Two adjacent equal values cannot form an internal boundary, so only a constant number of candidates need to be considered.↵
↵
After fixing $c$, merge↵
↵
$$↵
a_1,a_2,\ldots,a_c↵
$$↵
↵
with the reversed right part↵
↵
$$↵
a_{n-1},a_{n-2},\ldots,a_{c+1}↵
$$↵
↵
to obtain one non-decreasing sequence. Process its $i$-th value $x$:↵
↵
- If this is the first occurrence of $x$, then the maximum on that side must become $x$ at this position, so the assigned permutation value is forced to be $x$.↵
- Otherwise, we may assign any unused value smaller than $x$. Since $i-1$ values have already been used, there are $x-i+1$ choices.↵
↵
For each repeated occurrence, multiply the answer by $x-i+1$. This gives the number of permutations corresponding to the fixed dividing point. Finally, sum these values over all valid dividing points.↵
↵
Each merge takes $O(n)$ time. Since only a constant number of dividing points are valid, the time complexity is $O(n)$ per test case, and the space complexity is $O(n)$.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int N = 1000000;↵
const int mod = 998244353;↵
↵
int n;↵
int a[N + 10], vis[N + 10];↵
bool pre[N + 10], suf[N + 10];↵
↵
void work() {↵
cin >> n;↵
for (int i = 1; i < n; ++i) cin >> a[i];↵
a[n] = 0;↵
↵
for (int i = 1; i < n; ++i) {↵
if (a[i] != n) continue;↵
cout << 0 << '\n';↵
return;↵
}↵
↵
pre[0] = 1;↵
for (int i = 1; i < n; ++i) pre[i] = pre[i - 1] && a[i] >= a[i - 1];↵
suf[n] = 1;↵
for (int i = n - 1; i >= 1; --i) suf[i] = suf[i + 1] && a[i] >= a[i + 1];↵
↵
long long ans = 0;↵
for (int cut = 0; cut < n; ++cut) {↵
if (!pre[cut] || !suf[cut + 1]) continue;↵
↵
vector<int> l, r;↵
if (!l.empty() && !r.empty() && l.back() == r.front()) continue;↵
↵
memset(vis, 0, sizeof(int) * (n + 1));↵
int x = 0, y = 0, used = 0;↵
long long ways = 1;↵
↵
while (x < (int)l.size() || y < (int)r.size()) {↵
int w;↵
if (x == (int)l.size()) w = r[y++];↵
else if (y == (int)r.size()) w = l[x++];↵
else if (l[x] < r[y]) w = l[x++];↵
else if (l[x] > r[y]) w = r[y++];↵
else {↵
cout << 0 << '\n';↵
return;↵
}↵
↵
if (!vis[w]) vis[w] = 1;↵
else if (w < used) ways = 0;↵
else ways = ways * (w - used) % mod;↵
++used;↵
}↵
↵
ans += ways;↵
}↵
↵
cout << ans % mod << '\n';↵
}↵
↵
int main() {↵
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
↵
int T; cin >> T;↵
while (T--) work();↵
↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
## [problem:2249C]↵
↵
- Idea:[user:aaa_Pigeon2,2026-07-26]↵
↵
- Solution:[user:aaa_Pigeon2,2026-07-26]↵
↵
<spoiler summary="Hint 1">↵
Duplicate the permutation so that the cyclic sequence starting at any position becomes an ordinary contiguous segment of the duplicated array.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
After inserting a new value $x$, the change in the number of consecutive-value blocks depends only on whether $x-1$ and $x+1$ have already appeared.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Maintain the number of blocks for all starting positions simultaneously. Once a starting position has produced more than two blocks, it can be discarded permanently.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Checking every prefix separately for every starting position would introduce an additional factor of $n$. Instead, duplicate the permutation and define↵
↵
$$↵
q_i=p_{((i-1)\bmod n)+1}.↵
$$↵
↵
For a starting position $l$, the successive cyclic prefixes become the ordinary segments $[l,l],[l,l+1],\ldots,[l,l+n-1]$.↵
↵
Enumerate the right endpoint $r$ from left to right. When $q_r$ is inserted, the starting positions whose current segment ends at $r$ form the interval↵
↵
$$↵
L=\max(1,r-n+1),\qquad R=\min(r,n).↵
$$↵
↵
Let the new value be $x$. Because the current segment has length at most $n$, no permutation value appears twice. The change in the number of consecutive-value blocks is↵
↵
$$↵
\Delta=1-[x-1\text{ has already appeared}]-[x+1\text{ has already appeared}].↵
$$↵
↵
We first regard $x$ as a new block, then merge it with the block on either side whenever the corresponding neighboring value has already appeared.↵
↵
To update all starting positions simultaneously, let $\operatorname{last}_v$ be the latest position before $r$ at which value $v$ appeared. For a starting position $l$, value $v$ appears in $[l,r-1]$ if and only if $\operatorname{last}_v\ge l$.↵
↵
Therefore, inserting $x$ requires only three range additions:↵
↵
1. Add $1$ to $[L,R]$.↵
2. If $x-1$ exists, subtract $1$ from $[L,\min(R,\operatorname{last}_{x-1})]$.↵
3. If $x+1$ exists, subtract $1$ from $[L,\min(R,\operatorname{last}_{x+1})]$.↵
↵
Use a lazy segment tree to maintain the current number of blocks for every starting position, with range addition and a global maximum query. Once a starting position has more than two blocks, it has already produced an invalid prefix. A later decrease cannot erase that earlier invalid prefix, so the starting position can be removed permanently.↵
↵
Each starting position is removed at most once. We process $2n-1$ right endpoints, performing only a constant number of range operations for each one. Thus, the time complexity is $O(n\log n)$, and the space complexity is $O(n)$.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int N = 200000;↵
const int inf = 1000000000;↵
↵
int n;↵
int p[N + 10], last[N + 10];↵
int mx[4 * N + 10], lazy[4 * N + 10];↵
↵
void apply(int u, int v) {↵
mx[u] += v;↵
lazy[u] += v;↵
}↵
↵
void push(int u) {↵
if (!lazy[u]) return;↵
apply(u << 1, lazy[u]);↵
apply(u << 1 | 1, lazy[u]);↵
lazy[u] = 0;↵
}↵
↵
void add(int u, int l, int r, int ql, int qr, int v) {↵
if (ql <= l && r <= qr) {↵
apply(u, v);↵
return;↵
}↵
↵
push(u);↵
int mid = (l + r) >> 1;↵
if (ql <= mid) add(u << 1, l, mid, ql, qr, v);↵
if (qr > mid) add(u << 1 | 1, mid + 1, r, ql, qr, v);↵
mx[u] = max(mx[u << 1], mx[u << 1 | 1]);↵
}↵
↵
void add(int l, int r, int v) {↵
if (l <= r) add(1, 1, n, l, r, v);↵
}↵
↵
int find_bad(int u, int l, int r) {↵
if (l == r) return l;↵
↵
push(u);↵
int mid = (l + r) >> 1;↵
if (mx[u << 1] > 2) return find_bad(u << 1, l, mid);↵
return find_bad(u << 1 | 1, mid + 1, r);↵
}↵
↵
void del(int u, int l, int r, int x) {↵
if (l == r) {↵
mx[u] = -inf;↵
lazy[u] = 0;↵
return;↵
}↵
↵
push(u);↵
int mid = (l + r) >> 1;↵
if (x <= mid) del(u << 1, l, mid, x);↵
else del(u << 1 | 1, mid + 1, r, x);↵
mx[u] = max(mx[u << 1], mx[u << 1 | 1]);↵
}↵
↵
void work() {↵
cin >> n;↵
for (int i = 1; i <= n; ++i) cin >> p[i];↵
↵
memset(last, 0, sizeof(int) * (n + 2));↵
memset(mx, 0, sizeof(int) * (4 * n + 5));↵
memset(lazy, 0, sizeof(int) * (4 * n + 5));↵
↵
int ans = n;↵
for (int r = 1; r < 2 * n; ++r) {↵
int L = max(1, r - n + 1), R = min(r, n);↵
int x = p[(r - 1) % n + 1];↵
↵
add(L, R, 1);↵
if (x > 1 && last[x - 1] >= L) add(L, min(R, last[x - 1]), -1);↵
if (x < n && last[x + 1] >= L) add(L, min(R, last[x + 1]), -1);↵
last[x] = r;↵
↵
while (mx[1] > 2) {↵
int x = find_bad(1, 1, n);↵
del(1, 1, n, x);↵
--ans;↵
}↵
}↵
↵
cout << ans << '\n';↵
}↵
↵
int main() {↵
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
↵
int T; cin >> T;↵
while (T--) work();↵
↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
## [problem:2249D]↵
↵
- Idea:[user:aaa_Pigeon2,2026-07-26]↵
↵
- Solution:[user:aaa_Pigeon2,2026-07-26]↵
↵
<spoiler summary="Hint 1">↵
Compare two adjacent rows. For a fixed pair of rows, the $2\times2$ condition forces the XOR difference between corresponding entries to alternate with the parity of the column.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
We need many values $h$ satisfying↵
↵
$$↵
\{0,1,\ldots,n-1\}\mathbin{\operatorname{xor}}h=\{0,1,\ldots,n-1\}.↵
$$↵
↵
How large is the XOR stabilizer of this set?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
When $n$ is a power of two, pair the values as $y\leftrightarrow y\oplus x$, and place several complete pairs at odd positions.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
We first determine when a solution can exist. Let $S=\{0,1,\ldots,n-1\}$, and define the XOR difference between adjacent rows in column $j$ by↵
↵
$$↵
d_i(j)=A_{i,j}\oplus A_{i+1,j}.↵
$$↵
↵
The condition on every adjacent $2\times2$ submatrix implies↵
↵
$$↵
d_i(j+1)=d_i(j)\oplus x.↵
$$↵
↵
Thus, once the parity of the column is fixed, the XOR difference between the two rows is fixed. At least $\lceil n/2\rceil$ rows have the same parity, and every column must be a permutation. Therefore, we need at least $\lceil n/2\rceil$ distinct values $h$ such that $S\oplus h=S$.↵
↵
Let $L=\operatorname{lowbit}(n)$. The XOR stabilizer of $S$ is exactly↵
↵
$$↵
\{0,1,\ldots,L-1\}.↵
$$↵
↵
Every value smaller than $L$ merely permutes elements within blocks of length $L$. Conversely, write $h=gL+r$, where $0\le r<L$. If $g\ne0$, XOR by $h$ induces a nontrivial pairing of the block indices. Since the number of blocks, $n/L$, is odd, the whole set of block indices cannot remain invariant. Hence, $g=0$.↵
↵
The necessary condition is therefore↵
↵
$$↵
\operatorname{lowbit}(n)\ge\left\lceil\frac n2\right\rceil.↵
$$↵
↵
This holds only when $n$ is a power of two. In addition, when $n=2$, each value appears twice in any $2\times2$ Latin square, so the XOR of all four entries is always $0$. Thus, no solution exists for $n=2$ and $x>0$.↵
↵
We now describe the construction.↵
↵
If $x=0$, set↵
↵
$$↵
A_{i,j}=i\oplus j.↵
$$↵
↵
Because $n$ is a power of two, XOR with a fixed value permutes $S$, so every row and every column is a permutation. In each adjacent $2\times2$ submatrix, every index term appears twice, and the total XOR is $0$.↵
↵
Now assume $x>0$, $n$ is a power of two, and $n\ge4$. The map $y\mapsto y\oplus x$ partitions $S$ into $n/2$ pairs. Choose $n/4$ of these pairs to form a set $O$, and let the remaining values form a set $E$. Then↵
↵
$$↵
|E|=|O|=\frac n2,\qquad E\oplus x=E,\qquad O\oplus x=O.↵
$$↵
↵
Construct a permutation $p$ by placing the elements of $E$ at even positions and the elements of $O$ at odd positions. Then define↵
↵
$$↵
A_{i,j}=p_i\oplus p_j\oplus\bigl((i\bmod2)(j\bmod2)x\bigr).↵
$$↵
↵
Every even-indexed row is a fixed XOR translation of $p$. In an odd-indexed row, the even columns contain $p_i\oplus E$, while the odd columns contain $p_i\oplus(O\oplus x)=p_i\oplus O$. Together, they still form $S$. The formula is symmetric in $i$ and $j$, so the same argument applies to every column.↵
↵
Finally, consider any adjacent $2\times2$ submatrix. The four terms involving $p$ cancel in pairs. Among the four parity pairs, exactly one is $(1,1)$, so the remaining XOR is exactly $x$.↵
↵
The output contains $n^2$ numbers, so the time complexity is $O(n^2)$, and the extra space complexity is $O(n)$.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int N = 2500;↵
↵
int n, x;↵
int vis[N + 10], in_o[N + 10], e[N + 10], o[N + 10], a[N + 10];↵
pair<int, int> p[N + 10];↵
↵
bool check(int v) {↵
return (v & (v - 1)) == 0;↵
}↵
↵
void work() {↵
cin >> n >> x;↵
↵
if (!check(n) || (x && n < 4)) {↵
cout << -1 << '\n';↵
return;↵
}↵
↵
if (!x) {↵
for (int i = 0; i < n; ++i) {↵
for (int j = 0; j < n; ++j) {↵
cout << (i ^ j) << (j + 1 == n ? '\n' : ' ');↵
}↵
}↵
return;↵
}↵
↵
for (int i = 0; i <= n; ++i) vis[i] = in_o[i] = e[i] = o[i] = a[i] = 0;↵
↵
int cnt = 0;↵
for (int i = 0; i < n; ++i) {↵
if (vis[i]) continue;↵
int j = i ^ x;↵
vis[i] = vis[j] = 1;↵
p[++cnt] = {i, j};↵
}↵
↵
for (int i = 1; i <= n / 4; ++i) in_o[p[i].first] = in_o[p[i].second] = 1;↵
↵
int ec = 0, oc = 0;↵
for (int i = 0; i < n; ++i) {↵
if (in_o[i]) o[++oc] = i;↵
else e[++ec] = i;↵
}↵
↵
ec = oc = 0;↵
for (int i = 0; i < n; ++i) {↵
if (i & 1) a[i] = o[++oc];↵
else a[i] = e[++ec];↵
}↵
↵
for (int i = 0; i < n; ++i) {↵
for (int j = 0; j < n; ++j) {↵
int v = a[i] ^ a[j];↵
if ((i & 1) && (j & 1)) v ^= x;↵
cout << v << (j + 1 == n ? '\n' : ' ');↵
}↵
}↵
}↵
↵
int main() {↵
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
↵
int T; cin >> T;↵
while (T--) work();↵
↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
## [problem:2249E1]↵
↵
- Idea:[user:131241,2026-07-26]↵
↵
- Solution:[user:131241,2026-07-26]↵
↵
<spoiler summary="Hint 1">↵
Treat a prefix of length $k^i$ as one block. How can it be decomposed into smaller blocks?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Adding the same value to every character modulo $k$ produces only finitely many translated versions of the pattern-matching problem.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
For each block, store its internal occurrence count and its prefix and suffix of length at most $n-1$. When two blocks are merged, only occurrences crossing their boundary need additional processing.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Consider the self-similar structure of the infinite string. Let $B_{i,j}$ denote the standard block of length $k^i$ whose characters are all shifted by $j$ modulo $k$. Then↵
↵
$$↵
B_{i,j}=B_{i-1,j}B_{i-1,j+1}\cdots B_{i-1,j+k-1},↵
$$↵
↵
where all second indices are taken modulo $k$. This follows directly from how the base-$k$ digit sum changes when the highest digit is increased.↵
↵
For the current pattern $t$, maintain the following information for every block:↵
↵
- The number of occurrences of $t$ entirely inside the block.↵
- A prefix of the block of length at most $n-1$.↵
- A suffix of the block of length at most $n-1$.↵
↵
When two adjacent blocks are concatenated, their internal occurrence counts are added. Every newly created occurrence must cross the boundary, so it is sufficient to run KMP on the suffix of the left block followed by the prefix of the right block. The new prefix and suffix are again truncated to at most $n-1$ characters.↵
↵
Storing these boundary strings explicitly at every level would still be too slow. Let $x$ be the smallest integer such that $n\le k^x$. Once the block length reaches this scale, every boundary string is a uniform translation of the boundary of a standard block. Therefore, the contribution across the boundary of two large blocks depends only on their two translation values. There are only $k^2$ such pairs, so all of them can be precomputed.↵
↵
For a query interval $[l,r]$, recursively decompose it in base $k$ into $O(k\log_k V)$ standard blocks and concatenate them in order. The internal occurrence count of each block is obtained from preprocessing, while occurrences crossing block boundaries are counted using either the stored short boundaries or the precomputed translation transitions.↵
↵
At levels where the block length is smaller than $n$, the pattern cannot occur entirely inside a block. The first critical level can be processed directly; at all larger levels, only the finite set of translation transitions is needed. The total time complexity is↵
↵
$$↵
O\left(\sum n\cdot k^2+qk^2\log_k V\right),↵
$$↵
↵
where $V=10^{17}$. The space complexity is $O(n+k^2\log_k V)$.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
struct node {↵
long long v = 0;↵
bool b = 0;↵
string l = "", r = "";↵
int l1, r1;↵
};↵
↵
int n, k;↵
int fai[2000005];↵
long long T, ql, qr, trans[10][10];↵
long long ma, L, R;↵
node a[66][10], ans;↵
string pl[10], pr[10], s;↵
↵
void make_fai() {↵
for (int i = 1; i <= n; ++i) s[i] ^= 48;↵
↵
int l = 0;↵
for (int i = 2; i <= n; ++i) {↵
while (l && s[l + 1] != s[i]) l = fai[l];↵
l += s[l + 1] == s[i];↵
fai[i] = l;↵
}↵
}↵
↵
int val(string x) {↵
int l = 0, res = 0;↵
↵
for (int i = 0; i < (int)x.size(); ++i) {↵
while (l && s[l + 1] != x[i]) l = fai[l];↵
l += s[l + 1] == x[i];↵
if (l == n) ++res;↵
}↵
↵
return res;↵
}↵
↵
node add(node &x, node &y) {↵
node res;↵
↵
if (x.b && y.b) {↵
res.b = 1;↵
res.l1 = x.l1;↵
res.r1 = y.r1;↵
res.v = x.v + y.v + trans[x.r1][y.l1];↵
return res;↵
}↵
↵
if (x.b) x.l = pl[x.l1], x.r = pr[x.r1];↵
if (y.b) y.l = pl[y.l1], y.r = pr[y.r1];↵
res.v = x.v + y.v + val(x.r + y.l);↵
res.l = x.l;↵
↵
if ((int)res.l.size() < n - 1) {↵
int t = min(n - 1 - (int)res.l.size(), (int)y.l.size());↵
res.l += y.l.substr(0, t);↵
}↵
↵
res.r = y.r;↵
if ((int)res.r.size() < n - 1) {↵
int t = min(n - 1 - (int)res.r.size(), (int)x.r.size());↵
res.r = x.r.substr(x.r.size() - t, t) + res.r;↵
}↵
↵
return res;↵
}↵
↵
void init(long long x) {↵
bool done = 0;↵
↵
for (long long cur = 1, i = 0; cur <= x; cur *= k, ++i) {↵
ma = i;↵
L = 0, R = cur;↵
↵
if (i == 0) {↵
for (int j = 0; j < k; ++j) {↵
if (n == 1) {↵
a[0][j].v = j == s[1];↵
a[0][j].b = 0;↵
a[0][j].l = a[0][j].r = "";↵
}↵
else {↵
a[0][j].v = 0;↵
a[0][j].b = 0;↵
a[0][j].l = a[0][j].r = "";↵
a[0][j].l += (char)j;↵
a[0][j].r = a[0][j].l;↵
}↵
}↵
}↵
else {↵
for (int j = 0; j < k; ++j) {↵
node cur;↵
for (int t = 0; t < k; ++t) {↵
if (!cur.v && !cur.b && cur.l.empty()) cur = a[i - 1][(j + t) % k];↵
else cur = add(cur, a[i - 1][(j + t) % k]);↵
}↵
a[i][j] = cur;↵
}↵
}↵
↵
if (!done && cur >= n - 1) {↵
done = 1;↵
for (int j = 0; j < k; ++j) {↵
pl[j] = a[i][j].l;↵
pr[j] = a[i][j].r;↵
a[i][j].b = 1;↵
a[i][j].l1 = a[i][j].r1 = j;↵
a[i][j].l = a[i][j].r = "";↵
}↵
for (int j = 0; j < k; ++j) {↵
for (int t = 0; t < k; ++t) trans[j][t] = val(pr[j] + pl[t]);↵
}↵
}↵
}↵
}↵
↵
void calc(int dep, int st, long long l, long long r) {↵
if (r <= ql || l > qr) return;↵
↵
if (ql <= l && r - 1 <= qr) {↵
ans = add(ans, a[dep][st]);↵
return;↵
}↵
↵
node cur;↵
long long len = r - l;↵
↵
for (int i = 0; i < k; ++i) {↵
long long nl = l + len / k * i, nr = nl + len / k;↵
↵
if (ql <= nl && nr - 1 <= qr) {↵
if (!cur.v && !cur.b && cur.l.empty()) cur = a[dep - 1][(st + i) % k];↵
else cur = add(cur, a[dep - 1][(st + i) % k]);↵
continue;↵
}↵
↵
if (cur.v || cur.b || !cur.l.empty()) {↵
ans = add(ans, cur);↵
cur.v = 0, cur.b = 0;↵
cur.l = cur.r = "";↵
}↵
calc(dep - 1, (st + i) % k, nl, nr);↵
}↵
↵
if (cur.v || cur.b || !cur.l.empty()) ans = add(ans, cur);↵
}↵
↵
int main() {↵
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
↵
cin >>
while (T--) {↵
cin >> ql >> qr >> n >> s;↵
s = " " + s + "!";↵
↵
make_fai();↵
init(qr);↵
++ma, R *= k;↵
↵
ans.v = 0, ans.b = 0;↵
ans.l = ans.r = "";↵
calc(ma, 0, L, R);↵
cout << ans.v << '\n';↵
}↵
↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
## [problem:2249E2]↵
↵
- Idea:[user:131241,2026-07-26]↵
↵
- Solution:[user:131241,2026-07-26]↵
↵
<spoiler summary="Hint 1">↵
Partition the infinite string into blocks of length $k$. Every block is a cyclic shift of $\mathtt{012\ldots(k-1)}$. If each block is replaced by its shift value, the resulting sequence is the original infinite string again.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Let↵
↵
$$↵
d_i=(t_i-t_{i-1}+k)\bmod k.↵
$$↵
↵
Inside a complete block, $d_i$ is always $1$. Therefore, all positions with $d_i\ne1$ must have the same residue modulo $k$.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
If the positions with $d_i\ne1$ determine the block boundaries, compress both the pattern and the query interval by a factor of about $k$ and recurse. If no such position exists, an occurring pattern cannot be longer than $2k$.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
First examine the block structure of the infinite string $s$. Every block of length $k$ is a cyclic shift of↵
↵
$$↵
\mathtt{012\ldots(k-1)}.↵
$$↵
↵
If each complete block is replaced by its shift value, the resulting sequence is again $s$. Therefore, once the pattern $t$ is aligned with these blocks, both the pattern and the query interval can be compressed by a factor of about $k$.↵
↵
To determine the alignment, consider the adjacent differences of $t$ modulo $k$:↵
↵
$$↵
d_i=(t_i-t_{i-1}+k)\bmod k.↵
$$↵
↵
Inside a complete cyclic block, every adjacent difference is $1$. Hence, every position with $d_i\ne1$ must correspond to the same type of block boundary, so all such positions must have the same residue modulo $k$. If two different residues occur, the pattern cannot appear.↵
↵
If exactly one residue class occurs, the block boundaries are uniquely determined. Split $t$ according to these boundaries, compress each complete block into its shift value, map $[l,r]$ to the corresponding compressed interval according to the two partial end blocks, and recurse.↵
↵
It remains to handle the case in which every $d_i=1$, so the block boundaries are not determined. The string $s$ contains no substring longer than $2k$ whose adjacent differences are all $1$. Otherwise, there would be three corresponding terms satisfying $s_i=s_{i+k}=s_{i+2k}$. However, the equality $s_i=s_{i+k}$ requires a particular carry pattern when $i$ is increased by $k$, and the same pattern cannot hold again for $i+k$.↵
↵
Therefore, any pattern that occurs must satisfy $n\le2k$. We can enumerate all possible block alignments, reducing the compressed pattern to length at most $2$. When $n\le k$, we must also consider alignments that compress it to a single character. Different alignments correspond to different starting positions in the original string, so they are not counted more than once.↵
↵
We are left with occurrence queries for patterns of length $1$ or $2$.↵
↵
For a pattern of length $1$, every complete block of length $k$ contains each character exactly once. Only the final partial block of a prefix query needs to be checked directly.↵
↵
For a pattern of length $2$, precompute↵
↵
$$↵
f_{p,q,x,y},↵
$$↵
↵
the number of occurrences of the pair $xy$ in the first $qk^p$ characters. A block at the next level consists of $k$ shifted copies of a smaller block. Their internal contributions are accumulated with the appropriate shifts, and occurrences crossing block boundaries are counted by checking adjacent endpoints. A prefix can be decomposed in base $k$, and an interval answer is obtained by subtracting two prefix answers.↵
↵
The total time complexity is↵
↵
$$↵
O\left(qk\log_k V+\sum n+k^3\log_k V+k\log_k^2V\right),↵
$$↵
↵
where $V=10^{17}$.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```cpp↵
#include<bits/stdc++.h>↵
#define int long long↵
using namespace std;↵
int lg;↵
int q,L,R,n,k,d[10000005],t[100],b[100];↵
char c[10000005],s[10000005];↵
struct node{↵
int f[65][65];↵
}sum[65][65];↵
node merge(node a,node b,int v=1){↵
for(int i=0;i<k;i++){↵
for(int j=0;j<k;j++){↵
a.f[(i+v)%k][(j+v)%k]+=b.f[i][j];↵
}↵
}↵
return a;↵
}↵
int calc(int x){↵
int sum=0;↵
while(x){↵
sum+=x%k;↵
x=x/k;↵
}↵
return sum%k;↵
}↵
int sp[70];↵
int gs(int r,int x,int y){↵
// Count occurrences of the pattern "xy" in the range [0, r].↵
r++;↵
int cnt=0,xnow=0,ans=0,lowbit=0;↵
for(int i=0;i<=lg;i++){↵
sp[i]=r%k;r/=k;↵
}↵
for(int i=lg;i>=0;i--){↵
int j=sp[i];↵
if(!j) continue;↵
ans+=sum[i][j].f[(x+(k-1)*cnt)%k][(y+(k-1)*cnt)%k];↵
if(xnow){↵
int px=(cnt-1+lowbit*(k-1))%k,py=cnt%k;↵
if(px==x&&py==y){↵
ans++;↵
}↵
}↵
xnow+=b[i]*j;↵
cnt+=j;↵
lowbit=i;↵
}↵
return ans;↵
}↵
int gs(int r,int x){↵
// Count occurrences of the pattern "x" in the range [0, r].↵
r++;↵
int sum=r/k,pl=r/k*k,y=calc(pl);↵
while(pl<r){↵
if(y==x){↵
sum++;↵
break;↵
}↵
pl++;↵
y++;↵
y>=k?y-=k:0;↵
}↵
return sum;↵
}↵
void print(char c){↵
if(c<10){↵
cout<<char(c+'0');↵
}else{↵
cout<<char(c+'a'-10);↵
}↵
}↵
int ans=0;↵
void solve(int l,int r,int n){↵
// Compute the answer recursively.↵
if(l>r){↵
return ;↵
}↵
for(int i=0;i<k;i++){↵
t[i]=0;↵
}↵
if(n<=2){↵
// For length at most 2, use prefix-count differences directly.↵
if(n==2){↵
int pl=c[0],pr=c[1];↵
int sum=gs(r,pl,pr)-gs(l,pl,pr);↵
ans+=sum;↵
return ;↵
}else{↵
int sum=0;↵
sum=gs(r,c[0])-gs(l-1,c[0]);↵
ans+=sum;↵
return ;↵
}↵
}↵
int cnt=0;↵
for(int i=1;i<n;i++){↵
d[i]=(c[i]-c[i-1]+k)%k;↵
if(d[i]!=1){↵
if(!t[i%k]) cnt++;↵
t[i%k]=1;↵
}↵
}↵
if(cnt>1){↵
// If more than one residue occurs, the pattern cannot appear.↵
return ;↵
}↵
int m=0,pl=k,pr=k,p=0;↵
if(cnt){↵
// At least one adjacent difference is not 1.↵
for(int i=1;i<n;i++){↵
if(d[i]!=1) p=i%k;↵
}↵
if(p){↵
pl=p;↵
s[m++]=(c[p-1]+1)%k;↵
}↵
for(int i=p;i<n;i+=k){↵
if(i+k-1>=n) pr=n-i;↵
s[m++]=c[i];↵
}↵
↵
// Handle the two partial boundary blocks separately.↵
int bl=(r/k)*k,br=(l/k+1)*k-1;↵
if(br-l+1<pl) l=l/k+1;↵
else l=l/k;↵
if(r-bl+1<pr) r=r/k-1;↵
else r=r/k;↵
↵
for(int i=0;i<m;i++) c[i]=s[i];↵
solve(l,r,m);↵
}else{↵
// Every adjacent difference is 1.↵
int szl=(l/k+1)*k-l,szr=r-(r/k)*k+1,L,R;↵
if(n<=k){↵
int x=c[0];↵
for(int i=0;i+n-1<k;i++){↵
c[0]=(x-i+k)%k;↵
// Handle the two partial boundary blocks separately.↵
pl=k-i,pr=i+n;↵
if(szl<pl) L=l/k+1;↵
else L=l/k;↵
if(szr<pr) R=r/k-1;↵
else R=r/k;↵
solve(L,R,1);↵
}↵
}↵
for(int i=0;i<n;i++){↵
s[i]=c[i];↵
}↵
for(int i=0;i<min(n-1,k);i++){↵
// Handle the two partial boundary blocks separately.↵
pl=i+1,pr=n-1-i;↵
if(pr>k) continue;↵
if(szl<pl) L=l/k+1;↵
else L=l/k;↵
if(szr<pr) R=r/k-1;↵
else R=r/k;↵
c[0]=c[1]=s[i+1];↵
solve(L,R,2);↵
}↵
}↵
}↵
char change(int x){↵
if(0<=x&&x<=9) return x+'0';↵
if(10<=x&&x<=35) return x-10+'A';↵
if(36<=x&&x<=61) return x-36+'a';↵
}↵
int change(char x){↵
if('0'<=x&&x<='9') return x-'0';↵
if('A'<=x&&x<='Z') return x+10-'A';↵
if('a'<=x&&x<='z') return x+36-'a';↵
}↵
signed main(){↵
ios::sync_with_stdio(0);↵
cin.tie(0);cout.tie(0);↵
cin>>k>>q;↵
↵
// sum[i][j] stores counts of length-2 substrings in the first j * k^i characters.↵
b[0]=1;lg=0;↵
for(int i=1;i<=k;i++){↵
for(int j=1;j<i;j++){↵
sum[0][i].f[j-1][j]=1;↵
}↵
}↵
for(int p=1;p;p++){↵
b[p]=b[p-1]*k;↵
lg++;↵
if(b[p]>1e17){↵
break;↵
}↵
sum[p][1]=sum[p-1][k];↵
// Concatenate the k shifted blocks.↵
for(int i=2;i<=k;i++){↵
sum[p][i]=merge(sum[p][i-1],sum[p-1][k],i-1);↵
// Count substrings that cross a block boundary directly.↵
sum[p][i].f[calc(b[p]*(i-1)-1)][calc(b[p]*(i-1))]++;↵
}↵
}↵
↵
while(q--){↵
cin>>L>>R>>n;↵
cin>>c;↵
for(int i=0;i<n;i++){↵
c[i]=change(c[i]);↵
}↵
solve(L,R,n);↵
cout<<ans<<endl;↵
ans=0;↵
}↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
## [problem:2249F]↵
↵
- Idea:[user:aaa_Pigeon2,2026-07-26]↵
↵
- Solution:[user:aaa_Pigeon2,2026-07-26]↵
↵
<spoiler summary="Hint 1">↵
In a simple path, the two endpoints have degree $1$, every other used vertex has degree $2$, and every unused vertex has degree $0$. Can this degree condition be encoded by a matching?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Split every vertex into left and right copies, but remove $R(1)$ and $L(n)$. Original edges connect copies within the same layer, while an unused internal vertex matches its two copies with a cross-layer edge.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Give every cross-layer edge weight $M$ and every same-layer edge corresponding to an original edge weight $M-1$. A maximum-weight matching eliminates extra cycles and minimizes the resulting path length.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
The main difficulty is the simple-path constraint. We encode the degree structure of a simple path as a matching.↵
↵
A simple path from vertex $1$ to vertex $n$ satisfies the following degree conditions:↵
↵
- Vertices $1$ and $n$ have degree $1$ in the path.↵
- Every other used vertex has degree $2$.↵
- Every unused vertex has degree $0$.↵
↵
For every vertex $v$ of the original graph $G=(V,E)$, create two copies, $L(v)$ and $R(v)$, and then remove $R(1)$ and $L(n)$. The vertex set of the auxiliary graph $G'=(V',E')$ is↵
↵
$$↵
V'=\{L(v)\mid v\ne n\}\cup\{R(v)\mid v\ne1\}.↵
$$↵
↵
Removing these two copies ensures that vertices $1$ and $n$ contribute exactly one path edge each. Because the removed copies belong to different layers, the recovered path is also forced to have even length.↵
↵
For every original edge $(u,v)\in E$, add the same-layer edges $(L(u),L(v))$ and $(R(u),R(v))$ whenever both endpoint copies exist. Give each of these edges weight $M-1$.↵
↵
For every internal vertex $v\notin\{1,n\}$, add a cross-layer edge $(L(v),R(v))$ of weight $M$, where $M$ is any constant greater than $|V'|$.↵
↵
Compute a maximum-weight matching in the general graph $G'$. If it is not perfect, no valid path exists. Otherwise, the answer can be recovered from it. Since $M>|V'|$, whenever a perfect matching exists, losing one matching edge decreases the weight by more than all possible gains obtained by replacing the remaining edges. Therefore, a maximum-weight matching must be perfect.↵
↵
#### Interpretation of a Perfect Matching↵
↵
Consider a perfect matching $S$.↵
↵
For an internal vertex $v$, if $S$ contains the cross-layer edge $(L(v),R(v))$, then $v$ is unused, corresponding to degree $0$ in the original graph.↵
↵
Otherwise, $L(v)$ and $R(v)$ are each matched by a same-layer edge, so $v$ has degree $2$ in the original graph.↵
↵
Vertices $1$ and $n$ each have only one copy and no cross-layer edge, so they naturally have degree $1$.↵
↵
Thus, mapping all selected same-layer edges back to the original graph yields a path from $1$ to $n$, together with zero or more vertex-disjoint cycles.↵
↵
#### Why the Path Length Is Even↵
↵
Suppose there is an even-length simple path↵
↵
$$↵
p_0=1,p_1,p_2,\ldots,p_L=n.↵
$$↵
↵
Choose same-layer edges alternately along the path: use the left layer for the first edge, the right layer for the second edge, and so on. Since $L$ is even, the last edge lies in the right layer and reaches the existing copy $R(n)$. Every internal vertex not on the path is matched by its own cross-layer edge, producing a perfect matching.↵
↵
Conversely, take the symmetric difference of any perfect matching with the set of all cross-layer edges. The component containing $L(1)$ alternates between same-layer matching edges and cross-layer edges and eventually reaches $R(n)$. Consequently, it contains an even number of original edges. It has exactly two vertices of degree $1$, while every other vertex has degree $2$, so it corresponds to an even-length simple path.↵
↵
#### Why Maximum Weight Eliminates Cycles↵
↵
Suppose the recovered structure contains a cycle with $c$ vertices. The cycle uses $c$ same-layer matching edges of weight $M-1$, for a total weight of $c(M-1)$.↵
↵
Remove these edges and instead select the cross-layer edge of every vertex on the cycle. This still gives a perfect matching, but the total weight contributed by these vertices becomes $cM$, which is strictly larger. This contradicts maximality. Therefore, a maximum-weight perfect matching contains no extra cycle.↵
↵
#### Why the Recovered Path Is Shortest↵
↵
Every perfect matching contains the same number of edges. Cross-layer edges have weight $M$, while same-layer edges have weight $M-1$, so maximizing the total weight is equivalent to minimizing the number of same-layer edges.↵
↵
A maximum-weight matching contains no extra cycles, so its same-layer edges correspond exactly to the edges of the recovered path. Hence, the recovered path is the shortest even-length simple path.↵
↵
#### Matching and Path Recovery↵
↵
The auxiliary graph has $2n-2$ vertices and at most $2m+n-2$ edges. We therefore use a maximum-weight matching algorithm for general graphs, such as the weighted blossom algorithm, whose time complexity is $O(|V'|^3)$.↵
↵
After finding the matching:↵
↵
1. If its size is not $|V'|/2$, output $-1$.↵
2. Take the symmetric difference between the matching and the set of cross-layer edges of all internal vertices.↵
3. The cross-layer edges of unused vertices cancel, and the remaining auxiliary graph is exactly a path from $L(1)$ to $R(n)$.↵
4. Traverse this path and record the corresponding original vertex whenever a same-layer edge is crossed.↵
↵
This recovers the required shortest even-length simple path
↵
First, consider the degree pattern of a simple path from vertex $1$ to vertex $n$:↵
↵
* vertices $1$ and $n$ have degree $1$ in the path;↵
* every other used vertex has degree $2$;↵
* every unused vertex has degree $0$.↵
↵
We will build an auxiliary graph where:↵
↵
* an unused vertex corresponds to one internal matching edge;↵
* a used internal vertex must match both of its copies to other vertices;↵
* vertices $1$ and $n$ have only one copy each, so they contribute exactly one path edge.↵
↵
Then a perfect matching in the auxiliary graph will describe a path in the original graph.↵
↵
---↵
↵
Let the original graph be $G=(V,E)$.↵
↵
For every vertex $v$, create two copies $L(v)$ and $R(v)$. Then delete $R(1)$ and $L(n)$. Thus the vertex set of the auxiliary graph $G'=(V',E')$ is↵
↵
$$↵
V'=\{L(v)\mid v\ne n\}\cup\{R(v)\mid v\ne 1\}↵
$$↵
↵
We delete these two copies because vertices $1$ and $n$ should have degree $1$ in the restored path. Every internal vertex still has both copies, so it may contribute degree $2$.↵
↵
Also, the deleted copies are in different layers. This is what forces the restored path to have even length.↵
↵
For every original edge $(u,v)\in E$, add the same-layer edges $(L(u),L(v))$ and $(R(u),R(v))$ whenever both endpoints exist. Give each of these edges weight $M-1$.↵
↵
For every internal vertex $v\notin\{1,n\}$, add the cross-layer edge $(L(v),R(v))$ with weight $M$.↵
↵
Here $M$ is a sufficiently large constant, for example any $M>|V'|$.↵
↵
Now find a maximum-weight matching in the general graph $G'$. If it is not a perfect matching, then there is no valid path. Otherwise, we restore the answer from it.↵
↵
The choice $M>|V'|$ is useful here: if a perfect matching exists, any matching that misses at least one edge loses more weight than it can gain by changing all remaining edges from weight $M-1$ to weight $M$. Therefore a maximum-weight matching will be perfect whenever a perfect matching exists.↵
↵
---↵
↵
## Meaning of a Perfect Matching↵
↵
Consider a perfect matching $S$ of $G'$.↵
↵
For an internal vertex $v\notin\{1,n\}$, both $L(v)$ and $R(v)$ must be matched.↵
↵
If $S$ contains the cross-layer edge $(L(v),R(v))$, we treat $v$ as unused. This corresponds to degree $0$ in the original graph.↵
↵
Otherwise, $L(v)$ and $R(v)$ are each matched to another copy through same-layer edges. After mapping these same-layer edges back to the original graph, vertex $v$ has degree $2$.↵
↵
Vertices $1$ and $n$ have only one copy each and have no cross-layer edge, so they naturally have degree $1$.↵
↵
Thus the selected same-layer edges map to a subgraph of the original graph in which:↵
↵
* vertices $1$ and $n$ have degree $1$;↵
* every other vertex has degree $0$ or $2$.↵
↵
So this subgraph consists of one path from $1$ to $n$ and possibly several cycles.↵
↵
We now prove the construction in both directions and then explain why maximum weight removes the cycles and minimizes the path length.↵
↵
---↵
↵
### Proof 1: Every Even Simple Path Gives a Perfect Matching↵
↵
Suppose we have an even-length simple path↵
↵
$$↵
p_0=1,p_1,p_2,\ldots,p_L=n↵
$$↵
↵
where $2\mid L$.↵
↵
Choose edges along this path alternately:↵
↵
* for the first edge $(p_0,p_1)$, choose $(L(p_0),L(p_1))$;↵
* for the second edge $(p_1,p_2)$, choose $(R(p_1),R(p_2))$;↵
* for the third edge, choose the corresponding left-layer edge;↵
* for the fourth edge, choose the corresponding right-layer edge;↵
* and so on.↵
↵
Since $L$ is even, the last path edge $(p_{L-1},p_L)$ is chosen in the right layer, and $R(n)$ exists.↵
↵
For every internal vertex $v$ not on the path, choose the cross-layer edge $(L(v),R(v))$.↵
↵
Now every vertex of $G'$ is matched exactly once, so we have constructed a perfect matching.↵
↵
---↵
↵
### Proof 2: Every Perfect Matching Gives an Even Simple Path↵
↵
Take any perfect matching of $G'$ and map all selected same-layer edges back to the original graph.↵
↵
As shown above, the resulting subgraph has degree $1$ at vertices $1$ and $n$, and degree $0$ or $2$ at every other vertex. Therefore it is the disjoint union of one path from $1$ to $n$ and some cycles.↵
↵
Let us look at the path component. In the auxiliary graph, the endpoint corresponding to vertex $1$ is $L(1)$, while the endpoint corresponding to vertex $n$ is $R(n)$. Along the restored component, same-layer edges are the original graph edges, and the only way to switch layers is through cross-layer edges of the form $(L(v),R(v))$.↵
↵
Therefore the original edges on the path must appear as↵
↵
$$↵
\text{left layer},\ \text{right layer},\ \text{left layer},\ \text{right layer},\ldots,\ \text{right layer}↵
$$↵
↵
So the number of original edges on this path is even.↵
↵
The path component has exactly two vertices of degree $1$ and all other vertices of degree $2$, so it is a simple path. Hence every perfect matching gives an even-length simple path from $1$ to $n$, possibly together with extra cycles.↵
↵
---↵
↵
### Proof 3: A Maximum-Weight Perfect Matching Has No Extra Cycles↵
↵
Assume that a maximum-weight perfect matching maps back to a path from $1$ to $n$ plus at least one cycle. Let this cycle contain $k$ vertices.↵
↵
Every vertex on the cycle is used, so none of them uses its cross-layer edge. The cycle contributes exactly $k$ same-layer matching edges, with total weight↵
↵
$$↵
k(M-1)↵
$$↵
↵
Now remove this cycle from the matching and, for every vertex $v$ on the cycle, choose the cross-layer edge $(L(v),R(v))$ instead.↵
↵
This is still a valid perfect matching. The affected part now has total weight↵
↵
$$↵
kM↵
$$↵
↵
Since $kM>k(M-1)$, the matching weight increases, which contradicts maximality.↵
↵
Therefore a maximum-weight perfect matching cannot produce extra cycles. It restores exactly one even-length simple path from $1$ to $n$.↵
↵
---↵
↵
### Proof 4: The Restored Path Is Shortest↵
↵
In any perfect matching of $G'$, the number of matched edges is fixed.↵
↵
Cross-layer edges have weight $M$, and same-layer edges have weight $M-1$. Thus maximizing the total weight is the same as minimizing the number of selected same-layer edges.↵
↵
After Proof 3, a maximum-weight perfect matching has no extra cycles, so its selected same-layer edges are exactly the edges of the restored path. Therefore the maximum-weight perfect matching gives a shortest even-length simple path.↵
↵
---↵
↵
## Finding the Matching and Restoring the Path↵
↵
The auxiliary graph is not necessarily bipartite, because both the left layer and the right layer may contain edges. Therefore we need maximum-weight matching in a general graph, for example the weighted blossom algorithm.↵
↵
The auxiliary graph has $2n-2$ vertices and at most $2m+n-2$ edges. The weighted blossom algorithm runs in $O(|V'|^3)$ time.↵
↵
After computing the maximum-weight matching:↵
↵
* if its size is not $|V'|/2$, output $-1$;↵
* otherwise, take the symmetric difference between the matching edges and all cross-layer edges $(L(v),R(v))$ for $v\notin\{1,n\}$.↵
↵
Unused vertices disappear from this symmetric difference, because their cross-layer edge is present in both sets. Used vertices remain connected through their two copies.↵
↵
The resulting auxiliary graph contains one path from $L(1)$ to $R(n)$ and no cycles for a maximum-weight matching. Traverse this path and write down the original vertex whenever a same-layer edge is crossed. This gives the required shortest even-length simple path from vertex $1$ to vertex $n$.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int N = 1000;↵
const int V = 2 * N;↵
const int B = 2 * V;↵
const int inf = 0x3f3f3f3f;↵
const int big = 10000;↵
↵
struct edge {↵
int u, v, w;↵
};↵
↵
int n, m;↵
int idL[N + 10], idR[N + 10], ori[V + 10];↵
int init_u[N + 10], init_v[N + 10], init_cnt;↵
char sx[V + 10][V + 10];↵
vector<int> adj[V + 10];↵
↵
struct blossom_tree {↵
int n, nx;↵
edge g[B + 10][B + 10];↵
int lab[B + 10], match[B + 10], slack[B + 10], st[B + 10], pa[B + 10];↵
int flower_from[B + 10][V + 10], flower[B + 10][V + 10];↵
int S[B + 10], vis[B + 10], flower_cnt[B + 10], tmp[V + 10];↵
queue<int> q;↵
↵
void init(int _n) {↵
n = _n, nx = n;↵
↵
for (int i = 0; i <= 2 * n + 2; ++i) {↵
lab[i] = match[i] = slack[i] = st[i] = pa[i] = S[i] = vis[i] = 0;↵
flower_cnt[i] = 0;↵
for (int j = 0; j <= n; ++j) flower_from[i][j] = 0;↵
}↵
↵
for (int i = 1; i <= 2 * n + 2; ++i) {↵
for (int j = 1; j <= 2 * n + 2; ++j) g[i][j] = {i, j, 0};↵
}↵
}↵
↵
void add_edge(int u, int v, int w) {↵
if (u == v) return;↵
↵
if (w > g[u][v].w) {↵
g[u][v] = {u, v, w};↵
g[v][u] = {v, u, w};↵
}↵
}↵
↵
int e_delta(edge e) {↵
return lab[e.u] + lab[e.v] - g[e.u][e.v].w * 2;↵
}↵
↵
void update_slack(int u, int x) {↵
if (!slack[x] || e_delta(g[u][x]) < e_delta(g[slack[x]][x])) slack[x] = u;↵
}↵
↵
void set_slack(int x) {↵
slack[x] = 0;↵
↵
for (int u = 1; u <= n; ++u) {↵
if (g[u][x].w && st[u] != x && S[st[u]] == 0) update_slack(u, x);↵
}↵
}↵
↵
void q_push(int x) {↵
if (x <= n) q.push(x);↵
else {↵
for (int i = 0; i < flower_cnt[x]; ++i) q_push(flower[x][i]);↵
}↵
}↵
↵
void set_st(int x, int b) {↵
st[x] = b;↵
↵
if (x > n) {↵
for (int i = 0; i < flower_cnt[x]; ++i) set_st(flower[x][i], b);↵
}↵
}↵
↵
void reverse_flower(int b, int l, int r) {↵
while (l < r) {↵
swap(flower[b][l], flower[b][r]);↵
++l, --r;↵
}↵
}↵
↵
void rotate_flower(int b, int pr) {↵
int cnt = flower_cnt[b];↵
↵
for (int i = 0; i < cnt; ++i) tmp[i] = flower[b][(i + pr) % cnt];↵
for (int i = 0; i < cnt; ++i) flower[b][i] = tmp[i];↵
}↵
↵
int get_pr(int b, int xr) {↵
int pr = 0;↵
↵
while (flower[b][pr] != xr) ++pr;↵
↵
if (pr & 1) {↵
reverse_flower(b, 1, flower_cnt[b] - 1);↵
return flower_cnt[b] - pr;↵
}↵
↵
return pr;↵
}↵
↵
void set_match(int u, int v) {↵
match[u] = g[u][v].v;↵
↵
if (u > n) {↵
edge e = g[u][v];↵
int xr = flower_from[u][e.u];↵
int pr = get_pr(u, xr);↵
↵
for (int i = 0; i < pr; ++i) set_match(flower[u][i], flower[u][i ^ 1]);↵
↵
set_match(xr, v);↵
rotate_flower(u, pr);↵
}↵
}↵
↵
void augment(int u, int v) {↵
while (true) {↵
int xnv = st[match[u]];↵
↵
set_match(u, v);↵
↵
if (!xnv) return;↵
↵
set_match(xnv, st[pa[xnv]]);↵
u = st[pa[xnv]], v = xnv;↵
}↵
}↵
↵
int get_lca(int u, int v) {↵
static int tim = 0;↵
++tim;↵
↵
while (u || v) {↵
if (u) {↵
if (vis[u] == tim) return u;↵
↵
vis[u] = tim;↵
u = st[match[u]];↵
↵
if (u) u = st[pa[u]];↵
}↵
↵
swap(u, v);↵
}↵
↵
return 0;↵
}↵
↵
void add_blossom(int u, int lca, int v) {↵
int b = n + 1;↵
↵
while (b <= nx && st[b]) ++b;↵
if (b > nx) ++nx;↵
↵
lab[b] = 0, S[b] = 0, match[b] = match[lca];↵
flower_cnt[b] = 0;↵
flower[b][flower_cnt[b]++] = lca;↵
↵
for (int x = u, y; x != lca; x = st[pa[y]]) {↵
flower[b][flower_cnt[b]++] = x;↵
y = st[match[x]];↵
flower[b][flower_cnt[b]++] = y;↵
q_push(y);↵
}↵
↵
reverse_flower(b, 1, flower_cnt[b] - 1);↵
↵
for (int x = v, y; x != lca; x = st[pa[y]]) {↵
flower[b][flower_cnt[b]++] = x;↵
y = st[match[x]];↵
flower[b][flower_cnt[b]++] = y;↵
q_push(y);↵
}↵
↵
set_st(b, b);↵
↵
for (int x = 1; x <= nx; ++x) {↵
g[b][x] = {b, x, 0};↵
g[x][b] = {x, b, 0};↵
}↵
↵
for (int x = 1; x <= n; ++x) flower_from[b][x] = 0;↵
↵
for (int i = 0; i < flower_cnt[b]; ++i) {↵
int xs = flower[b][i];↵
↵
for (int x = 1; x <= nx; ++x) {↵
if (g[xs][x].w && (!g[b][x].w || e_delta(g[xs][x]) < e_delta(g[b][x]))) {↵
g[b][x] = g[xs][x];↵
g[x][b] = g[x][xs];↵
}↵
}↵
↵
for (int x = 1; x <= n; ++x) {↵
if (flower_from[xs][x]) flower_from[b][x] = xs;↵
}↵
}↵
↵
set_slack(b);↵
}↵
↵
void expand_blossom(int b) {↵
for (int i = 0; i < flower_cnt[b]; ++i) set_st(flower[b][i], flower[b][i]);↵
↵
int xr = flower_from[b][g[b][pa[b]].u];↵
int pr = get_pr(b, xr);↵
↵
for (int i = 0; i < pr; i += 2) {↵
int xs = flower[b][i];↵
int xns = flower[b][i + 1];↵
↵
pa[xs] = g[xns][xs].u;↵
S[xs] = 1, S[xns] = 0;↵
slack[xs] = 0;↵
↵
set_slack(xns);↵
q_push(xns);↵
}↵
↵
S[xr] = 1;↵
pa[xr] = pa[b];↵
↵
for (int i = pr + 1; i < flower_cnt[b]; ++i) {↵
int xs = flower[b][i];↵
↵
S[xs] = -1;↵
set_slack(xs);↵
}↵
↵
st[b] = 0;↵
}↵
↵
bool on_found_edge(edge e) {↵
int u = st[e.u], v = st[e.v];↵
↵
if (S[v] == -1) {↵
pa[v] = e.u;↵
S[v] = 1;↵
↵
int nu = st[match[v]];↵
↵
slack[v] = slack[nu] = 0;↵
S[nu] = 0;↵
↵
q_push(nu);↵
}↵
else if (S[v] == 0) {↵
int lca = get_lca(u, v);↵
↵
if (!lca) {↵
augment(u, v);↵
augment(v, u);↵
return true;↵
}↵
else add_blossom(u, lca, v);↵
}↵
↵
return false;↵
}↵
↵
bool matching() {↵
for (int i = 1; i <= nx; ++i) S[i] = -1, slack[i] = 0;↵
↵
while (!q.empty()) q.pop();↵
↵
for (int x = 1; x <= nx; ++x) {↵
if (st[x] == x && !match[x]) {↵
pa[x] = 0;↵
S[x] = 0;↵
q_push(x);↵
}↵
}↵
↵
if (q.empty()) return false;↵
↵
while (true) {↵
while (!q.empty()) {↵
int u = q.front(); q.pop();↵
if (S[st[u]] == 1) continue;↵
↵
for (int v = 1; v <= n; ++v) {↵
if (g[u][v].w && st[u] != st[v]) {↵
if (!e_delta(g[u][v])) {↵
if (on_found_edge(g[u][v])) return true;↵
}↵
else update_slack(u, st[v]);↵
}↵
}↵
}↵
↵
int d = inf;↵
↵
for (int u = 1; u <= n; ++u) {↵
if (S[st[u]] == 0) d = min(d, lab[u]);↵
}↵
↵
for (int b = n + 1; b <= nx; ++b) {↵
if (st[b] == b && S[b] == 1) d = min(d, lab[b] / 2);↵
}↵
↵
for (int x = 1; x <= nx; ++x) {↵
if (st[x] == x && slack[x]) {↵
if (S[x] == -1) d = min(d, e_delta(g[slack[x]][x]));↵
else if (S[x] == 0) d = min(d, e_delta(g[slack[x]][x]) / 2);↵
}↵
}↵
↵
if (d == inf) return false;↵
↵
for (int u = 1; u <= n; ++u) {↵
if (S[st[u]] == 0) {↵
if (lab[u] == d) return false;↵
lab[u] -= d;↵
}↵
else if (S[st[u]] == 1) lab[u] += d;↵
}↵
↵
for (int b = n + 1; b <= nx; ++b) {↵
if (st[b] == b) {↵
if (S[b] == 0) lab[b] += d * 2;↵
else if (S[b] == 1) lab[b] -= d * 2;↵
}↵
}↵
↵
while (!q.empty()) q.pop();↵
↵
for (int x = 1; x <= nx; ++x) {↵
if (st[x] == x && slack[x] && st[slack[x]] != x && !e_delta(g[slack[x]][x])) {↵
if (on_found_edge(g[slack[x]][x])) return true;↵
}↵
}↵
↵
for (int b = n + 1; b <= nx; ++b) {↵
if (st[b] == b && S[b] == 1 && !lab[b]) expand_blossom(b);↵
}↵
}↵
}↵
↵
int solve() {↵
nx = n;↵
int cnt = 0, mx = 0;↵
↵
for (int i = 0; i <= 2 * n + 2; ++i) {↵
lab[i] = match[i] = slack[i] = pa[i] = S[i] = vis[i] = 0;↵
st[i] = 0;↵
flower_cnt[i] = 0;↵
}↵
↵
for (int i = 0; i <= n; ++i) st[i] = i;↵
↵
for (int u = 1; u <= n; ++u) {↵
for (int v = 1; v <= n; ++v) {↵
flower_from[u][v] = (u == v ? u : 0);↵
mx = max(mx, g[u][v].w);↵
}↵
}↵
↵
for (int u = 1; u <= n; ++u) lab[u] = mx;↵
↵
while (matching()) ++cnt;↵
return cnt;↵
}↵
} blossom;↵
↵
int new_node(int x, int &tot) {↵
ori[tot + 1] = x;↵
return ++tot;↵
}↵
↵
void toggle_edge(int u, int v) {↵
if (u > v) swap(u, v);↵
sx[u][v] ^= 1;↵
}↵
↵
void work() {↵
cin >> n >> m;↵
↵
memset(idL, -1, sizeof(idL));↵
memset(idR, -1, sizeof(idR));↵
↵
int tot = 0;↵
↵
for (int i = 1; i <= n; ++i) {↵
if (i != n) idL[i] = new_node(i, tot);↵
}↵
for (int i = 1; i <= n; ++i) {↵
if (i != 1) idR[i] = new_node(i, tot);↵
}↵
↵
blossom.init(tot);↵
↵
for (int i = 1; i <= m; ++i) {↵
int u, v; cin >> u >> v;↵
↵
if (idL[u] != -1 && idL[v] != -1) blossom.add_edge(idL[u], idL[v], big - 1);↵
if (idR[u] != -1 && idR[v] != -1) blossom.add_edge(idR[u], idR[v], big - 1);↵
}↵
↵
init_cnt = 0;↵
↵
for (int i = 2; i < n; ++i) {↵
blossom.add_edge(idL[i], idR[i], big);↵
init_u[++init_cnt] = idL[i], init_v[init_cnt] = idR[i];↵
}↵
↵
int cnt = blossom.solve();↵
↵
if (cnt != tot / 2) {↵
cout << -1 << '\n';↵
return;↵
}↵
↵
for (int i = 1; i <= tot; ++i) {↵
adj[i].clear();↵
for (int j = 1; j <= tot; ++j) sx[i][j] = 0;↵
}↵
↵
for (int i = 1; i <= tot; ++i) {↵
if (blossom.match[i] && i < blossom.match[i]) toggle_edge(i, blossom.match[i]);↵
}↵
↵
for (int i = 1; i <= init_cnt; ++i) toggle_edge(init_u[i], init_v[i]);↵
↵
for (int i = 1; i <= tot; ++i) {↵
for (int j = i + 1; j <= tot; ++j) {↵
if (sx[i][j]) {↵
adj[i].push_back(j);↵
adj[j].push_back(i);↵
}↵
}↵
}↵
↵
int st = idL[1], ed = idR[n];↵
vector<int> aux, path;↵
int last = 0, cur = st;↵
↵
while (true) {↵
aux.push_back(cur);↵
if (cur == ed) break;↵
↵
int nxt = 0;↵
↵
for (int v : adj[cur]) {↵
if (v != last) {↵
nxt = v;↵
break;↵
}↵
}↵
↵
if (!nxt) {↵
cout << -1 << '\n';↵
return;↵
}↵
↵
last = cur, cur = nxt;↵
↵
if ((int)aux.size() > tot + 5) {↵
cout << -1 << '\n';↵
return;↵
}↵
}↵
↵
path.push_back(1);↵
for (int i = 1; i < (int)aux.size(); ++i) {↵
int u = aux[i - 1], v = aux[i];↵
if (ori[u] != ori[v]) path.push_back(ori[v]);↵
}↵
↵
if (path.back() != n || ((int)path.size() - 1) % 2) {↵
cout << -1 << '\n';↵
return;↵
}↵
↵
cout << (int)path.size() - 1 << '\n';↵
for (int i = 0; i < (int)path.size(); ++i) {↵
if (i) cout << ' ';↵
cout << path[i];↵
}↵
cout << '\n';↵
}↵
↵
int main() {↵
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
↵
int T; cin >> T;↵
while (T--) work();↵
↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
