2249.md (51640B)
1 Source: https://codeforces.com/blog/entry/155516 2 3 ## [2250A - Threshold Movement](/contest/2250/problem/A "Codeforces Round 1112 (Div. 2)") 4 5 * Idea:[aaa_Pigeon2](/profile/aaa_Pigeon2 "International Grandmaster aaa_Pigeon2") 6 * Solution:[aaa_Pigeon2](/profile/aaa_Pigeon2 "International Grandmaster aaa_Pigeon2") 7 8 **Solution** 9 10 Let us determine what is required for every position to contain exactly one element after the simultaneous move. 11 12 The element initially at position $1$ cannot move to the left, so it must move to the right. Therefore, $w_1 \gt k$. Once it leaves, only the element initially at position $2$ can fill position $1$, so $w_2 \lt k$. 13 14 Thus, the elements at positions $1$ and $2$ must swap. Repeating the same argument for the remaining positions, the only possible movement pattern is 15 16 $ 1\leftrightarrow 2,\quad 3\leftrightarrow 4,\quad 5\leftrightarrow 6,\ldots $ 17 18 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. 19 20 Let 21 22 $ L=\max_{i\bmod 2=0}w_i,\qquad R=\min_{i\bmod 2=1}w_i. $ 23 24 We need an integer $k$ such that $L \lt k \lt R$. Such an integer exists if and only if $L+2\le R$. 25 26 The time complexity is $O(n)$ per test case, and the extra space complexity is $O(1)$. 27 28 **Code** 29 30 ``` 31 #include <bits/stdc++.h> 32 using namespace std; 33 34 void work() { 35 int n; cin >> n; 36 long long L = 0, R = 1000000001LL; 37 38 for (int i = 1; i <= n; ++i) { 39 long long w; cin >> w; 40 if (i & 1) R = min(R, w); 41 else L = max(L, w); 42 } 43 44 cout << (n % 2 == 0 && L + 2 <= R ? "YES" : "NO") << '\n'; 45 } 46 47 int main() { 48 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 49 50 int T; cin >> T; 51 while (T--) work(); 52 53 return 0; 54 } 55 ``` 56 57 ## [2250B - String Construction](/contest/2250/problem/B "Codeforces Round 1112 (Div. 2)") 58 59 * Idea:[_MCYYDS_](/profile/_MCYYDS_ "Grandmaster _MCYYDS_") 60 * Solution:[_MCYYDS_](/profile/_MCYYDS_ "Grandmaster _MCYYDS_") 61 62 **Hint 1** 63 64 Partition the string into maximal blocks of equal characters. How does the number of blocks determine the number of adjacent equal pairs? 65 66 **Solution** 67 68 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 69 70 $ \sum_{i=1}^{r}(l_i-1)=n-r. $ 71 72 Therefore, we need to construct a string with exactly $r=n-k$ blocks. 73 74 Because $k \lt 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. 75 76 Now assume $r\ge2$. Let the block characters alternate, starting with $\mathtt{0}$. The numbers of $\mathtt{0}$-blocks and $\mathtt{1}$-blocks are 77 78 $ r_0=\left\lceil\frac r2\right\rceil,\qquad r_1=\left\lfloor\frac r2\right\rfloor. $ 79 80 We want the total numbers of the two characters to be 81 82 $ c_0=\left\lceil\frac n2\right\rceil,\qquad c_1=\left\lfloor\frac n2\right\rfloor. $ 83 84 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$. 85 86 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. 87 88 The time complexity is $O(n)$ per test case and $O(\sum n)$ in total. The space complexity is $O(n)$. 89 90 **Code** 91 92 ``` 93 #include <bits/stdc++.h> 94 using namespace std; 95 96 void work() { 97 int n, k; cin >> n >> k; 98 99 if (n > 1 && k == n - 1) { 100 cout << -1 << '\n'; 101 return; 102 } 103 104 k = n - k; 105 int c0 = (n + 1) / 2, c1 = n / 2; 106 107 for (int i = 1; i <= k; ++i) { 108 if (i & 1) { 109 if (i + 2 > k) { 110 while (c0--) cout << 0; 111 } 112 else { 113 --c0; 114 cout << 0; 115 } 116 } 117 else { 118 if (i + 2 > k) { 119 while (c1--) cout << 1; 120 } 121 else { 122 --c1; 123 cout << 1; 124 } 125 } 126 } 127 cout << '\n'; 128 } 129 130 int main() { 131 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 132 133 int T; cin >> T; 134 while (T--) work(); 135 136 return 0; 137 } 138 ``` 139 140 ## [2249A - Rank Subsequence](/contest/2249/problem/A "Codeforces Round 1112 (Div. 1)") 141 142 * Idea:[aaa_Pigeon2](/profile/aaa_Pigeon2 "International Grandmaster aaa_Pigeon2") 143 * Solution:[aaa_Pigeon2](/profile/aaa_Pigeon2 "International Grandmaster aaa_Pigeon2") 144 145 **Hint 1** 146 147 An element's rank from the right depends on both its position in the retained subsequence and the subsequence's final length. 148 149 **Hint 2** 150 151 Enumerate the final retained length $m$. Once $m$ is fixed, the condition for every position in the subsequence is fixed. 152 153 **Solution** 154 155 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$. 156 157 Therefore, we enumerate the final length $m$. 158 159 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 160 161 $ j\notin[l_i,r_i] $ 162 163 and 164 165 $ m-j+1\notin[u_i,v_i]. $ 166 167 Whenever the current element satisfies both conditions, choose it immediately. 168 169 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. 170 171 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$. 172 173 The time complexity is $O(n^2)$ per test case, and the space complexity is $O(n)$. 174 175 **Code** 176 177 ``` 178 #include <bits/stdc++.h> 179 using namespace std; 180 181 const int N = 5000; 182 183 int n; 184 int l[N + 10], r[N + 10], u[N + 10], v[N + 10]; 185 186 bool check(int m) { 187 int j = 1; 188 189 for (int i = 1; i <= n && j <= m; ++i) { 190 int x = m - j + 1; 191 if ((j < l[i] || j > r[i]) && (x < u[i] || x > v[i])) ++j; 192 } 193 194 return j == m + 1; 195 } 196 197 void work() { 198 cin >> n; 199 for (int i = 1; i <= n; ++i) cin >> l[i] >> r[i] >> u[i] >> v[i]; 200 201 for (int m = n; m >= 1; --m) { 202 if (!check(m)) continue; 203 cout << m << '\n'; 204 return; 205 } 206 207 cout << 0 << '\n'; 208 } 209 210 int main() { 211 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 212 213 int T; cin >> T; 214 while (T--) work(); 215 216 return 0; 217 } 218 ``` 219 220 ## [2249B - Permutation Cuts](/contest/2249/problem/B "Codeforces Round 1112 (Div. 1)") 221 222 * Idea:[aaa_Pigeon2](/profile/aaa_Pigeon2 "International Grandmaster aaa_Pigeon2") 223 * Solution:[aaa_Pigeon2](/profile/aaa_Pigeon2 "International Grandmaster aaa_Pigeon2") 224 225 **Hint 1** 226 227 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. 228 229 **Hint 2** 230 231 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. 232 233 **Hint 3** 234 235 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. 236 237 **Solution** 238 239 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$. 240 241 Now consider the position of $n$. For cut $i$: 242 243 * If $n$ lies on the right, then $a_i$ is the maximum of the prefix on the left. 244 * If $n$ lies on the left, then $a_i$ is the maximum of the suffix on the right. 245 246 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. 247 248 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. 249 250 After fixing $c$, merge 251 252 $ a_1,a_2,\ldots,a_c $ 253 254 with the reversed right part 255 256 $ a_{n-1},a_{n-2},\ldots,a_{c+1} $ 257 258 to obtain one non-decreasing sequence. Process its $i$-th value $x$: 259 260 * 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$. 261 * Otherwise, we may assign any unused value smaller than $x$. Since $i-1$ values have already been used, there are $x-i+1$ choices. 262 263 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. 264 265 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)$. 266 267 **Code** 268 269 ``` 270 #include <bits/stdc++.h> 271 using namespace std; 272 273 const int N = 1000000; 274 const int mod = 998244353; 275 276 int n; 277 int a[N + 10], vis[N + 10]; 278 bool pre[N + 10], suf[N + 10]; 279 280 void work() { 281 cin >> n; 282 for (int i = 1; i < n; ++i) cin >> a[i]; 283 a[n] = 0; 284 285 for (int i = 1; i < n; ++i) { 286 if (a[i] != n) continue; 287 cout << 0 << '\n'; 288 return; 289 } 290 291 pre[0] = 1; 292 for (int i = 1; i < n; ++i) pre[i] = pre[i - 1] && a[i] >= a[i - 1]; 293 suf[n] = 1; 294 for (int i = n - 1; i >= 1; --i) suf[i] = suf[i + 1] && a[i] >= a[i + 1]; 295 296 long long ans = 0; 297 for (int cut = 0; cut < n; ++cut) { 298 if (!pre || !suf[cut + 1]) continue; 299 if (cut > 0 && cut < n - 1 && a[cut] == a[cut + 1]) continue; 300 301 vector<int> l, r; 302 for (int i = 1; i <= cut; ++i) l.push_back(a[i]); 303 for (int i = cut + 1; i < n; ++i) r.push_back(a[i]); 304 reverse(r.begin(), r.end()); 305 306 memset(vis, 0, sizeof(int) * (n + 1)); 307 int x = 0, y = 0, used = 0; 308 long long ways = 1; 309 310 while (x < (int)l.size() || y < (int)r.size()) { 311 int w; 312 if (x == (int)l.size()) w = r[y++]; 313 else if (y == (int)r.size()) w = l[x++]; 314 else if (l[x] < r[y]) w = l[x++]; 315 else if (l[x] > r[y]) w = r[y++]; 316 else { 317 cout << 0 << '\n'; 318 return; 319 } 320 321 if (!vis[w]) vis[w] = 1; 322 else if (w < used) ways = 0; 323 else ways = ways * (w - used) % mod; 324 ++used; 325 } 326 327 ans += ways; 328 } 329 330 cout << ans % mod << '\n'; 331 } 332 333 int main() { 334 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 335 336 int T; cin >> T; 337 while (T--) work(); 338 339 return 0; 340 } 341 ``` 342 343 ## [2249C - Double-Rift Dial](/contest/2249/problem/C "Codeforces Round 1112 (Div. 1)") 344 345 * Idea:[aaa_Pigeon2](/profile/aaa_Pigeon2 "International Grandmaster aaa_Pigeon2") 346 * Solution:[aaa_Pigeon2](/profile/aaa_Pigeon2 "International Grandmaster aaa_Pigeon2") 347 348 **Hint 1** 349 350 Duplicate the permutation so that the cyclic sequence starting at any position becomes an ordinary contiguous segment of the duplicated array. 351 352 **Hint 2** 353 354 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. 355 356 **Hint 3** 357 358 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. 359 360 **Solution** 361 362 Checking every prefix separately for every starting position would introduce an additional factor of $n$. Instead, duplicate the permutation and define 363 364 $ q_i=p_{((i-1)\bmod n)+1}. $ 365 366 For a starting position $l$, the successive cyclic prefixes become the ordinary segments $[l,l],[l,l+1],\ldots,[l,l+n-1]$. 367 368 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 369 370 $ L=\max(1,r-n+1),\qquad R=\min(r,n). $ 371 372 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 373 374 $ \Delta=1-[x-1\text{ has already appeared}]-[x+1\text{ has already appeared}]. $ 375 376 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. 377 378 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$. 379 380 Therefore, inserting $x$ requires only three range additions: 381 382 1. Add $1$ to $[L,R]$. 383 2. If $x-1$ exists, subtract $1$ from $[L,\min(R,\operatorname{last}_{x-1})]$. 384 3. If $x+1$ exists, subtract $1$ from $[L,\min(R,\operatorname{last}_{x+1})]$. 385 386 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. 387 388 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)$. 389 390 **Code** 391 392 ``` 393 #include <bits/stdc++.h> 394 using namespace std; 395 396 const int N = 200000; 397 const int inf = 1000000000; 398 399 int n; 400 int p[N + 10], last[N + 10]; 401 int mx[4 * N + 10], lazy[4 * N + 10]; 402 403 void apply(int u, int v) { 404 mx[u] += v; 405 lazy[u] += v; 406 } 407 408 void push(int u) { 409 if (!lazy[u]) return; 410 apply(u << 1, lazy[u]); 411 apply(u << 1 | 1, lazy[u]); 412 lazy[u] = 0; 413 } 414 415 void add(int u, int l, int r, int ql, int qr, int v) { 416 if (ql <= l && r <= qr) { 417 apply(u, v); 418 return; 419 } 420 421 push(u); 422 int mid = (l + r) >> 1; 423 if (ql <= mid) add(u << 1, l, mid, ql, qr, v); 424 if (qr > mid) add(u << 1 | 1, mid + 1, r, ql, qr, v); 425 mx[u] = max(mx[u << 1], mx[u << 1 | 1]); 426 } 427 428 void add(int l, int r, int v) { 429 if (l <= r) add(1, 1, n, l, r, v); 430 } 431 432 int find_bad(int u, int l, int r) { 433 if (l == r) return l; 434 435 push(u); 436 int mid = (l + r) >> 1; 437 if (mx[u << 1] > 2) return find_bad(u << 1, l, mid); 438 return find_bad(u << 1 | 1, mid + 1, r); 439 } 440 441 void del(int u, int l, int r, int x) { 442 if (l == r) { 443 mx[u] = -inf; 444 lazy[u] = 0; 445 return; 446 } 447 448 push(u); 449 int mid = (l + r) >> 1; 450 if (x <= mid) del(u << 1, l, mid, x); 451 else del(u << 1 | 1, mid + 1, r, x); 452 mx[u] = max(mx[u << 1], mx[u << 1 | 1]); 453 } 454 455 void work() { 456 cin >> n; 457 for (int i = 1; i <= n; ++i) cin >> p[i]; 458 459 memset(last, 0, sizeof(int) * (n + 2)); 460 memset(mx, 0, sizeof(int) * (4 * n + 5)); 461 memset(lazy, 0, sizeof(int) * (4 * n + 5)); 462 463 int ans = n; 464 for (int r = 1; r < 2 * n; ++r) { 465 int L = max(1, r - n + 1), R = min(r, n); 466 int x = p[(r - 1) % n + 1]; 467 468 add(L, R, 1); 469 if (x > 1 && last[x - 1] >= L) add(L, min(R, last[x - 1]), -1); 470 if (x < n && last[x + 1] >= L) add(L, min(R, last[x + 1]), -1); 471 last[x] = r; 472 473 while (mx[1] > 2) { 474 int x = find_bad(1, 1, n); 475 del(1, 1, n, x); 476 --ans; 477 } 478 } 479 480 cout << ans << '\n'; 481 } 482 483 int main() { 484 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 485 486 int T; cin >> T; 487 while (T--) work(); 488 489 return 0; 490 } 491 ``` 492 493 ## [2249D - Xor Permutation Matrix](/contest/2249/problem/D "Codeforces Round 1112 (Div. 1)") 494 495 * Idea:[aaa_Pigeon2](/profile/aaa_Pigeon2 "International Grandmaster aaa_Pigeon2") 496 * Solution:[aaa_Pigeon2](/profile/aaa_Pigeon2 "International Grandmaster aaa_Pigeon2") 497 498 **Hint 1** 499 500 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. 501 502 **Hint 2** 503 504 We need many values $h$ satisfying 505 506 $ \{0,1,\ldots,n-1\}\mathbin{\operatorname{xor}}h=\{0,1,\ldots,n-1\}. $ 507 508 How large is the XOR stabilizer of this set? 509 510 **Hint 3** 511 512 When $n$ is a power of two, pair the values as $y\leftrightarrow y\oplus x$, and place several complete pairs at odd positions. 513 514 **Solution** 515 516 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 517 518 $ d_i(j)=A_{i,j}\oplus A_{i+1,j}. $ 519 520 The condition on every adjacent $2\times2$ submatrix implies 521 522 $ d_i(j+1)=d_i(j)\oplus x. $ 523 524 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$. 525 526 Let $L=\operatorname{lowbit}(n)$. The XOR stabilizer of $S$ is exactly 527 528 $ \{0,1,\ldots,L-1\}. $ 529 530 Every value smaller than $L$ merely permutes elements within blocks of length $L$. Conversely, write $h=gL+r$, where $0\le r \lt 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$. 531 532 The necessary condition is therefore 533 534 $ \operatorname{lowbit}(n)\ge\left\lceil\frac n2\right\rceil. $ 535 536 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 \gt 0$. 537 538 We now describe the construction. 539 540 If $x=0$, set 541 542 $ A_{i,j}=i\oplus j. $ 543 544 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$. 545 546 Now assume $x \gt 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 547 548 $ |E|=|O|=\frac n2,\qquad E\oplus x=E,\qquad O\oplus x=O. $ 549 550 Construct a permutation $p$ by placing the elements of $E$ at even positions and the elements of $O$ at odd positions. Then define 551 552 $ A_{i,j}=p_i\oplus p_j\oplus\bigl((i\bmod2)(j\bmod2)x\bigr). $ 553 554 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. 555 556 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$. 557 558 The output contains $n^2$ numbers, so the time complexity is $O(n^2)$, and the extra space complexity is $O(n)$. 559 560 **Code** 561 562 ``` 563 #include <bits/stdc++.h> 564 using namespace std; 565 566 const int N = 2500; 567 568 int n, x; 569 int vis[N + 10], in_o[N + 10], e[N + 10], o[N + 10], a[N + 10]; 570 pair<int, int> p[N + 10]; 571 572 bool check(int v) { 573 return (v & (v - 1)) == 0; 574 } 575 576 void work() { 577 cin >> n >> x; 578 579 if (!check(n) || (x && n < 4)) { 580 cout << -1 << '\n'; 581 return; 582 } 583 584 if (!x) { 585 for (int i = 0; i < n; ++i) { 586 for (int j = 0; j < n; ++j) { 587 cout << (i ^ j) << (j + 1 == n ? '\n' : ' '); 588 } 589 } 590 return; 591 } 592 593 for (int i = 0; i <= n; ++i) vis[i] = in_o[i] = e[i] = o[i] = a[i] = 0; 594 595 int cnt = 0; 596 for (int i = 0; i < n; ++i) { 597 if (vis[i]) continue; 598 int j = i ^ x; 599 vis[i] = vis[j] = 1; 600 p[++cnt] = {i, j}; 601 } 602 603 for (int i = 1; i <= n / 4; ++i) in_o[p[i].first] = in_o[p[i].second] = 1; 604 605 int ec = 0, oc = 0; 606 for (int i = 0; i < n; ++i) { 607 if (in_o[i]) o[++oc] = i; 608 else e[++ec] = i; 609 } 610 611 ec = oc = 0; 612 for (int i = 0; i < n; ++i) { 613 if (i & 1) a[i] = o[++oc]; 614 else a[i] = e[++ec]; 615 } 616 617 for (int i = 0; i < n; ++i) { 618 for (int j = 0; j < n; ++j) { 619 int v = a[i] ^ a[j]; 620 if ((i & 1) && (j & 1)) v ^= x; 621 cout << v << (j + 1 == n ? '\n' : ' '); 622 } 623 } 624 } 625 626 int main() { 627 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 628 629 int T; cin >> T; 630 while (T--) work(); 631 632 return 0; 633 } 634 ``` 635 636 ## [2249E1 - String (Easy Version)](/contest/2249/problem/E1 "Codeforces Round 1112 (Div. 1)") 637 638 * Idea:[131241](/profile/131241 "Specialist 131241") 639 * Solution:[131241](/profile/131241 "Specialist 131241") 640 641 **Hint 1** 642 643 Treat a prefix of length $k^i$ as one block. How can it be decomposed into smaller blocks? 644 645 **Hint 2** 646 647 Adding the same value to every character modulo $k$ produces only finitely many translated versions of the pattern-matching problem. 648 649 **Hint 3** 650 651 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. 652 653 **Solution** 654 655 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 656 657 $ B_{i,j}=B_{i-1,j}B_{i-1,j+1}\cdots B_{i-1,j+k-1}, $ 658 659 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. 660 661 For the current pattern $t$, maintain the following information for every block: 662 663 * The number of occurrences of $t$ entirely inside the block. 664 * A prefix of the block of length at most $n-1$. 665 * A suffix of the block of length at most $n-1$. 666 667 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. 668 669 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. 670 671 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. 672 673 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 674 675 $ O\left(\sum n\cdot k^2+qk^2\log_k V\right), $ 676 677 where $V=10^{17}$. The space complexity is $O(n+k^2\log_k V)$. 678 679 **Code** 680 681 ``` 682 #include <bits/stdc++.h> 683 using namespace std; 684 685 struct node { 686 long long v = 0; 687 bool b = 0; 688 string l = "", r = ""; 689 int l1, r1; 690 }; 691 692 int n, k; 693 int fai[2000005]; 694 long long T, ql, qr, trans[10][10]; 695 long long ma, L, R; 696 node a[66][10], ans; 697 string pl[10], pr[10], s; 698 699 void make_fai() { 700 for (int i = 1; i <= n; ++i) s[i] ^= 48; 701 702 int l = 0; 703 for (int i = 2; i <= n; ++i) { 704 while (l && s[l + 1] != s[i]) l = fai[l]; 705 l += s[l + 1] == s[i]; 706 fai[i] = l; 707 } 708 } 709 710 int val(string x) { 711 int l = 0, res = 0; 712 713 for (int i = 0; i < (int)x.size(); ++i) { 714 while (l && s[l + 1] != x[i]) l = fai[l]; 715 l += s[l + 1] == x[i]; 716 if (l == n) ++res; 717 } 718 719 return res; 720 } 721 722 node add(node &x, node &y) { 723 node res; 724 725 if (x.b && y.b) { 726 res.b = 1; 727 res.l1 = x.l1; 728 res.r1 = y.r1; 729 res.v = x.v + y.v + trans[x.r1][y.l1]; 730 return res; 731 } 732 733 if (x.b) x.l = pl[x.l1], x.r = pr[x.r1]; 734 if (y.b) y.l = pl[y.l1], y.r = pr[y.r1]; 735 res.v = x.v + y.v + val(x.r + y.l); 736 res.l = x.l; 737 738 if ((int)res.l.size() < n - 1) { 739 int t = min(n - 1 - (int)res.l.size(), (int)y.l.size()); 740 res.l += y.l.substr(0, t); 741 } 742 743 res.r = y.r; 744 if ((int)res.r.size() < n - 1) { 745 int t = min(n - 1 - (int)res.r.size(), (int)x.r.size()); 746 res.r = x.r.substr(x.r.size() - t, t) + res.r; 747 } 748 749 return res; 750 } 751 752 void init(long long x) { 753 bool done = 0; 754 755 for (long long cur = 1, i = 0; cur <= x; cur *= k, ++i) { 756 ma = i; 757 L = 0, R = cur; 758 759 if (i == 0) { 760 for (int j = 0; j < k; ++j) { 761 if (n == 1) { 762 a[0][j].v = j == s[1]; 763 a[0][j].b = 0; 764 a[0][j].l = a[0][j].r = ""; 765 } 766 else { 767 a[0][j].v = 0; 768 a[0][j].b = 0; 769 a[0][j].l = a[0][j].r = ""; 770 a[0][j].l += (char)j; 771 a[0][j].r = a[0][j].l; 772 } 773 } 774 } 775 else { 776 for (int j = 0; j < k; ++j) { 777 node cur; 778 for (int t = 0; t < k; ++t) { 779 if (!cur.v && !cur.b && cur.l.empty()) cur = a[i - 1][(j + t) % k]; 780 else cur = add(cur, a[i - 1][(j + t) % k]); 781 } 782 a[i][j] = cur; 783 } 784 } 785 786 if (!done && cur >= n - 1) { 787 done = 1; 788 for (int j = 0; j < k; ++j) { 789 pl[j] = a[i][j].l; 790 pr[j] = a[i][j].r; 791 a[i][j].b = 1; 792 a[i][j].l1 = a[i][j].r1 = j; 793 a[i][j].l = a[i][j].r = ""; 794 } 795 for (int j = 0; j < k; ++j) { 796 for (int t = 0; t < k; ++t) trans[j][t] = val(pr[j] + pl[t]); 797 } 798 } 799 } 800 } 801 802 void calc(int dep, int st, long long l, long long r) { 803 if (r <= ql || l > qr) return; 804 805 if (ql <= l && r - 1 <= qr) { 806 ans = add(ans, a[dep][st]); 807 return; 808 } 809 810 node cur; 811 long long len = r - l; 812 813 for (int i = 0; i < k; ++i) { 814 long long nl = l + len / k * i, nr = nl + len / k; 815 816 if (ql <= nl && nr - 1 <= qr) { 817 if (!cur.v && !cur.b && cur.l.empty()) cur = a[dep - 1][(st + i) % k]; 818 else cur = add(cur, a[dep - 1][(st + i) % k]); 819 continue; 820 } 821 822 if (cur.v || cur.b || !cur.l.empty()) { 823 ans = add(ans, cur); 824 cur.v = 0, cur.b = 0; 825 cur.l = cur.r = ""; 826 } 827 calc(dep - 1, (st + i) % k, nl, nr); 828 } 829 830 if (cur.v || cur.b || !cur.l.empty()) ans = add(ans, cur); 831 } 832 833 int main() { 834 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 835 836 cin >> k >> T; 837 while (T--) { 838 cin >> ql >> qr >> n >> s; 839 s = " " + s + "!"; 840 841 make_fai(); 842 init(qr); 843 ++ma, R *= k; 844 845 ans.v = 0, ans.b = 0; 846 ans.l = ans.r = ""; 847 calc(ma, 0, L, R); 848 cout << ans.v << '\n'; 849 } 850 851 return 0; 852 } 853 ``` 854 855 ## [2249E2 - String (Hard Version)](/contest/2249/problem/E2 "Codeforces Round 1112 (Div. 1)") 856 857 * Idea:[131241](/profile/131241 "Specialist 131241") 858 * Solution:[131241](/profile/131241 "Specialist 131241") 859 860 **Hint 1** 861 862 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. 863 864 **Hint 2** 865 866 Let 867 868 $ d_i=(t_i-t_{i-1}+k)\bmod k. $ 869 870 Inside a complete block, $d_i$ is always $1$. Therefore, all positions with $d_i\ne1$ must have the same residue modulo $k$. 871 872 **Hint 3** 873 874 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$. 875 876 **Solution** 877 878 First examine the block structure of the infinite string $s$. Every block of length $k$ is a cyclic shift of 879 880 $ \mathtt{012\ldots(k-1)}. $ 881 882 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$. 883 884 To determine the alignment, consider the adjacent differences of $t$ modulo $k$: 885 886 $ d_i=(t_i-t_{i-1}+k)\bmod k. $ 887 888 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. 889 890 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. 891 892 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$. 893 894 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. 895 896 We are left with occurrence queries for patterns of length $1$ or $2$. 897 898 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. 899 900 For a pattern of length $2$, precompute 901 902 $ f_{p,q,x,y}, $ 903 904 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. 905 906 The total time complexity is 907 908 $ O\left(qk\log_k V+\sum n+k^3\log_k V+k\log_k^2V\right), $ 909 910 where $V=10^{17}$. 911 912 **Code** 913 914 ``` 915 #include<bits/stdc++.h> 916 #define int long long 917 using namespace std; 918 int lg; 919 int q,L,R,n,k,d[10000005],t[100],b[100]; 920 char c[10000005],s[10000005]; 921 struct node{ 922 int f[65][65]; 923 }sum[65][65]; 924 node merge(node a,node b,int v=1){ 925 for(int i=0;i<k;i++){ 926 for(int j=0;j<k;j++){ 927 a.f[(i+v)%k][(j+v)%k]+=b.f[i][j]; 928 } 929 } 930 return a; 931 } 932 int calc(int x){ 933 int sum=0; 934 while(x){ 935 sum+=x%k; 936 x=x/k; 937 } 938 return sum%k; 939 } 940 int sp[70]; 941 int gs(int r,int x,int y){ 942 // Count occurrences of the pattern "xy" in the range [0, r]. 943 r++; 944 int cnt=0,xnow=0,ans=0,lowbit=0; 945 for(int i=0;i<=lg;i++){ 946 sp[i]=r%k;r/=k; 947 } 948 for(int i=lg;i>=0;i--){ 949 int j=sp[i]; 950 if(!j) continue; 951 ans+=sum[i][j].f[(x+(k-1)*cnt)%k][(y+(k-1)*cnt)%k]; 952 if(xnow){ 953 int px=(cnt-1+lowbit*(k-1))%k,py=cnt%k; 954 if(px==x&&py==y){ 955 ans++; 956 } 957 } 958 xnow+=b[i]*j; 959 cnt+=j; 960 lowbit=i; 961 } 962 return ans; 963 } 964 int gs(int r,int x){ 965 // Count occurrences of the pattern "x" in the range [0, r]. 966 r++; 967 int sum=r/k,pl=r/k*k,y=calc(pl); 968 while(pl<r){ 969 if(y==x){ 970 sum++; 971 break; 972 } 973 pl++; 974 y++; 975 y>=k?y-=k:0; 976 } 977 return sum; 978 } 979 void print(char c){ 980 if(c<10){ 981 cout<<char(c+'0'); 982 }else{ 983 cout<<char(c+'a'-10); 984 } 985 } 986 int ans=0; 987 void solve(int l,int r,int n){ 988 // Compute the answer recursively. 989 if(l>r){ 990 return ; 991 } 992 for(int i=0;i<k;i++){ 993 t[i]=0; 994 } 995 if(n<=2){ 996 // For length at most 2, use prefix-count differences directly. 997 if(n==2){ 998 int pl=c[0],pr=c[1]; 999 int sum=gs(r,pl,pr)-gs(l,pl,pr); 1000 ans+=sum; 1001 return ; 1002 }else{ 1003 int sum=0; 1004 sum=gs(r,c[0])-gs(l-1,c[0]); 1005 ans+=sum; 1006 return ; 1007 } 1008 } 1009 int cnt=0; 1010 for(int i=1;i<n;i++){ 1011 d[i]=(c[i]-c[i-1]+k)%k; 1012 if(d[i]!=1){ 1013 if(!t[i%k]) cnt++; 1014 t[i%k]=1; 1015 } 1016 } 1017 if(cnt>1){ 1018 // If more than one residue occurs, the pattern cannot appear. 1019 return ; 1020 } 1021 int m=0,pl=k,pr=k,p=0; 1022 if(cnt){ 1023 // At least one adjacent difference is not 1. 1024 for(int i=1;i<n;i++){ 1025 if(d[i]!=1) p=i%k; 1026 } 1027 if(p){ 1028 pl=p; 1029 s[m++]=(c[p-1]+1)%k; 1030 } 1031 for(int i=p;i<n;i+=k){ 1032 if(i+k-1>=n) pr=n-i; 1033 s[m++]=c[i]; 1034 } 1035 1036 // Handle the two partial boundary blocks separately. 1037 int bl=(r/k)*k,br=(l/k+1)*k-1; 1038 if(br-l+1<pl) l=l/k+1; 1039 else l=l/k; 1040 if(r-bl+1<pr) r=r/k-1; 1041 else r=r/k; 1042 1043 for(int i=0;i<m;i++) c[i]=s[i]; 1044 solve(l,r,m); 1045 }else{ 1046 // Every adjacent difference is 1. 1047 int szl=(l/k+1)*k-l,szr=r-(r/k)*k+1,L,R; 1048 if(n<=k){ 1049 int x=c[0]; 1050 for(int i=0;i+n-1<k;i++){ 1051 c[0]=(x-i+k)%k; 1052 // Handle the two partial boundary blocks separately. 1053 pl=k-i,pr=i+n; 1054 if(szl<pl) L=l/k+1; 1055 else L=l/k; 1056 if(szr<pr) R=r/k-1; 1057 else R=r/k; 1058 solve(L,R,1); 1059 } 1060 } 1061 for(int i=0;i<n;i++){ 1062 s[i]=c[i]; 1063 } 1064 for(int i=0;i<min(n-1,k);i++){ 1065 // Handle the two partial boundary blocks separately. 1066 pl=i+1,pr=n-1-i; 1067 if(pr>k) continue; 1068 if(szl<pl) L=l/k+1; 1069 else L=l/k; 1070 if(szr<pr) R=r/k-1; 1071 else R=r/k; 1072 c[0]=c[1]=s[i+1]; 1073 solve(L,R,2); 1074 } 1075 } 1076 } 1077 char change(int x){ 1078 if(0<=x&&x<=9) return x+'0'; 1079 if(10<=x&&x<=35) return x-10+'A'; 1080 if(36<=x&&x<=61) return x-36+'a'; 1081 } 1082 int change(char x){ 1083 if('0'<=x&&x<='9') return x-'0'; 1084 if('A'<=x&&x<='Z') return x+10-'A'; 1085 if('a'<=x&&x<='z') return x+36-'a'; 1086 } 1087 signed main(){ 1088 ios::sync_with_stdio(0); 1089 cin.tie(0);cout.tie(0); 1090 cin>>k>>q; 1091 1092 // sum[i][j] stores counts of length-2 substrings in the first j * k^i characters. 1093 b[0]=1;lg=0; 1094 for(int i=1;i<=k;i++){ 1095 for(int j=1;j<i;j++){ 1096 sum[0][i].f[j-1][j]=1; 1097 } 1098 } 1099 for(int p=1;p;p++){ 1100 b[p]=b[p-1]*k; 1101 lg++; 1102 if(b[p]>1e17){ 1103 break; 1104 } 1105 sum[p][1]=sum[p-1][k]; 1106 // Concatenate the k shifted blocks. 1107 for(int i=2;i<=k;i++){ 1108 sum[p][i]=merge(sum[p][i-1],sum[p-1][k],i-1); 1109 // Count substrings that cross a block boundary directly. 1110 sum[p][i].f[calc(b[p]*(i-1)-1)][calc(b[p]*(i-1))]++; 1111 } 1112 } 1113 1114 while(q--){ 1115 cin>>L>>R>>n; 1116 cin>>c; 1117 for(int i=0;i<n;i++){ 1118 c[i]=change(c[i]); 1119 } 1120 solve(L,R,n); 1121 cout<<ans<<endl; 1122 ans=0; 1123 } 1124 return 0; 1125 } 1126 ``` 1127 1128 ## [2249F - Even Simple Path](/contest/2249/problem/F "Codeforces Round 1112 (Div. 1)") 1129 1130 * Idea:[aaa_Pigeon2](/profile/aaa_Pigeon2 "International Grandmaster aaa_Pigeon2") 1131 * Solution:[aaa_Pigeon2](/profile/aaa_Pigeon2 "International Grandmaster aaa_Pigeon2") 1132 1133 **Hint 1** 1134 1135 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? 1136 1137 **Hint 2** 1138 1139 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. 1140 1141 **Hint 3** 1142 1143 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. 1144 1145 **Solution** 1146 1147 The 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. 1148 1149 First, consider the degree pattern of a simple path from vertex $1$ to vertex $n$: 1150 1151 * vertices $1$ and $n$ have degree $1$ in the path; 1152 * every other used vertex has degree $2$; 1153 * every unused vertex has degree $0$. 1154 1155 We will build an auxiliary graph where: 1156 1157 * an unused vertex corresponds to one internal matching edge; 1158 * a used internal vertex must match both of its copies to other vertices; 1159 * vertices $1$ and $n$ have only one copy each, so they contribute exactly one path edge. 1160 1161 Then a perfect matching in the auxiliary graph will describe a path in the original graph. 1162 1163 --- 1164 1165 Let the original graph be $G=(V,E)$. 1166 1167 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 1168 1169 $ V'=\{L(v)\mid v\ne n\}\cup\{R(v)\mid v\ne 1\} $ 1170 1171 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$. 1172 1173 Also, the deleted copies are in different layers. This is what forces the restored path to have even length. 1174 1175 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$. 1176 1177 For every internal vertex $v\notin{1,n}$, add the cross-layer edge $(L(v),R(v))$ with weight $M$. 1178 1179 Here $M$ is a sufficiently large constant, for example any $M \gt |V'|$. 1180 1181 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. 1182 1183 The choice $M \gt |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. 1184 1185 --- 1186 1187 ## Meaning of a Perfect Matching 1188 1189 Consider a perfect matching $S$ of $G'$. 1190 1191 For an internal vertex $v\notin{1,n}$, both $L(v)$ and $R(v)$ must be matched. 1192 1193 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. 1194 1195 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$. 1196 1197 Vertices $1$ and $n$ have only one copy each and have no cross-layer edge, so they naturally have degree $1$. 1198 1199 Thus the selected same-layer edges map to a subgraph of the original graph in which: 1200 1201 * vertices $1$ and $n$ have degree $1$; 1202 * every other vertex has degree $0$ or $2$. 1203 1204 So this subgraph consists of one path from $1$ to $n$ and possibly several cycles. 1205 1206 We now prove the construction in both directions and then explain why maximum weight removes the cycles and minimizes the path length. 1207 1208 --- 1209 1210 ### Proof 1: Every Even Simple Path Gives a Perfect Matching 1211 1212 Suppose we have an even-length simple path 1213 1214 $ p_0=1,p_1,p_2,\ldots,p_L=n $ 1215 1216 where $2\mid L$. 1217 1218 Choose edges along this path alternately: 1219 1220 * for the first edge $(p_0,p_1)$, choose $(L(p_0),L(p_1))$; 1221 * for the second edge $(p_1,p_2)$, choose $(R(p_1),R(p_2))$; 1222 * for the third edge, choose the corresponding left-layer edge; 1223 * for the fourth edge, choose the corresponding right-layer edge; 1224 * and so on. 1225 1226 Since $L$ is even, the last path edge $(p_{L-1},p_L)$ is chosen in the right layer, and $R(n)$ exists. 1227 1228 For every internal vertex $v$ not on the path, choose the cross-layer edge $(L(v),R(v))$. 1229 1230 Now every vertex of $G'$ is matched exactly once, so we have constructed a perfect matching. 1231 1232 --- 1233 1234 ### Proof 2: Every Perfect Matching Gives an Even Simple Path 1235 1236 Take any perfect matching of $G'$ and map all selected same-layer edges back to the original graph. 1237 1238 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. 1239 1240 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))$. 1241 1242 Therefore the original edges on the path must appear as 1243 1244 $ \text{left layer},\ \text{right layer},\ \text{left layer},\ \text{right layer},\ldots,\ \text{right layer} $ 1245 1246 So the number of original edges on this path is even. 1247 1248 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. 1249 1250 --- 1251 1252 ### Proof 3: A Maximum-Weight Perfect Matching Has No Extra Cycles 1253 1254 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. 1255 1256 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 1257 1258 $ k(M-1) $ 1259 1260 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. 1261 1262 This is still a valid perfect matching. The affected part now has total weight 1263 1264 $ kM $ 1265 1266 Since $kM \gt k(M-1)$, the matching weight increases, which contradicts maximality. 1267 1268 Therefore a maximum-weight perfect matching cannot produce extra cycles. It restores exactly one even-length simple path from $1$ to $n$. 1269 1270 --- 1271 1272 ### Proof 4: The Restored Path Is Shortest 1273 1274 In any perfect matching of $G'$, the number of matched edges is fixed. 1275 1276 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. 1277 1278 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. 1279 1280 --- 1281 1282 ## Finding the Matching and Restoring the Path 1283 1284 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. 1285 1286 The auxiliary graph has $2n-2$ vertices and at most $2m+n-2$ edges. The weighted blossom algorithm runs in $O(|V'|^3)$ time. 1287 1288 After computing the maximum-weight matching: 1289 1290 * if its size is not $|V'|/2$, output $-1$; 1291 * otherwise, take the symmetric difference between the matching edges and all cross-layer edges $(L(v),R(v))$ for $v\notin{1,n}$. 1292 1293 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. 1294 1295 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$. 1296 1297 **Code** 1298 1299 ``` 1300 #include <bits/stdc++.h> 1301 using namespace std; 1302 1303 const int N = 1000; 1304 const int V = 2 * N; 1305 const int B = 2 * V; 1306 const int inf = 0x3f3f3f3f; 1307 const int big = 10000; 1308 1309 struct edge { 1310 int u, v, w; 1311 }; 1312 1313 int n, m; 1314 int idL[N + 10], idR[N + 10], ori[V + 10]; 1315 int init_u[N + 10], init_v[N + 10], init_cnt; 1316 char sx[V + 10][V + 10]; 1317 vector<int> adj[V + 10]; 1318 1319 struct blossom_tree { 1320 int n, nx; 1321 edge g[B + 10][B + 10]; 1322 int lab[B + 10], match[B + 10], slack[B + 10], st[B + 10], pa[B + 10]; 1323 int flower_from[B + 10][V + 10], flower[B + 10][V + 10]; 1324 int S[B + 10], vis[B + 10], flower_cnt[B + 10], tmp[V + 10]; 1325 queue<int> q; 1326 1327 void init(int _n) { 1328 n = _n, nx = n; 1329 1330 for (int i = 0; i <= 2 * n + 2; ++i) { 1331 lab[i] = match[i] = slack[i] = st[i] = pa[i] = S[i] = vis[i] = 0; 1332 flower_cnt[i] = 0; 1333 for (int j = 0; j <= n; ++j) flower_from[i][j] = 0; 1334 } 1335 1336 for (int i = 1; i <= 2 * n + 2; ++i) { 1337 for (int j = 1; j <= 2 * n + 2; ++j) g[i][j] = {i, j, 0}; 1338 } 1339 } 1340 1341 void add_edge(int u, int v, int w) { 1342 if (u == v) return; 1343 1344 if (w > g[u][v].w) { 1345 g[u][v] = {u, v, w}; 1346 g[v][u] = {v, u, w}; 1347 } 1348 } 1349 1350 int e_delta(edge e) { 1351 return lab[e.u] + lab[e.v] - g[e.u][e.v].w * 2; 1352 } 1353 1354 void update_slack(int u, int x) { 1355 if (!slack[x] || e_delta(g[u][x]) < e_delta(g[slack[x]][x])) slack[x] = u; 1356 } 1357 1358 void set_slack(int x) { 1359 slack[x] = 0; 1360 1361 for (int u = 1; u <= n; ++u) { 1362 if (g[u][x].w && st[u] != x && S[st[u]] == 0) update_slack(u, x); 1363 } 1364 } 1365 1366 void q_push(int x) { 1367 if (x <= n) q.push(x); 1368 else { 1369 for (int i = 0; i < flower_cnt[x]; ++i) q_push(flower[x][i]); 1370 } 1371 } 1372 1373 void set_st(int x, int b) { 1374 st[x] = b; 1375 1376 if (x > n) { 1377 for (int i = 0; i < flower_cnt[x]; ++i) set_st(flower[x][i], b); 1378 } 1379 } 1380 1381 void reverse_flower(int b, int l, int r) { 1382 while (l < r) { 1383 swap(flower[b][l], flower[b][r]); 1384 ++l, --r; 1385 } 1386 } 1387 1388 void rotate_flower(int b, int pr) { 1389 int cnt = flower_cnt[b]; 1390 1391 for (int i = 0; i < cnt; ++i) tmp[i] = flower[b][(i + pr) % cnt]; 1392 for (int i = 0; i < cnt; ++i) flower[b][i] = tmp[i]; 1393 } 1394 1395 int get_pr(int b, int xr) { 1396 int pr = 0; 1397 1398 while (flower[b][pr] != xr) ++pr; 1399 1400 if (pr & 1) { 1401 reverse_flower(b, 1, flower_cnt[b] - 1); 1402 return flower_cnt[b] - pr; 1403 } 1404 1405 return pr; 1406 } 1407 1408 void set_match(int u, int v) { 1409 match[u] = g[u][v].v; 1410 1411 if (u > n) { 1412 edge e = g[u][v]; 1413 int xr = flower_from[u][e.u]; 1414 int pr = get_pr(u, xr); 1415 1416 for (int i = 0; i < pr; ++i) set_match(flower[u][i], flower[u][i ^ 1]); 1417 1418 set_match(xr, v); 1419 rotate_flower(u, pr); 1420 } 1421 } 1422 1423 void augment(int u, int v) { 1424 while (true) { 1425 int xnv = st[match[u]]; 1426 1427 set_match(u, v); 1428 1429 if (!xnv) return; 1430 1431 set_match(xnv, st[pa[xnv]]); 1432 u = st[pa[xnv]], v = xnv; 1433 } 1434 } 1435 1436 int get_lca(int u, int v) { 1437 static int tim = 0; 1438 ++tim; 1439 1440 while (u || v) { 1441 if (u) { 1442 if (vis[u] == tim) return u; 1443 1444 vis[u] = tim; 1445 u = st[match[u]]; 1446 1447 if (u) u = st[pa[u]]; 1448 } 1449 1450 swap(u, v); 1451 } 1452 1453 return 0; 1454 } 1455 1456 void add_blossom(int u, int lca, int v) { 1457 int b = n + 1; 1458 1459 while (b <= nx && st[b]) ++b; 1460 if (b > nx) ++nx; 1461 1462 lab[b] = 0, S[b] = 0, match[b] = match[lca]; 1463 flower_cnt[b] = 0; 1464 flower[b][flower_cnt[b]++] = lca; 1465 1466 for (int x = u, y; x != lca; x = st[pa[y]]) { 1467 flower[b][flower_cnt[b]++] = x; 1468 y = st[match[x]]; 1469 flower[b][flower_cnt[b]++] = y; 1470 q_push(y); 1471 } 1472 1473 reverse_flower(b, 1, flower_cnt[b] - 1); 1474 1475 for (int x = v, y; x != lca; x = st[pa[y]]) { 1476 flower[b][flower_cnt[b]++] = x; 1477 y = st[match[x]]; 1478 flower[b][flower_cnt[b]++] = y; 1479 q_push(y); 1480 } 1481 1482 set_st(b, b); 1483 1484 for (int x = 1; x <= nx; ++x) { 1485 g[b][x] = {b, x, 0}; 1486 g[x][b] = {x, b, 0}; 1487 } 1488 1489 for (int x = 1; x <= n; ++x) flower_from[b][x] = 0; 1490 1491 for (int i = 0; i < flower_cnt[b]; ++i) { 1492 int xs = flower[b][i]; 1493 1494 for (int x = 1; x <= nx; ++x) { 1495 if (g[xs][x].w && (!g[b][x].w || e_delta(g[xs][x]) < e_delta(g[b][x]))) { 1496 g[b][x] = g[xs][x]; 1497 g[x][b] = g[x][xs]; 1498 } 1499 } 1500 1501 for (int x = 1; x <= n; ++x) { 1502 if (flower_from[xs][x]) flower_from[b][x] = xs; 1503 } 1504 } 1505 1506 set_slack(b); 1507 } 1508 1509 void expand_blossom(int b) { 1510 for (int i = 0; i < flower_cnt[b]; ++i) set_st(flower[b][i], flower[b][i]); 1511 1512 int xr = flower_from[b][g[b][pa[b]].u]; 1513 int pr = get_pr(b, xr); 1514 1515 for (int i = 0; i < pr; i += 2) { 1516 int xs = flower[b][i]; 1517 int xns = flower[b][i + 1]; 1518 1519 pa[xs] = g[xns][xs].u; 1520 S[xs] = 1, S[xns] = 0; 1521 slack[xs] = 0; 1522 1523 set_slack(xns); 1524 q_push(xns); 1525 } 1526 1527 S[xr] = 1; 1528 pa[xr] = pa[b]; 1529 1530 for (int i = pr + 1; i < flower_cnt[b]; ++i) { 1531 int xs = flower[b][i]; 1532 1533 S[xs] = -1; 1534 set_slack(xs); 1535 } 1536 1537 st[b] = 0; 1538 } 1539 1540 bool on_found_edge(edge e) { 1541 int u = st[e.u], v = st[e.v]; 1542 1543 if (S[v] == -1) { 1544 pa[v] = e.u; 1545 S[v] = 1; 1546 1547 int nu = st[match[v]]; 1548 1549 slack[v] = slack[nu] = 0; 1550 S[nu] = 0; 1551 1552 q_push(nu); 1553 } 1554 else if (S[v] == 0) { 1555 int lca = get_lca(u, v); 1556 1557 if (!lca) { 1558 augment(u, v); 1559 augment(v, u); 1560 return true; 1561 } 1562 else add_blossom(u, lca, v); 1563 } 1564 1565 return false; 1566 } 1567 1568 bool matching() { 1569 for (int i = 1; i <= nx; ++i) S[i] = -1, slack[i] = 0; 1570 1571 while (!q.empty()) q.pop(); 1572 1573 for (int x = 1; x <= nx; ++x) { 1574 if (st[x] == x && !match[x]) { 1575 pa[x] = 0; 1576 S[x] = 0; 1577 q_push(x); 1578 } 1579 } 1580 1581 if (q.empty()) return false; 1582 1583 while (true) { 1584 while (!q.empty()) { 1585 int u = q.front(); q.pop(); 1586 if (S[st[u]] == 1) continue; 1587 1588 for (int v = 1; v <= n; ++v) { 1589 if (g[u][v].w && st[u] != st[v]) { 1590 if (!e_delta(g[u][v])) { 1591 if (on_found_edge(g[u][v])) return true; 1592 } 1593 else update_slack(u, st[v]); 1594 } 1595 } 1596 } 1597 1598 int d = inf; 1599 1600 for (int u = 1; u <= n; ++u) { 1601 if (S[st[u]] == 0) d = min(d, lab[u]); 1602 } 1603 1604 for (int b = n + 1; b <= nx; ++b) { 1605 if (st[b] == b && S[b] == 1) d = min(d, lab[b] / 2); 1606 } 1607 1608 for (int x = 1; x <= nx; ++x) { 1609 if (st[x] == x && slack[x]) { 1610 if (S[x] == -1) d = min(d, e_delta(g[slack[x]][x])); 1611 else if (S[x] == 0) d = min(d, e_delta(g[slack[x]][x]) / 2); 1612 } 1613 } 1614 1615 if (d == inf) return false; 1616 1617 for (int u = 1; u <= n; ++u) { 1618 if (S[st[u]] == 0) { 1619 if (lab[u] == d) return false; 1620 lab[u] -= d; 1621 } 1622 else if (S[st[u]] == 1) lab[u] += d; 1623 } 1624 1625 for (int b = n + 1; b <= nx; ++b) { 1626 if (st[b] == b) { 1627 if (S[b] == 0) lab[b] += d * 2; 1628 else if (S[b] == 1) lab[b] -= d * 2; 1629 } 1630 } 1631 1632 while (!q.empty()) q.pop(); 1633 1634 for (int x = 1; x <= nx; ++x) { 1635 if (st[x] == x && slack[x] && st[slack[x]] != x && !e_delta(g[slack[x]][x])) { 1636 if (on_found_edge(g[slack[x]][x])) return true; 1637 } 1638 } 1639 1640 for (int b = n + 1; b <= nx; ++b) { 1641 if (st[b] == b && S[b] == 1 && !lab[b]) expand_blossom(b); 1642 } 1643 } 1644 } 1645 1646 int solve() { 1647 nx = n; 1648 int cnt = 0, mx = 0; 1649 1650 for (int i = 0; i <= 2 * n + 2; ++i) { 1651 lab[i] = match[i] = slack[i] = pa[i] = S[i] = vis[i] = 0; 1652 st[i] = 0; 1653 flower_cnt[i] = 0; 1654 } 1655 1656 for (int i = 0; i <= n; ++i) st[i] = i; 1657 1658 for (int u = 1; u <= n; ++u) { 1659 for (int v = 1; v <= n; ++v) { 1660 flower_from[u][v] = (u == v ? u : 0); 1661 mx = max(mx, g[u][v].w); 1662 } 1663 } 1664 1665 for (int u = 1; u <= n; ++u) lab[u] = mx; 1666 1667 while (matching()) ++cnt; 1668 return cnt; 1669 } 1670 } blossom; 1671 1672 int new_node(int x, int &tot) { 1673 ori[tot + 1] = x; 1674 return ++tot; 1675 } 1676 1677 void toggle_edge(int u, int v) { 1678 if (u > v) swap(u, v); 1679 sx[u][v] ^= 1; 1680 } 1681 1682 void work() { 1683 cin >> n >> m; 1684 1685 memset(idL, -1, sizeof(idL)); 1686 memset(idR, -1, sizeof(idR)); 1687 1688 int tot = 0; 1689 1690 for (int i = 1; i <= n; ++i) { 1691 if (i != n) idL[i] = new_node(i, tot); 1692 } 1693 for (int i = 1; i <= n; ++i) { 1694 if (i != 1) idR[i] = new_node(i, tot); 1695 } 1696 1697 blossom.init(tot); 1698 1699 for (int i = 1; i <= m; ++i) { 1700 int u, v; cin >> u >> v; 1701 1702 if (idL[u] != -1 && idL[v] != -1) blossom.add_edge(idL[u], idL[v], big - 1); 1703 if (idR[u] != -1 && idR[v] != -1) blossom.add_edge(idR[u], idR[v], big - 1); 1704 } 1705 1706 init_cnt = 0; 1707 1708 for (int i = 2; i < n; ++i) { 1709 blossom.add_edge(idL[i], idR[i], big); 1710 init_u[++init_cnt] = idL[i], init_v[init_cnt] = idR[i]; 1711 } 1712 1713 int cnt = blossom.solve(); 1714 1715 if (cnt != tot / 2) { 1716 cout << -1 << '\n'; 1717 return; 1718 } 1719 1720 for (int i = 1; i <= tot; ++i) { 1721 adj[i].clear(); 1722 for (int j = 1; j <= tot; ++j) sx[i][j] = 0; 1723 } 1724 1725 for (int i = 1; i <= tot; ++i) { 1726 if (blossom.match[i] && i < blossom.match[i]) toggle_edge(i, blossom.match[i]); 1727 } 1728 1729 for (int i = 1; i <= init_cnt; ++i) toggle_edge(init_u[i], init_v[i]); 1730 1731 for (int i = 1; i <= tot; ++i) { 1732 for (int j = i + 1; j <= tot; ++j) { 1733 if (sx[i][j]) { 1734 adj[i].push_back(j); 1735 adj[j].push_back(i); 1736 } 1737 } 1738 } 1739 1740 int st = idL[1], ed = idR[n]; 1741 vector<int> aux, path; 1742 int last = 0, cur = st; 1743 1744 while (true) { 1745 aux.push_back(cur); 1746 if (cur == ed) break; 1747 1748 int nxt = 0; 1749 1750 for (int v : adj[cur]) { 1751 if (v != last) { 1752 nxt = v; 1753 break; 1754 } 1755 } 1756 1757 if (!nxt) { 1758 cout << -1 << '\n'; 1759 return; 1760 } 1761 1762 last = cur, cur = nxt; 1763 1764 if ((int)aux.size() > tot + 5) { 1765 cout << -1 << '\n'; 1766 return; 1767 } 1768 } 1769 1770 path.push_back(1); 1771 for (int i = 1; i < (int)aux.size(); ++i) { 1772 int u = aux[i - 1], v = aux[i]; 1773 if (ori[u] != ori[v]) path.push_back(ori[v]); 1774 } 1775 1776 if (path.back() != n || ((int)path.size() - 1) % 2) { 1777 cout << -1 << '\n'; 1778 return; 1779 } 1780 1781 cout << (int)path.size() - 1 << '\n'; 1782 for (int i = 0; i < (int)path.size(); ++i) { 1783 if (i) cout << ' '; 1784 cout << path[i]; 1785 } 1786 cout << '\n'; 1787 } 1788 1789 int main() { 1790 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 1791 1792 int T; cin >> T; 1793 while (T--) work(); 1794 1795 return 0; 1796 } 1797 ```