1844.md (22076B)
1 Source: https://codeforces.com/blog/entry/118128 2 3 Video editorials for [B](https://www.youtube.com/watch?v=5nzUni8dFLQ), [C](https://www.youtube.com/watch?v=8mz7gnAJ5QM), and [D](https://www.youtube.com/watch?v=ahnNAwpGwHc) are available on [competitive__programmer](/profile/competitive__programmer "Specialist competitive__programmer")'s channel. 4 5 ### [1844A - Subtraction Game](/contest/1844/problem/A) 6 7 **Hint 1** 8 9 There exists a small $n$ where the second player can win. 10 11 **Hint 2** 12 13 If $a \ge 2$, then $n = 1$ works. 14 15 **Solution** 16 17 Tutorial is loading... 18 19 **Implementation** 20 21 ``` 22 #include <bits/stdc++.h> 23 using namespace std; 24 25 int main() { 26 int t,a,b; 27 scanf("%d",&t); 28 while (t--) { 29 scanf("%d %d",&a,&b); 30 printf("%d\n",a+b); 31 } 32 return 0; 33 } 34 ``` 35 36 ### [1844B - Permutations & Primes](/contest/1844/problem/B) 37 38 **Hint 1** 39 40 In order for $(l,r)$ to contribute to the primality, we must have $\operatorname{MEX}(a_l,\dots,a_r) \ge 2$, so there is some value $1$ between indices $l$ and $r$. 41 42 **Hint 2** 43 44 To maximize the number of pairs $(l,r)$ that contain the value $1$, we should put $1$ near the middle of the array. 45 46 **Hint 3** 47 48 To minimize the number of pairs $(l,r)$ where $\operatorname{MEX}(a_l,\dots,a_r) \ge 2$ but is not prime, we should put $2$ and $3$ at the ends of the array. 49 50 **Solution** 51 52 Tutorial is loading... 53 54 **Implementation** 55 56 ``` 57 #include <bits/stdc++.h> 58 using namespace std; 59 60 int a[200000]; 61 int main() { 62 int i; 63 int t,n; 64 scanf("%d",&t); 65 while (t--) { 66 scanf("%d",&n); 67 if (n == 1) printf("1\n"); 68 else if (n == 2) printf("1 2\n"); 69 else { 70 int c = 4; 71 fill(a,a+n,0); 72 a[0] = 2,a[n/2] = 1,a[n-1] = 3; 73 for (i = 0; i < n; i++) { 74 if (a[i] == 0) a[i] = c++; 75 } 76 for (i = 0; i < n; i++) printf("%d%c",a[i],(i == n-1) ? '\n':' '); 77 } 78 } 79 return 0; 80 } 81 ``` 82 83 ### [1844C - Particles](/contest/1844/problem/C) 84 85 **Hint 1** 86 87 The answer is the sum of some subset of $c_1,\dots,c_n$. Think about which subsets are obtainable. 88 89 **Hint 2** 90 91 Consider the set of even-indexed particles and the set of odd-indexed particles. 92 93 **Solution** 94 95 Tutorial is loading... 96 97 **Implementation** 98 99 ``` 100 #include <bits/stdc++.h> 101 using namespace std; 102 typedef long long int LLI; 103 104 int c[200000]; 105 int main() { 106 int i; 107 int t,n; 108 scanf("%d",&t); 109 while (t--) { 110 scanf("%d",&n); 111 for (i = 0; i < n; i++) scanf("%d",&c[i]); 112 113 int allneg = 1; 114 for (i = 0; i < n; i++) allneg &= (c[i] < 0); 115 if (allneg) printf("%d\n",*max_element(c,c+n)); 116 else { 117 LLI ans1 = 0,ans2 = 0; 118 for (i = 0; i < n; i++) { 119 if (i & 1) ans1 += max(c[i],0); 120 else ans2 += max(c[i],0); 121 } 122 printf("%lld\n",max(ans1,ans2)); 123 } 124 } 125 return 0; 126 } 127 ``` 128 129 ### [1844D - Row Major](/contest/1844/problem/D) 130 131 **Hint 1** 132 133 Describe, using a graph, all the pairs of characters in $s$ that need to be different. 134 135 **Hint 2** 136 137 Consider the smallest positive integer that does not divide $n$. 138 139 **Solution** 140 141 Tutorial is loading... 142 143 **Implementation** 144 145 ``` 146 #include <bits/stdc++.h> 147 using namespace std; 148 149 char s[1000001]; 150 int main() { 151 int i; 152 int t,n; 153 scanf("%d",&t); 154 while (t--) { 155 scanf("%d",&n); 156 int c = 1; 157 while ((n % c) == 0) c++; 158 for (i = 0; i < n; i++) s[i] = 'a'+(i % c); 159 s[n] = '\0'; 160 printf("%s\n",s); 161 } 162 return 0; 163 } 164 ``` 165 166 ### [1844E - Great Grids](/contest/1844/problem/E) 167 168 **Hint 1** 169 170 Try to find a characterization of all great grids. 171 172 **Hint 2** 173 174 There are two approaches that lead to the same conclusion. Approach 1 is more clever and leads more easily to the conclusion, while approach 2 is perhaps more natural to consider. Feel free to read the hint towards the approach that sounds better. 175 176 **Hint Towards Approach 1** 177 178 Think of the letters as numbers modulo $3$ and look at differences of adjacent cells. 179 180 **Hint Towards Approach 2** 181 182 Draw a `/` or `\` for each $2 \times 2$ subgrid connecting the equal letters, and look for patterns. 183 184 **Hint 3** 185 186 In either approach, we can associate a type to each row and column, which has one of two possibilities. The constraints correspond to a row and a column needing to have the same or different types. 187 188 **Hint 4** 189 190 The problem reduces to checking the $2$-colourability of a graph. 191 192 **Solution** 193 194 Tutorial is loading... 195 196 **Implementation** 197 198 ``` 199 #include <bits/stdc++.h> 200 using namespace std; 201 typedef vector<pair<int,int> > vpii; 202 #define mp make_pair 203 #define pb push_back 204 205 vpii adjList[4000]; 206 int colour[4000],bad = 0; 207 int doDFS(int u,int c) { 208 if (colour[u] != -1) { 209 if (colour[u] != c) bad = 1; 210 return 0; 211 } 212 colour[u] = c; 213 for (auto [v,e]: adjList[u]) doDFS(v,c^e); 214 return 0; 215 } 216 int main() { 217 int i; 218 int t,n,m,k; 219 int x1,y1,x2,y2; 220 scanf("%d",&t); 221 while (t--) { 222 scanf("%d %d %d",&n,&m,&k); 223 for (i = 0; i < k; i++) { 224 scanf("%d %d %d %d",&x1,&y1,&x2,&y2); 225 x1--,y1--,x2--,y2--; 226 adjList[min(x1,x2)].pb(mp(n+min(y1,y2),(x1+y1 != x2+y2))); 227 adjList[n+min(y1,y2)].pb(mp(min(x1,x2),(x1+y1 != x2+y2))); 228 } 229 230 fill(colour,colour+n+m,-1),bad = 0; 231 for (i = 0; i < n+m; i++) { 232 if (colour[i] == -1) doDFS(i,0); 233 } 234 printf(bad ? "NO\n":"YES\n"); 235 236 for (i = 0; i < n+m; i++) adjList[i].clear(); 237 } 238 return 0; 239 } 240 ``` 241 242 ### [1844F1 - Min Cost Permutation (Easy Version)](/contest/1844/problem/F1) 243 244 **Hint 1** 245 246 Solve the case $c \ge 0$ first. There is a very simple description of the answer. 247 248 **Another Hint** 249 250 What is the answer when $c = 0$? 251 252 **Hint 2** 253 254 When $c \ge 0$, the answer is the array sorted in nondecreasing order. 255 256 **Hint 3** 257 258 When $c \lt 0$, the minimum cost is achieved by sorting the array in nonincreasing order, but this is not the lexicographically smallest. Try to greedily form the lexicographically smallest array one element at a time. 259 260 **Solution (easy version)** 261 262 Tutorial is loading... 263 264 **Implementation** 265 266 ``` 267 #include <bits/stdc++.h> 268 using namespace std; 269 typedef long long int LLI; 270 271 int a[200000]; 272 int main() { 273 int i,j; 274 int t,n,c; 275 scanf("%d",&t); 276 while (t--) { 277 scanf("%d %d",&n,&c); 278 for (i = 0; i < n; i++) scanf("%d",&a[i]); 279 if (c >= 0) { 280 sort(a,a+n); 281 for (i = 0; i < n; i++) printf("%d%c",a[i],(i == n-1) ? '\n':' '); 282 continue; 283 } 284 285 sort(a,a+n,greater<int>()); 286 for (i = 0; i < n; i++) { 287 for (j = n-1; j > i; j--) { 288 LLI diff = -abs(a[j]-a[j-1]-c); 289 if (j < n-1) { 290 diff -= abs(a[j+1]-a[j]-c); 291 diff += abs(a[j+1]-a[j-1]-c); 292 } 293 if (i == 0) diff += abs(a[i]-a[j]-c); 294 else { 295 diff -= abs(a[i]-a[i-1]-c); 296 diff += abs(a[i]-a[j]-c); 297 diff += abs(a[j]-a[i-1]-c); 298 } 299 if (diff == 0) { 300 for (; j > i; j--) swap(a[j],a[j-1]); 301 } 302 } 303 } 304 for (i = 0; i < n; i++) printf("%d%c",a[i],(i == n-1) ? '\n':' '); 305 } 306 return 0; 307 } 308 ``` 309 310 ### [1844F2 - Min Cost Permutation (Hard Version)](/contest/1844/problem/F2) 311 312 These hints and solution continue from the solution for the easy version, so please read the solution for the easy version first. 313 314 **Hint 4** 315 316 We need to optimize the $\mathcal{O}(n^2)$ greedy with some data structures. There exist solutions with varying levels of data structure implementation depending on how much effort is put into characterizing the answer array. For a short solution, start by simplifying the formula $(*)$ (in the solution for the easy version) to get a cleaner description. 317 318 **Hint 5** 319 320 The condition is actually equivalent to ($a_{i-1}-a_{i+1} \le |c|$ or $a_{i-1} = a_i$ or $a_i = a_{i+1}$) and ($b_{k-1}-a_i \le |c|$). 321 322 **Hint 6** 323 324 Maintain a linked list of the unused entries of $a$ and a set of unused entries that satisfy ($a_{i-1}-a_{i+1} \le |c|$ or $a_{i-1} = a_i$ or $a_i = a_{i+1}$). 325 326 **Solution (hard version)** 327 328 ### [1844F2 - Min Cost Permutation (Hard Version)](/contest/1844/problem/F2) 329 330 Let $c \lt 0$. 331 332 We now simplify condition $(*)$, which involves considering a few cases depending on the sign of the terms. It turns out that the condition is equivalent to ($a_{i-1}-a_{i+1} \le |c|$ or $a_{i-1} = a_i$ or $a_i = a_{i+1}$) and ($b_{k-1}-a_i \le |c|$) (for full details, see the overall proof below). 333 334 Sort $a$ in nonincreasing order so that $a_1 \ge a_2 \ge \dots \ge a_n$. We can simulate the greedy algorithm from the easy version with the help of a linked list of the unused elements of $a$ and a set of $a_i$ which satisfy the first part of the condition, ($a_{i-1}-a_{i+1} \le |c|$ or $a_{i-1} = a_i$ or $a_i = a_{i+1}$). Here, $a_{i-1}$ and $a_{i+1}$ actually refer to the closest unused elements of $a$, which are $a_i$'s left and right pointers in the linked list, respectively. 335 336 Each time, we query the set for its smallest element $a_i$ that satisfies $a_i \ge b_{k-1}-|c|$. If this element does not exist, then we take $a_i$ to be the largest element in the linked list. Then, we set $b_k := a_i$, delete $a_i$ from the linked list, and update the set with the left and right elements of $a_i$ if they now satisfy the condition. 337 338 One small observation is that in the answer $b$, $b_1 = a_1$ and $b_n = a_n$. This may simplify the implementation since it means that some edge cases of $(*)$ actually don't need to be checked. It is also actually not necessary to check the $a_{i-1} = a_i$ or $a_i = a_{i+1}$ condition. 339 340 The time complexity is $\mathcal{O}(n \log n)$. 341 342 **Proofs** 343 344 The case $n \le 2$ is trivial. In the following, we only consider the case $c \lt 0$ and $n \ge 3$. The case $c \ge 0$ follows by symmetry (reverse the array). 345 346 Let $c' := -c$ to reduce confusion with negative signs, and WLOG let $a_1 \ge a_2 \ge \dots \ge a_n$. 347 348 Instead of considering $\sum_{i=1}^{n-1} |b_{i+1}-b_i-c|$, consider a permutation $b$ that minimizes the *augmented cost* $|b_1-b_n-c|+\sum_{i=1}^{n-1} |b_{i+1}-b_i-c|$. By circular symmetry, WLOG rotate $b$ so that $b_n = a_n$. 349 350 We will perform a sequence of steps to sort $b$ in nonincreasing order without ever increasing the augmented cost. Consider looking at $b_{n-1},b_{n-2},\dots,b_1$ in order, such that when we look at $b_k$, we have the invariant that $b_{k+1} \ge b_{k+2} \ge \dots \ge b_n = a_n$. If $b_k \ge b_{k+1}$, do not do anything. Otherwise, since $b_k \ge a_n = b_n$, there exists an index $k+1 \le i \lt n$ such that $b_i \ge b_k \ge b_{i+1}$. Consider deleting $b_k$ from the array and reinserting it between index $i$ and $i+1$. We have the following results: 351 352 **Claim 1**: Deleting $b_k$ decreases the augmented cost by at least $c'$. 353 354 **Proof**: Let $x := b_{k-1}-b_k$ (or $b_n-b_1$ if $k = 1$) and $y := b_{k+1}-b_k \ge 0$. We need to check that $|x-y-c'|+c' \le |x-c'|+|-y-c'|$, which follows from $|x-c'|+|-y-c'| = |x-c'|+y+c' \ge |x-y-c'|+c'$ (we use the triangle inequality in the last step). 355 356 Note that equality holds if and only if $x-c' \le 0$, i.e. $b_{k-1}-b_k \le c'$. 357 358 **Claim 2**: Reinserting $b_k$ increases the augmented cost by at most $c'$. 359 360 **Proof**: Let $x := b_i-b_k \ge 0$ and $y := b_k-b_{i+1} \ge 0$. We need to check that $|x-c'|+|y-c'| \le |x+y-c'|+c'$. Consider four cases: 361 362 * If $x,y \ge c'$, then $|x-c'|+|y-c'| = x+y-2c' \lt (x+y-c')+c' = |x+y-c'|+c'$. 363 * If $x \ge c', y \le c'$, then $|x-c'|+|y-c'| = x-y \le (x+y-c')+c' = |x+y-c'|+c'$. 364 * If $x \le c', y \ge c'$, then $|x-c'|+|y-c'| = y-x \le (x+y-c')+c' = |x+y-c'|+c'$. 365 * If $x,y \le c'$, then $|x-c'|+|y-c'| = 2c'-x-y = (c'-x-y)+c' \le |x+y-c'|+c'$. 366 367 Note that equality holds if and only if $x = 0$ or $y = 0$ or $c'-x-y \ge 0$, i.e. $b_i-b_{i+1} \le c'$ or $b_i = b_k$ or $b_k = b_{i+1}$. 368 369 Therefore, each step does not increase the augmented cost. After all the steps, $b$ will be sorted in nonincreasing order. Therefore, the smallest possible augmented cost is $|a_1-a_n-c|+\sum_{i=1}^{n-1} |a_{i+1}-a_i-c|$. 370 371 Now note that $|a_1-a_n-c| = (a_1-a_n)+c'$ is the *maximum* possible value of $|b_1-b_n-c|$! This means that the minimum cost cannot be less than the minimum augmented cost minus $(a_1-a_n)+c'$. It follows that the minimum cost is obtained by sorting $a$ in nonincreasing order, and furthermore, *any* optimal permutation $b$ satisfies $b_1 = a_1$ and $b_n = a_n$. 372 373 Furthermore, suppose we have fixed $b_1,\dots,b_k$ and also $b_n = a_n$. By a similar argument (looking at $b_{n-1},\dots,b_{k+1}$ and reinserting them to the right), one optimal permutation $b_{k+1},\dots,b_n$ of the remaining elements is to sort them in nonincreasing order. Our greedy algorithm can only reach states where the optimal remaining permutation satisfies $b_n = a_n$, so it is correct. 374 375 Note that condition $(*)$ is similar to equality being achieved in both claim 1 and claim 2. It follows that $(*)$ is equivalent to ($a_{i-1}-a_{i+1} \le |c|$ or $a_{i-1} = a_i$ or $a_i = a_{i+1}$) and ($b_{k-1}-a_i \le |c|$) as claimed. 376 377 **Implementation** 378 379 ``` 380 #include <bits/stdc++.h> 381 using namespace std; 382 typedef pair<int,int> pii; 383 #define mp make_pair 384 385 int a[200000],b[200000],l[200000],r[200000]; 386 set<pii> S; 387 int main() { 388 int i; 389 int t,n,c; 390 scanf("%d",&t); 391 while (t--) { 392 scanf("%d %d",&n,&c); 393 for (i = 0; i < n; i++) scanf("%d",&a[i]); 394 if (c >= 0) { 395 sort(a,a+n); 396 for (i = 0; i < n; i++) printf("%d%c",a[i],(i == n-1) ? '\n':' '); 397 continue; 398 } 399 400 sort(a,a+n,greater<int>()); 401 b[0] = a[0]; 402 for (i = 0; i < n; i++) l[i] = (i+n-1) % n,r[i] = (i+1) % n; 403 for (i = 2; i < n-1; i++) { 404 if (a[l[i]]-a[r[i]] <= -c) S.insert(mp(a[i],i)); 405 } 406 for (i = 1; i < n; i++) { 407 int u; 408 auto it = S.lower_bound(mp(b[i-1]+c,0)); 409 if (it == S.end()) u = r[0]; 410 else u = it->second,S.erase(it); 411 b[i] = a[u]; 412 int x = l[u],y = r[u]; 413 r[x] = y,l[y] = x; 414 S.erase(mp(a[x],x)),S.erase(mp(a[y],y)); 415 if ((x != 0) && (l[x] != 0) && (r[x] != 0) && (a[l[x]]-a[r[x]] <= -c)) S.insert(mp(a[x],x)); 416 if ((y != 0) && (l[y] != 0) && (r[y] != 0) && (a[l[y]]-a[r[y]] <= -c)) S.insert(mp(a[y],y)); 417 } 418 for (i = 0; i < n; i++) printf("%d%c",b[i],(i == n-1) ? '\n':' '); 419 } 420 return 0; 421 } 422 ``` 423 424 ### [1844G - Tree Weights](/contest/1844/problem/G) 425 426 **Hint 1** 427 428 Model the problem as a system of linear equations. 429 430 **Hint 2** 431 432 Let $x_u$ be the sum of the weights of the edges on the path from node $1$ to node $u$. The equations are of the form $x_i + x_{i+1} - 2x_{\text{lca}(i,i+1)} = d_i$. 433 434 **Hint 3** 435 436 The intended solution does not do anything like attempt to maintain paths/virtual trees of known weight. One easily overlooked detail that is essential to the solution is that $x_i$ are integers. 437 438 **Hint 4** 439 440 Solve the equations modulo $2$ first, so that the $2x_{\text{lca}(i,i+1)}$ term disappears. 441 442 **Hint 5** 443 444 After solving the equations modulo $2$, we can similarly solve modulo $4$, $8$, etc. 445 446 **Solution** 447 448 Tutorial is loading... 449 450 **Implementation** 451 452 ``` 453 #include <bits/stdc++.h> 454 using namespace std; 455 typedef long long int LLI; 456 typedef vector<pair<int,int> > vpii; 457 #define mp make_pair 458 #define pb push_back 459 460 vpii adjList[100000]; 461 LLI d[100000]; 462 int parent[100000][17],parenti[100000],depth[100000]; 463 int doDFS(int u,int p,int d) { 464 parent[u][0] = p,depth[u] = d; 465 for (auto [v,i]: adjList[u]) { 466 if (v != p) parenti[v] = i,doDFS(v,u,d+1); 467 } 468 return 0; 469 } 470 int logn; 471 int lca(int u,int v) { 472 int i; 473 if (depth[u] < depth[v]) swap(u,v); 474 for (i = logn-1; i >= 0; i--) { 475 if ((parent[u][i] != -1) && (depth[parent[u][i]] >= depth[v])) u = parent[u][i]; 476 } 477 if (u == v) return u; 478 for (i = logn-1; i >= 0; i--) { 479 if (parent[u][i] != parent[v][i]) u = parent[u][i],v = parent[v][i]; 480 } 481 return parent[u][0]; 482 } 483 int lcas[100000],bit[100000]; 484 LLI ans[100000],w[100000]; 485 int main() { 486 int i; 487 int n,u,v; 488 scanf("%d",&n); 489 for (i = 0; i < n-1; i++) { 490 scanf("%d %d",&u,&v); 491 u--,v--; 492 adjList[u].pb(mp(v,i)); 493 adjList[v].pb(mp(u,i)); 494 } 495 for (i = 0; i < n-1; i++) scanf("%lld",&d[i]); 496 497 int j; 498 doDFS(0,-1,0); 499 for (i = 1; (1 << i) < n; i++) { 500 for (j = 0; j < n; j++) { 501 if (parent[j][i-1] != -1) parent[j][i] = parent[parent[j][i-1]][i-1]; 502 else parent[j][i] = -1; 503 } 504 } 505 logn = i; 506 for (i = 0; i < n-1; i++) lcas[i] = lca(i,i+1); 507 508 for (i = 0; i < 57; i++) { 509 bit[0] = 0; 510 for (j = 0; j < n-1; j++) bit[j+1] = bit[j]^(d[j] & 1); 511 for (j = 0; j < n-1; j++) d[j] = (d[j]-bit[j]-bit[j+1]+2*bit[lcas[j]])/2; 512 for (j = 0; j < n; j++) ans[j] |= ((LLI) bit[j] << i); 513 } 514 for (i = 0; i < n-1; i++) { 515 if (d[i] != 0) { 516 printf("-1\n"); 517 return 0; 518 } 519 } 520 for (i = 1; i < n; i++) { 521 w[parenti[i]] = ans[i]-ans[parent[i][0]]; 522 if (w[parenti[i]] <= 0) { 523 printf("-1\n"); 524 return 0; 525 } 526 } 527 for (i = 0; i < n-1; i++) printf("%lld\n",w[i]); 528 529 return 0; 530 } 531 ``` 532 533 ### [1844H - Multiple of Three Cycles](/contest/1844/problem/H) 534 535 **Hint 1** 536 537 The partially formed permutation is composed of several paths and cycles. Only the length of each path/cycle modulo $3$ matters. 538 539 **Hint 2** 540 541 The problem reduces to the following: Given $a$ $1$s, $b$ $2$s, and $c$ $0$s, how many ways are there to build a permutation on these objects so that each cycle sums to a multiple of $3$? Let $f(a,b,c)$ be the answer. Write some dynamic programming recurrences for $f(a,b,c)$. 542 543 **Hint 3** 544 545 Note that $f(a,b,c) = (a+b+c)f(a,b,c-1)$ (choose the next object of any $0$ and merge them). 546 547 **Why is this useful?** 548 549 This allows us to eliminate the $c$ parameter, multiplying the answer by a factorial and inverse factorial. 550 551 **Hint 4** 552 553 Let $f(a,b) = f(a,b,0)$. Write down not one, but two recurrence relations $f(a,b)$ satisfies. 554 555 **What are the recurrences?** 556 557 We have $f(a,b) = b(a+b-1)f(a-1,b-1) + (a-1)f(a-2,b+1)$ when $a \gt 0$ (choose the next object of any $1$ and merge them) and also $f(a,b) = a(a+b-1)f(a-1,b-1) + (b-1)f(a+1,b-2)$ when $b \gt 0$ (choose the next object of any $2$ and merge them). 558 559 **Hint 5** 560 561 These recurrences mean that given any two of $f(a,b),f(a-1,b-1),f(a+2,b-1),f(a-1,b+2)$, we can solve for the other two. 562 563 **Hint 6** 564 565 Consider the pairs $(a,b)$ that arise from the $n$ queries. These pairs can be visualized as a walk in the plane, where each each pair does not differ from the previous pair by much. If we carefully use the recurrences to solve for values of $f(a,b)$ from values we already know, we can answer all queries on this walk while calculating only $\mathcal{O}(n)$ values of $f(a,b)$. 566 567 **Solution** 568 569 Tutorial is loading... 570 571 **Implementation** 572 573 ``` 574 #include <bits/stdc++.h> 575 using namespace std; 576 typedef long long int LLI; 577 #define MOD 998244353 578 579 int parent[300000],siz[300000]; 580 int find(int n) { 581 if (parent[n] != n) parent[n] = find(parent[n]); 582 return parent[n]; 583 } 584 int queries[600000][3],ans[600000]; 585 int fact[300000],invfact[300000],invn[300000]; 586 int inv(int n) { 587 int e = MOD-2,r = 1; 588 while (e > 0) { 589 if (e & 1) r = ((LLI) r*n) % MOD; 590 e >>= 1; 591 n = ((LLI) n*n) % MOD; 592 } 593 return r; 594 } 595 int main() { 596 int i; 597 int n,x,y,bad = 1e9; 598 int num[3]; 599 scanf("%d",&n); 600 for (i = 0; i < n; i++) parent[i] = i,siz[i] = 1; 601 num[0] = 0,num[1] = n,num[2] = 0; 602 for (i = 0; i < n; i++) { 603 scanf("%d %d",&x,&y); 604 x--,y--; 605 if (find(x) != find(y)) { 606 num[siz[find(x)] % 3]--; 607 num[siz[find(y)] % 3]--; 608 siz[find(y)] += siz[find(x)]; 609 parent[find(x)] = find(y); 610 num[siz[find(y)] % 3]++; 611 } 612 else if ((siz[find(x)] % 3) == 0) num[0]--; 613 else if (bad == 1e9) bad = i; 614 copy(num,num+3,queries[i]); 615 } 616 617 fact[0] = 1; 618 for (i = 1; i < n; i++) fact[i] = ((LLI) i*fact[i-1]) % MOD; 619 invfact[n-1] = inv(fact[n-1]); 620 for (i = n-2; i >= 0; i--) invfact[i] = ((LLI) (i+1)*invfact[i+1]) % MOD; 621 for (i = 1; i < n; i++) invn[i] = ((LLI) invfact[i]*fact[i-1]) % MOD; 622 623 int m = n; 624 while (num[1]+num[2] > 0) { 625 int a = (num[1] > 0) ? 1:2; 626 num[a]--; 627 int b = (num[1] > 0) ? 1:2; 628 num[b]--; 629 num[(a+b) % 3]++; 630 copy(num,num+3,queries[m++]); 631 } 632 x = 1,y = 1; 633 int u = 1,v = 8; 634 auto f = [&]() { 635 assert(x > 0); 636 int nu = (((v-(((LLI) (y+1)*(x+y+1)) % MOD)*u) % MOD)*invn[x]) % MOD; 637 int nv = ((((LLI) x*(x+y+2)) % MOD)*nu+(LLI) (y+2)*v) % MOD; 638 x--,y += 2,u = nu,v = nv; 639 if (u < 0) u += MOD; 640 if (v < 0) v += MOD; 641 }; 642 auto g = [&]() { 643 assert(y > 0); 644 int nu = (((v-(((LLI) (x+1)*(x+y+1)) % MOD)*u) % MOD)*invn[y]) % MOD; 645 int nv = ((((LLI) y*(x+y+2)) % MOD)*nu+(LLI) (x+2)*v) % MOD; 646 x += 2,y--,u = nu,v = nv; 647 if (u < 0) u += MOD; 648 if (v < 0) v += MOD; 649 }; 650 for (i = m-1; i >= 0; i--) { 651 int a = queries[i][1],b = queries[i][2],c = queries[i][0]; 652 if ((a == 0) && (b == 0)) ans[i] = 1; 653 else if ((a == x) && (b == y)) ans[i] = u; 654 else if ((a == x-1) && (b == y+2)) f(),ans[i] = u; 655 else if ((a == x+2) && (b == y-1)) g(),ans[i] = u; 656 else if ((a == x+1) && (b == y+1)) { 657 if (x > 0) f(),g(),ans[i] = u; 658 else g(),f(),ans[i] = u; 659 } 660 else assert(0); 661 ans[i] = ((LLI) ans[i]*fact[a+b+c]) % MOD; 662 ans[i] = ((LLI) ans[i]*invfact[a+b]) % MOD; 663 } 664 for (i = 0; i < n; i++) printf("%d\n",(i >= bad) ? 0:ans[i]); 665 666 return 0; 667 } 668 ```