2002.md (43419B)
1 Source: https://codeforces.com/blog/entry/132569 2 3 [2002A — Distanced Coloring](https://codeforces.com/contest/2002/problem/A) 4 5 idea & solution: [xcyle](/profile/xcyle "International Grandmaster xcyle") 6 7 **Hint 1** 8 9 Consider the case with $n=m=k$. 10 11 **Hint 2** 12 13 Generalize the solution for all $n,m,k$. 14 15 **Tutorial** 16 17 It can be shown that for any $k\times k$ subgrid, the colors we use must be pairwise distinct. Thus, we have an lower bound of $\min(n,k)\cdot\min(m,k)$. We can show that this lower bound is indeed achievable by coloring the upper-left $\min(n,k)\cdot\min(m,k)$ subgrid with distinct colors, and copy-pasting it to fill the rest of the grid. 18 19 Time complexity: $O(1)$. 20 21 **Solution** 22 23 ``` 24 #include <bits/stdc++.h> 25 using namespace std; 26 int t, n, m, k; 27 int main() { 28 scanf("%d", &t); 29 30 while (t--) { 31 scanf("%d%d%d", &n, &m, &k); 32 printf("%d\n", min(n, k)*min(m, k)); 33 } 34 35 return 0; 36 } 37 ``` 38 39 [2002B — Removals Game](https://codeforces.com/contest/2002/problem/B) 40 41 idea & solution: [xcyle](/profile/xcyle "International Grandmaster xcyle") 42 43 **Hint** 44 45 Find some conditions that Bob need to win. 46 47 **Tutorial** 48 49 A general idea is that it is very difficult for Bob to win. We make some observations regarding the case where Bob wins. It is intuitive to see that for any subarray $[A_l,A_{l+1},\cdots,A_r]$, the elements' positions in $B$ must also form an interval. If $A[l:r]$ does not form an interval in $B$, Alice can simply remove elements until only $A[l:r]$ is left, no matter how Bob plays, there must now be an element in $A$ but not in $B$ because of our previous condition. Alice can then remove everything other than this element to win. 50 51 From here, it is easy to prove by induction that for Bob to win, either $A=B$ or $A=\textrm{rev}(B)$. 52 53 Time complexity: $O(n)$. 54 55 **Solution** 56 57 ``` 58 #include <bits/stdc++.h> 59 #define ll long long 60 #define lc(x) ((x) << 1) 61 #define rc(x) ((x) << 1 | 1) 62 #define ru(i, l, r) for (int i = (l); i <= (r); i++) 63 #define rd(i, r, l) for (int i = (r); i >= (l); i--) 64 #define mid ((l + r) >> 1) 65 #define pii pair<int, int> 66 #define mp make_pair 67 #define fi first 68 #define se second 69 #define sz(s) (int)s.size() 70 #include <ext/pb_ds/assoc_container.hpp> 71 #include <ext/pb_ds/tree_policy.hpp> 72 using namespace __gnu_pbds; 73 #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> 74 using namespace std; 75 mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count()); 76 int read() { 77 int x = 0, w = 0; 78 char ch = getchar(); 79 80 while (!isdigit(ch)) 81 w |= ch == '-', ch = getchar(); 82 83 while (isdigit(ch)) 84 x = x * 10 + ch - '0', ch = getchar(); 85 86 return w ? -x : x; 87 } 88 int main() { 89 int T = read(); 90 91 while (T--) { 92 int n = read(); 93 vector<int> a, b; 94 ru(i, 1, n) a.push_back(read()); 95 ru(i, 1, n) b.push_back(read()); 96 97 if (a == b) { 98 printf("Bob\n"); 99 continue; 100 } 101 102 reverse(a.begin(), a.end()); 103 104 if (a == b) { 105 printf("Bob\n"); 106 continue; 107 } 108 109 printf("Alice\n"); 110 } 111 112 return 0; 113 } 114 ``` 115 116 [2002C — Black Circles](https://codeforces.com/contest/2002/problem/C) 117 118 idea: [Flamire](/profile/Flamire "International Grandmaster Flamire"), solution: [le0n](/profile/le0n "International Grandmaster le0n") 119 120 **Hint** 121 122 The problem can't be that hard, find some simple strategy. 123 124 **Tutorial** 125 126 We consider a simple strategy: walk towards the goal in a straight line. 127 128 If some circle reaches the goal first, it is obvious that we have no chance of succeeding, no matter what path we take. 129 130 Otherwise, it can be proven that we will not pass any circles on our way to the goal. 131 132  133 134 Suppose we start at $A$, our goal is $B$, and we got intercepted by some circle $C$ at the point $D$. It follows that $CD=AD$. According to the triangle inequality, $CD \gt CB-DB$ should hold. Thus, we have $CB-DB\le AD$, which means $CB\le AB$, proof by contradiction. 135 136 Time complexity: $O(n)$. 137 138 **Solution** 139 140 ``` 141 #include <bits/stdc++.h> 142 #define ll long long 143 using namespace std; 144 int t, n, x[100011], y[100011], xs, ys, xt, yt; 145 ll dis(int x1, int y1, int x2, int y2) { 146 return 1ll * (x2 - x1) * (x2 - x1) + 1ll * (y2 - y1) * (y2 - y1); 147 } 148 int main() { 149 scanf("%d", &t); 150 151 while (t--) { 152 scanf("%d", &n); 153 154 for (int i = 1; i <= n; ++i) 155 scanf("%d%d", x + i, y + i); 156 157 scanf("%d%d%d%d", &xs, &ys, &xt, &yt); 158 bool ok = 1; 159 160 for (int i = 1; i <= n; ++i) { 161 if (dis(xt, yt, x[i], y[i]) <= dis(xt, yt, xs, ys)) { 162 ok = 0; 163 break; 164 } 165 } 166 167 printf(ok ? "YES\n" : "NO\n"); 168 } 169 170 fclose(stdin); 171 fclose(stdout); 172 return 0; 173 } 174 ``` 175 176 [2002D1 — DFS Checker (Easy Version)](https://codeforces.com/contest/2002/problem/D1) and [2002D2 — DFS Checker (Hard Version)](https://codeforces.com/contest/2002/problem/D1) 177 178 idea & solution: [xcyle](/profile/xcyle "International Grandmaster xcyle") 179 180 **Hint** 181 182 Try to find some easy checks that can be maintained. 183 184 **Tutorial** 185 186 The problem revolves around finding a check for dfs orders that's easy to maintain. We have discovered several such checks, a few checks and their proofs are described below, any one of these checks suffices to tell whether a dfs order is valid. 187 188 **Check 1** 189 190 For every $u$, all of its children $v$ satisfies $[pos_v,pos_v+siz_v-1]\subseteq[pos_u,pos_u+siz_u-1]$. We can maintain this check by keeping track of the number of $u$ which violates this condition, and check for each $u$ using sets, when checking, we need only check the child with the minimum $pos_v$ and maximum $pos_v+siz_v-1$. 191 192 Proof: We prove by induction. When $u$'s children only consists of leaves, it is easy to see that this check ensures $[pos_u,pos_u+siz_u-1]$ is a valid dfs order of the subtree of $u$. Then, we can merge the subtree of $u$ into a large node with size $siz_u$, and continue the analysis above. 193 194 **Check 2** 195 196 Check 2: First we check $p_1=1$. Then, for each pair of adjacent elements $p_i,p_{i+1}$, $fa(p_{i+1})$ must be an ancestor of $p_i$, where $fa(u)$ denotes the father of node $u$. We can maintain this check by keeping track of the number of $u$ which violates this condition, and check for each $i$ by checking whether $p_i$ is in the subtree of $fa(p_{i+1})$. 197 198 Proof: For any subtree $u$, we take any $p_i,p_{i+1}$ such that $p_i$ does not belong in subtree $u$, but $p_{i+1}$ does. It follows that $p_{i+1}=u$, since only the subtree of $fa(u)$ has nodes that does not belong in subtree $u$. From this, we can gather that each subtree will be entered at most once (and form a continuous interval), and that the first visited node will be $u$, which is sufficient to say that $p$ is a dfs order. 199 200 Time complexity: $O((n+q)\log n)/O(n+q)$. 201 202 **Solution (Check 1)** 203 204 ``` 205 #include <bits/stdc++.h> 206 #define ll long long 207 #define lc(x) ((x) << 1) 208 #define rc(x) ((x) << 1 | 1) 209 #define ru(i, l, r) for (int i = (l); i <= (r); i++) 210 #define rd(i, r, l) for (int i = (r); i >= (l); i--) 211 #define mid ((l + r) >> 1) 212 #define pii pair<int, int> 213 #define mp make_pair 214 #define fi first 215 #define se second 216 #define sz(s) (int)s.size() 217 #include <ext/pb_ds/assoc_container.hpp> 218 #include <ext/pb_ds/tree_policy.hpp> 219 using namespace __gnu_pbds; 220 #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> 221 using namespace std; 222 #define maxn 500005 223 mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count()); 224 int read() { 225 int x = 0, w = 0; char ch = getchar(); 226 while(!isdigit(ch)) w |= ch == '-', ch = getchar(); 227 while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); 228 return w ? -x : x; 229 } 230 int n, Q, fa[maxn], p[maxn], q[maxn], siz[maxn]; 231 set<int> son[maxn]; 232 int chk(int x) { 233 return son[x].empty() ? 1 : (q[x] < *son[x].begin() && *--son[x].end() + siz[p[*--son[x].end()]] <= q[x] + siz[x]); 234 } 235 void solve() { 236 n = read(), Q = read(); 237 ru(i, 1, n) siz[i] = 1, son[i].clear(); 238 ru(i, 2, n) fa[i] = read(); 239 rd(i, n, 2) siz[fa[i]] += siz[i]; 240 ru(i, 1, n) son[fa[p[i] = read()]].insert(i), q[p[i]] = i; 241 int cnt = 0; 242 ru(i, 1, n) cnt += chk(i); 243 while(Q--) { 244 int i = read(), j = read(), x = p[i], y = p[j]; 245 set<int> s; s.insert(x), s.insert(y), s.insert(fa[x]), s.insert(fa[y]); 246 for (auto x: s) if(x) cnt -= chk(x); 247 son[fa[x]].erase(i), son[fa[y]].erase(j); 248 swap(p[i], p[j]), swap(q[x], q[y]); 249 son[fa[x]].insert(j), son[fa[y]].insert(i); 250 for (auto x: s) if(x) cnt += chk(x); 251 puts(cnt == n ? "YES" : "NO"); 252 } 253 } 254 int main() { 255 int T = read(); 256 while(T--) solve(); 257 return 0; 258 } 259 ``` 260 261 **Solution (Check 2, LipArcanjo)** 262 263 ``` 264 #include <bits/stdc++.h> 265 using namespace std; 266 #define pb push_back 267 #define mp make_pair 268 #define fi first 269 #define se second 270 #define int long long 271 void dbg_out() { cerr << endl; } 272 template <typename H, typename... T> 273 void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); } 274 #define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); } 275 using ll = long long; 276 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); 277 278 const int MAXN = 3e5 + 5; 279 const int MOD = 1e9+7; //998244353; 280 const int INF = 0x3f3f3f3f; 281 const ll INF64 = ll(4e18) + 5; 282 283 284 vector<int> g[MAXN]; 285 286 int tin[MAXN]; 287 int tout[MAXN]; 288 int id[MAXN]; 289 int par[MAXN]; 290 int T = 0; 291 void dfs(int u, int p){ 292 id[u] = tin[u] = tout[u] = T++; 293 for(auto v : g[u]) if(v != p){ 294 dfs(v,u); 295 par[v] = u; 296 tout[u] = tout[v]; 297 } 298 } 299 300 void solve(){ 301 int n,q; 302 cin >> n >> q; 303 vector<int> p(n+1); 304 for(int i = 0; i <= n; i++) g[i].clear(); 305 T = 0; 306 for(int i = 2; i <= n; i++){ 307 int pi; 308 cin >> pi; 309 g[pi].push_back(i); 310 } 311 for(int i = 1; i <= n; i++){ 312 cin >> p[i]; 313 } 314 dfs(1,1); 315 int cnt = 0; 316 auto ok = [&](int i){ 317 if(p[i] == 1){ 318 if(i == 1) return 1; 319 return 0; 320 } 321 int ant = p[i-1]; 322 if(par[p[i]] == ant) return 1; 323 if(tin[ant] != tout[ant]) return 0; 324 int pa = par[p[i]]; 325 if(tin[ant] < tin[pa] || tin[ant] > tout[pa]) return 0; 326 return 1; 327 }; 328 for(int i = 1; i <= n; i++){ 329 cnt += ok(i); 330 } 331 for(int qw = 0; qw < q; qw++){ 332 int x,y; 333 cin >> x >> y; 334 set<int> in; 335 in.insert(x); 336 in.insert(y); 337 if(x-1 >= 1) in.insert(x-1); 338 if(x+1 <= n) in.insert(x+1); 339 if(y-1 >= 1) in.insert(y-1); 340 if(y+1 <= n) in.insert(y+1); 341 for(auto v : in){ 342 cnt -= ok(v); 343 } 344 swap(p[x],p[y]); 345 for(auto v : in){ 346 cnt += ok(v); 347 } 348 cout << (cnt == n ? "YES": "NO") << '\n'; 349 } 350 351 } 352 353 signed main(){ 354 355 ios::sync_with_stdio(false); cin.tie(NULL); 356 357 int t = 1; 358 cin >> t; 359 while(t--){ 360 solve(); 361 } 362 363 return 0; 364 } 365 ``` 366 367 [2002E — Cosmic Rays](https://codeforces.com/contest/2002/problem/E) 368 369 idea: [le0n](/profile/le0n "International Grandmaster le0n"), solution: [Flamire](/profile/Flamire "International Grandmaster Flamire") 370 371 **Hint 1** 372 373 Consider an incremental solution. 374 375 **Hint 2** 376 377 Use stacks. 378 379 **Tutorial** 380 381 The problems asks for the answer for every prefix, which hints at an incremental solution. 382 383 To add a new pair to the current prefix, we need to somehow process the new block merging with old ones. Thus, we should use some structure to store the information on the last block over time. 384 385 Namely, we use a stack to keep track of all blocks that became the last. For each block, we keep two values: its color $c$ and its lifetime $l$ (the times it takes for the block to disappear). 386 387 When inserting a new block, we pop all blocks that would be shadowed by the current one (i.e. with lifetime shorter than the current block), and merging blocks with the same $a$. When merging two blocks with length $x$ and $z$, and the maximum lifetime of blocks between them is $y$, $y\le\min(x,z)$ should hold, and the new block will have lifetime $x+z-y$. 388 389 For more details, please refer to the solution code. 390 391 There also exists $O(n\log n)$ solutions using ordered sets or heaps. 392 393 Time complexity: $O(n)$. 394 395 **Solution** 396 397 ``` 398 #include <bits/stdc++.h> 399 #define N 1000011 400 #define ll long long 401 #define pii pair<ll,int> 402 #define s1 first 403 #define s2 second 404 using namespace std; 405 int t, n, b[N]; 406 ll a[N]; 407 pii s[N]; 408 int sn; 409 int main() { 410 scanf("%d", &t); 411 412 while (t--) { 413 scanf("%d", &n); 414 415 for (int i = 1; i <= n; ++i) 416 scanf("%lld%d", a + i, b + i); 417 418 sn = 0; 419 ll x = 0; 420 421 for (int i = 1; i <= n; ++i) { 422 ll mx = 0; 423 424 while (sn) { 425 if (s[sn].s2 == b[i]) 426 a[i] += s[sn--].s1 - mx; 427 else if (s[sn].s1 <= a[i]) 428 mx = max(mx, s[sn--].s1); 429 else 430 break; 431 } 432 433 ++sn; 434 s[sn] = pii(a[i], b[i]); 435 x = max(x, s[sn].s1); 436 printf("%lld ", x); 437 } 438 439 putchar(10); 440 } 441 442 return 0; 443 } 444 ``` 445 446 **Solution (priority_queue)** 447 448 ``` 449 #include <bits/stdc++.h> 450 #define ll long long 451 #define N 3000011 452 #define pii pair<ll,int> 453 #define s1 first 454 #define s2 second 455 using namespace std; 456 int t, n, prv[N], nxt[N], b[N]; 457 ll a[N]; 458 priority_queue<pair<ll, int>> pq, del; 459 ll sum = 0, ans[N]; 460 int main() { 461 scanf("%d", &t); 462 463 while (t--) { 464 scanf("%d", &n); 465 466 for (int i = 1; i <= n; ++i) 467 scanf("%lld%d", a + i, b + i); 468 469 while (!pq.empty()) 470 pq.pop(); 471 472 while (!del.empty()) 473 del.pop(); 474 475 nxt[0] = 1; 476 prv[n + 1] = n; 477 478 for (int i = 1; i <= n; ++i) 479 pq.push({-a[i], i}), prv[i] = i - 1, nxt[i] = i + 1; 480 ll tim = 0; 481 int lst = 1; 482 483 for (int _ = 1; _ <= n; ++_) { 484 while (!del.empty() && pq.top() == del.top()) 485 pq.pop(), del.pop(); 486 487 pii p = pq.top(); 488 pq.pop(); 489 int id = p.s2; 490 tim = -p.s1; 491 492 if (nxt[id] <= n && b[id] == b[nxt[id]]) { 493 a[nxt[id]] += tim; 494 pq.push({-a[nxt[id]], nxt[id]}); 495 } 496 497 if (prv[id] && nxt[id] <= n && b[prv[id]] == b[nxt[id]]) { 498 del.push({-a[nxt[id]], nxt[id]}); 499 a[nxt[id]] -= tim; 500 } 501 502 prv[nxt[id]] = prv[id]; 503 nxt[prv[id]] = nxt[id]; 504 505 while (lst < nxt[0]) 506 ans[lst++] = tim; 507 } 508 509 for (int i = 1; i <= n; ++i) 510 printf("%lld ", ans[i]); 511 512 putchar(10); 513 } 514 515 return 0; 516 } 517 ``` 518 519 [2002F1 — Court Blue (Easy Version)](https://codeforces.com/contest/2002/problem/F1) 520 521 idea: [Flamire](/profile/Flamire "International Grandmaster Flamire"), solution: [le0n](/profile/le0n "International Grandmaster le0n") 522 523 **Hint 1** 524 525 Primes are powerful. 526 527 **Hint 2** 528 529 Prime gaps are small. 530 531 **Tutorial** 532 533 We view the problem as a walk on grid, starting at $(1,1)$. WLOG, we suppose $l \gt f$, thus only cells $(a,b)$ where $a \lt b$ would be considered. 534 535 Notice that when $n$ is large enough, the largest prime $p\le n$ satisfies $2p \gt n$. As such, all cells $(p,i)$ where $i \lt p$ will be unblocked and reachable. 536 537 However, we've only bounded one side of the final result. We take this a step further, let $q$ be the second-largest prime $q\le n$. By the same logic, we assume that $2q \gt n$. As such, all cells $(i,q)$, where $p\le i\le n$ will be unblocked and reachable. 538 539 Thus, we have constructed an area where the optimal solution must be, with its dimensions bounded by $n-p$ and $n-q$. We just need to run any brute force solution (dfs with memorization or dp) on this area to find the result. 540 541 If we assume the asymptotic of prime gap is $O(P(n))$, this yields a $O(n\cdot P(n)^2\cdot\log P(n))$ solution, where the $\log\log n$ is from taking the gcd of two numbers which differ by $O(P(n))$. This can also be optimized to $O(n\cdot P(n)^2)$ by preprocessing gcd. 542 543 We added the constraints that $n$'s are pairwise distinct to avoid forcing participants to write memorizations. In fact, under the constraints of the problem, the maximum area is $39201$, and the sum of the $10^3$ largest areas is $2.36\times10^7$. 544 545 Time complexity: $O(P(n)^2\log P(n))/O(P(n)^2)$ 546 547 **Solution** 548 549 ``` 550 #include <bits/stdc++.h> 551 552 using namespace std; 553 typedef long long ll; 554 555 const int N = 2e7 + 5; 556 bool ntp[N]; 557 int di[405][405]; 558 bool bad[405][405]; 559 int pos[N], g = 0, m = 3; 560 int prime[2000005], cnt = 0; 561 void sieve(int n) { 562 int i, j; 563 564 for (i = 2; i <= n; i++) { 565 if (!ntp[i]) 566 prime[++cnt] = i; 567 568 for (j = 1; j <= cnt && i * prime[j] <= n; j++) { 569 ntp[i * prime[j]] = 1; 570 571 if (!(i % prime[j])) 572 break; 573 } 574 } 575 } 576 int gcd(int x, int y) { 577 if (!x) 578 return y; 579 580 if (x <= g && y <= g) 581 return di[x][y]; 582 583 return gcd(y % x, x); 584 } 585 586 int main() { 587 sieve(2e7); 588 int i, j = 1, T, n, a, b, c, u, v; 589 ll ans; 590 591 for (i = 3; i <= 2e7; i++) { 592 while (j < cnt - 1 && prime[j + 2] <= i) 593 j++; 594 595 g = max(g, i - prime[j] + 1); 596 597 if (prime[j] * 2 <= i) 598 m = i; 599 600 pos[i] = j; 601 } 602 603 for (i = 0; i <= g; i++) 604 for (j = 0; j <= g; j++) 605 if (!i) 606 di[i][j] = j; 607 else 608 di[i][j] = di[j % i][i]; 609 610 scanf("%d", &T); 611 612 while (T--) { 613 scanf("%*d%d%d%d", &n, &a, &b); 614 615 if (n <= m) 616 u = v = 1; 617 else { 618 u = prime[pos[n] + 1]; 619 v = prime[pos[n]]; 620 } 621 622 ans = 0; 623 624 for (i = u; i <= n; i++) 625 for (j = v; j <= i; j++) { 626 bad[i - u + 1][j - v + 1] = (gcd(i, j) > 1 || (bad[i - u][j - v + 1] && bad[i - u + 1][j - v])); 627 628 if (!bad[i - u + 1][j - v + 1]) 629 ans = max(ans, max((ll)a * i + (ll)b * j, (ll)a * j + (ll)b * i)); 630 } 631 632 printf("%lld\n", ans); 633 } 634 635 return 0; 636 } 637 ``` 638 639 [2002F2 — Court Blue (Hard Version)](https://codeforces.com/contest/2002/problem/F2) 640 641 idea: [le0n](/profile/le0n "International Grandmaster le0n"), solution: [xcyle](/profile/xcyle "International Grandmaster xcyle") 642 643 **Hint** 644 645 Try generalizing the solution of F1. 646 647 **Hint (alternate version)** 648 649 Write anything and pray that it will pass because of number theory magic. 650 651 **Tutorial** 652 653 We generalize the solution in F1. Let $p$ be the largest prime $\le m$ and $q$ be the largest prime $\le\min(n,p-1)$. The problem is that there might be $\gcd(q,i)\neq1$ for some $p+1\le i\le m$, thus invalidating our previous analysis. 654 655 To solve this, we simply choose $q$ to be the largest integer such that $q\le n$ and $\gcd(q,i)=1$ for all $p+1\le i\le m$. An asymptotic analysis of this solution is as follows: 656 657 As the length of $[p+1,m]$ is $O(P(m))$, and each of these integers have at most $O(\log_nm)$ prime divisors of $O(m)$ magnitude, which means that if we only restrict $q$ to primes, we will have to skip at most $O(P(n)\log_nm)$ primes to find the largest $q$. As the density of primes is $O(\frac1{P(n)})$, the asymptotic of $n-q$ will be $O(P(m)\log_nm\cdot P(n))=O(P(m)^2)$, our actual $q$ (which is not restricted to primes) will not be worse than this. Thus, our total area will be $O(P(m)^3)$, times the gcd complexity gives us an $O(P(m)^3\log m)$ solution. However, the actual area is much lower than this. 658 659 Under the constraints of the problem, when forcing $p,q$ to take primes, the maximum area is $39960$, and the sum of the $10^3$ largest areas is $3.44\times10^7$. The actual solution will not be worse than this. 660 661 Because we only need to check whether $\gcd(x,y)=1$, the complexity can actually be optimized to $O(P(m)^3)$ with some sieves. Namely, iterating over prime divisors $d$ of $[p,m]$ and $[q,n]$ and marking all cells which has $d$ as its common divisor. 662 663 This solution is by far from optimal. We invite you to continue optimizing your solutions and try to minimize the number of cells visited in each query :) 664 665 Time complexity: $O(P(m)^3\log m)$ 666 667 **Select solutions from paticipants and testers** 668 669 **Solution 1** 670 671 Keep $p$ the same, set $q$ to $p-L$ and only keep reachable cells in $[p,n]\times [q,m]$. $L$ is some constant ($100$ should work). 672 673 We found this solution during testing, tried, and failed to hack it. 674 675 **Solution 2** 676 677 Keep $p$ the same, do dfs from each cell $(n,p),(n-1,p),\cdots$, prioritizing increasing $W_L$ over increasing $W_F$, and stop the process the first time you reach any cell $(x,m)$, take the maximum of all cells visited. 678 679 This should not be worse than the intended solution, and actually runs quite fast. 680 681 **Solution 3** 682 683 Simply take all cells in $[n-L,n]\times [m-L,m]$ and mark everything outside as reachable. $L=50$ works. 684 685 We found this solution the day before the round, we don't know how to hack it either. 686 687 **UPD**: $L=50$ was hacked. Hats off to the hacker. 688 689 **Solution 4** 690 691 Do dfs with pruning. Run dfs starting at $(n,m)$, return when the cell is $(p,i)$ (i.e. obviously reachable because of primes), or when the value of the cell is smaller than the current answer. Add some memorization and it passes. 692 693 **Solution** 694 695 ``` 696 #include <bits/stdc++.h> 697 698 using namespace std; 699 typedef long long ll; 700 701 const int N = 2e7 + 5; 702 bool ntp[N]; 703 bool bad[405][405]; 704 int pos[N]; 705 int prime[2000005], mn[N], cnt; 706 void sieve(int n) { 707 int i, j; 708 709 for (i = 2; i <= n; i++) { 710 if (!ntp[i]) 711 prime[++cnt] = i, mn[i] = i; 712 713 for (j = 1; j <= cnt && i * prime[j] <= n; j++) { 714 mn[i * prime[j]] = prime[j]; 715 ntp[i * prime[j]] = 1; 716 717 if (!(i % prime[j])) 718 break; 719 } 720 } 721 } 722 int gcd(int x, int y) { 723 return x ? gcd(y % x, x) : y; 724 } 725 bool no(int l, int r, int k) { 726 while (k > 1) { 727 int x = mn[k]; 728 729 while (k % x == 0) 730 k /= x; 731 732 if (((l + x - 1) / x) * x <= r) 733 return 0; 734 } 735 736 return 1; 737 } 738 739 int main() { 740 sieve(20000000); 741 int i, j = 0, T, n, m, a, b, u, v, g = 0, S = 0, px, py, qwq = 0; 742 ll ans; 743 prime[0] = 1; 744 745 for (i = 2; i <= 20000000; i++) { 746 while (j < cnt && prime[j + 1] <= i) 747 j++; 748 749 pos[i] = j; 750 } 751 752 scanf("%d", &T); 753 754 while (T--) { 755 scanf("%d%d%d%d", &n, &m, &a, &b); 756 757 if (n < m) { 758 swap(n, m); 759 swap(a, b); 760 } 761 762 u = prime[pos[n]]; 763 v = m; 764 765 while (v && !no(u, n, v)) 766 v--; 767 768 ans = 0; 769 px = py = 0; 770 771 for (i = u; i <= n; i++) 772 for (j = v; j <= m && j <= i; j++) { 773 bad[i - u + 1][j - v + 1] = ((bad[i - u][j - v + 1] && bad[i - u + 1][j - v]) || gcd(i, j) > 1); 774 775 if (!bad[i - u + 1][j - v + 1]) { 776 ans = max(ans, (ll)a * i + (ll)b * j); 777 778 if ((ll)a * i + (ll)b * j == ans) { 779 px = i; 780 py = j; 781 } 782 783 if (i <= m) 784 ans = max(ans, (ll)a * j + (ll)b * i); 785 } 786 } 787 788 qwq = max(qwq, (n - px) + (m - py)); 789 printf("%lld\n", ans); 790 } 791 return 0; 792 } 793 ``` 794 795 **Solution (dfs)** 796 797 ``` 798 #include <bits/stdc++.h> 799 #define ll long long 800 #define N 20000011 801 using namespace std; 802 int t, n, m, a, b; 803 bool is[N]; 804 int pr[N / 10]; 805 int gcd(int a, int b) { 806 while (b) 807 a %= b, swap(a, b); 808 809 return a; 810 } 811 ll ans = 0; 812 bool vis[1011][1011]; 813 pair<int, int> vv[200011]; 814 int vn, c; 815 bool flg = 0; 816 inline ll V(int i, int j) { 817 return i <= n ? 1ll * max(i, j) * max(a, b) + 1ll * min(i, j) * min(a, b) : 1ll * i * b + 1ll * j * a; 818 } 819 void dfs(int i, int j) { 820 ++c; 821 bool mk = gcd(i, j) == 1; 822 823 if (!mk) 824 return; 825 826 ans = max(ans, V(i, j)); 827 vis[m - i][n - j] = 1; 828 vv[++vn] = {i, j}; 829 830 if (j < n && !vis[m - i][n - j - 1]) 831 dfs(i, j + 1); 832 833 if (i == m || flg) { 834 flg = 1; 835 return; 836 } 837 838 if (i < m && !vis[m - i - 1][n - j]) 839 dfs(i + 1, j); 840 } 841 int main() { 842 is[0] = is[1] = 1; 843 844 for (int i = 2; i < N; ++i) { 845 if (!is[i]) 846 pr[++pr[0]] = i; 847 848 for (int j = 1; j <= pr[0] && i * pr[j] < N; ++j) { 849 is[i * pr[j]] = 1; 850 851 if (i % pr[j] == 0) 852 break; 853 } 854 } 855 856 scanf("%d", &t); 857 858 while (t--) { 859 scanf("%d%d%d%d", &n, &m, &a, &b); 860 int p; 861 862 if (m <= 10) 863 p = 1; 864 else { 865 p = m; 866 867 while (is[p]) 868 --p; 869 } 870 871 vn = 0; 872 ans = 0; 873 flg = 0; 874 c = 0; 875 876 for (int i = min(n, p - (p > 1));; --i) { 877 assert(i > 0); 878 ans = max(ans, V(p, i)); 879 880 if (p < m) 881 dfs(p + 1, i); 882 else 883 break; 884 885 if (flg) 886 break; 887 } 888 889 for (int i = 1; i <= vn; ++i) 890 vis[m - vv[i].first][n - vv[i].second] = 0; 891 892 printf("%lld\n", ans); 893 } 894 895 return 0; 896 } 897 ``` 898 899 [2002G — Lattice Optimizing](https://codeforces.com/contest/2002/problem/G) 900 901 idea & solution: [xcyle](/profile/xcyle "International Grandmaster xcyle") 902 903 We apologize for unintended solutions passing, and intended solutions failing with large constants. Brute force runs very fast on $n=18$, which forced us to increase constraints. 904 905 **Hint 1** 906 907 Meet in the middle with a twist. 908 909 **Hint 2** 910 911 Union of sets is hard. Disjoint union of sets is easy. 912 913 **Tutorial** 914 915 The problem hints strongly at meet in the middle, at each side, there will be $O(2^n)$ paths. The twist is on merging: we are given two sequence of sets $S_1,S_2,\cdots$ and $T_1,T_2,\cdots$, we have to find the maximum $\textrm{MEX}(S_i\cup T_j)$. 916 917 If we enumerate over the maximum MEX $P$, we only need to check whether there exists two sets such that $\{ 0,1,\cdots,P-1\} \subseteq S_i\cup T_j$. 918 919 Instead of meeting at $n$, we perform meet in the middle at the partition of $Bn$ and $(2-B)n$. For each $S_i$, we put all its subsets $S^\prime_i$ into a hashmap. When checking MEX $P$, we iterate over all $T_j$, and check whether $\{ 0,1,\cdots,P-1\} -T_j$ is in the hashmap. This gives us a $O((2^{2Bn}+2^{(2-B)n})\cdot n)$ solution, which is optimal at $B=\frac23$, where the complexity is $O(2^{\frac43}\cdot n)$. 920 921 We can substitute enumerating $P$ with binary search, yielding $O(2^{\frac43n}\cdot\log n)$, or checking whether $P$ can be increased each time, yielding $O(2^{\frac43n})$. 922 923 Instead of hashmaps, you can also insert all $S$ and $T$'s into a trie, and run a brute force dfs to search for MEX $P$. It can be proven that the complexity is also $O(2^{\frac43n}\cdot n)$. 924 925 The intended solution is $O(2^{\frac43 n})$, however solutions that have slightly higher complexity can pass with good optimizations. 926 927 Time complexity: $O(2^{\frac43n})$. 928 929 **Solution** 930 931 ``` 932 #include <bits/stdc++.h> 933 #define ll long long 934 using namespace std; 935 int D[111][111], R[111][111], n; 936 const int P = 30000019; 937 struct custom_hash { 938 static uint64_t splitmix64(uint64_t x) { 939 // http://xorshift.di.unimi.it/splitmix64.c 940 x += 0x9e3779b97f4a7c15; 941 x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; 942 x = (x ^ (x >> 27)) * 0x94d049bb133111eb; 943 return x ^ (x >> 31); 944 } 945 946 size_t operator()(uint64_t x) const { 947 static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); 948 return splitmix64(x + FIXED_RANDOM); 949 } 950 } HH; 951 int sta[P], top; 952 struct uset { 953 struct edge { 954 pair<int, ll> v; 955 int next; 956 edge() {} edge(pair<int, ll> _v, int _next) { 957 v = _v; 958 next = _next; 959 } 960 } e[20000011]; 961 int head[P], sz; 962 uset() { 963 memset(head, -1, sizeof(head)); 964 sz = 0; 965 } 966 void insert(pair<int, ll> x) { 967 int u = HH(x.second * n + x.first) % P; 968 sta[++top] = u; 969 970 for (int i = head[u]; ~i; i = e[i].next) 971 if (e[i].v == x) 972 return; 973 974 e[++sz] = edge(x, head[u]); 975 head[u] = sz; 976 } 977 bool find(pair<int, ll> x) { 978 int u = HH(x.second * n + x.first) % P; 979 980 for (int i = head[u]; ~i; i = e[i].next) 981 if (e[i].v == x) 982 return 1; 983 984 return 0; 985 } 986 } st; 987 int B; 988 void dfs1(int x, int y, ll S, int tp) { 989 if (x + y == B) { 990 st.insert({x, S}); 991 return; 992 } 993 994 if (y < n) { 995 dfs1(x, y + 1, S, 0); 996 dfs1(x, y + 1, S | 1ll << R[x][y], -1); 997 } 998 999 if (x < n) { 1000 if (tp != 0) 1001 dfs1(x + 1, y, S, 1); 1002 1003 dfs1(x + 1, y, S | 1ll << D[x][y], -1); 1004 } 1005 } 1006 int ans = 0; 1007 void dfs2(int x, int y, ll S) { 1008 if (x + y == B) { 1009 int res = 0; 1010 1011 while (ans <= 2 * n - 2) { 1012 if (st.find({x, (~S) & (1ll << (ans + 1)) - 1})) 1013 ans++; 1014 else 1015 break; 1016 } 1017 1018 return; 1019 } 1020 1021 if (x > 1) 1022 dfs2(x - 1, y, S | 1ll << D[x - 1][y]); 1023 1024 if (y > 1) 1025 dfs2(x, y - 1, S | 1ll << R[x][y - 1]); 1026 } 1027 void solve() { 1028 while (top) 1029 st.head[sta[top--]] = -1; 1030 1031 st.sz = 0; 1032 ans = 0; 1033 scanf("%d", &n); 1034 1035 for (int i = 1; i < n; ++i) 1036 for (int j = 1; j <= n; ++j) 1037 scanf("%d", D[i] + j); 1038 1039 for (int i = 1; i <= n; ++i) 1040 for (int j = 1; j < n; ++j) 1041 scanf("%d", R[i] + j); 1042 1043 B = 2 * n / 3 + 2; 1044 dfs1(1, 1, 0, -1); 1045 dfs2(n, n, 0); 1046 printf("%d\n", ans); 1047 } 1048 int main() { 1049 int T; 1050 scanf("%d", &T); 1051 1052 while (T--) 1053 solve(); 1054 1055 return 0; 1056 } 1057 ``` 1058 1059 **Solution (trie, LipArcanjo)** 1060 1061 ``` 1062 #include <bits/stdc++.h> 1063 using namespace std; 1064 #define pb push_back 1065 #define mp make_pair 1066 #define fi first 1067 #define se second 1068 #define int long long 1069 void dbg_out() { 1070 cerr << endl; 1071 } 1072 template <typename H, typename... T> 1073 void dbg_out(H h, T... t) { 1074 cerr << ' ' << h; 1075 dbg_out(t...); 1076 } 1077 #define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); } 1078 using ll = long long; 1079 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); 1080 1081 const int MAXN = 3e7 + 5; 1082 const int MOD = 1e9 + 7; //998244353; 1083 const int INF = 0x3f3f3f3f; 1084 const ll INF64 = ll(4e18) + 5; 1085 1086 int D[40][40]; 1087 int R[40][40]; 1088 1089 int L; 1090 1091 int32_t trie[MAXN][2]; 1092 int n; 1093 int li = 1; 1094 void add(int x) { 1095 int at = 0; 1096 int K = 2 * n - 2; 1097 1098 for (int i = 0; i <= K; i++) { 1099 int id = (x >> i) & 1; 1100 1101 if (trie[at][id] == 0) { 1102 trie[at][id] = li++; 1103 } 1104 1105 at = trie[at][id]; 1106 } 1107 } 1108 1109 void limpa() { 1110 for (int i = 0; i < li; i++) { 1111 trie[i][0] = trie[i][1] = 0; 1112 } 1113 1114 li = 1; 1115 } 1116 1117 int query(int at, int x, int dep) { 1118 int id = (x >> dep) & 1; 1119 1120 if (id == 0) { 1121 if (trie[at][1]) { 1122 return query(trie[at][1], x, dep + 1); 1123 } 1124 1125 return dep; 1126 } 1127 1128 int ans = dep; 1129 1130 if (trie[at][0]) 1131 ans = max(ans, query(trie[at][0], x, dep + 1)); 1132 1133 if (trie[at][1]) 1134 ans = max(ans, query(trie[at][1], x, dep + 1)); 1135 1136 while ((x >> ans) & 1) 1137 ans++; 1138 1139 return ans; 1140 } 1141 1142 void rec_in(int i, int j, int tar1, int tar2, int v) { 1143 if (i > tar1 || j > tar2) 1144 return; 1145 1146 if (i == tar1 && j == tar2) { 1147 add(v); 1148 } 1149 1150 int right = v | (1ll << R[i][j]); 1151 int down = v | (1ll << D[i][j]); 1152 rec_in(i + 1, j, tar1, tar2, down); 1153 rec_in(i, j + 1, tar1, tar2, right); 1154 } 1155 1156 int ANS = 0; 1157 void rec_out(int i, int j, int tar1, int tar2, int v) { 1158 if (i < tar1 || j < tar2) 1159 return; 1160 1161 if (i == tar1 && j == tar2) { 1162 ANS = max(ANS, query(0, v, 0)); 1163 return; 1164 } 1165 1166 int left = v | (1ll << R[i][j - 1]); 1167 int up = v | (1ll << D[i - 1][j]); 1168 rec_out(i - 1, j, tar1, tar2, up); 1169 rec_out(i, j - 1, tar1, tar2, left); 1170 } 1171 1172 void solve() { 1173 ANS = 0; 1174 1175 for (int i = 1; i <= li; i++) 1176 trie[i][0] = trie[i][1] = 0; 1177 1178 li = 1; 1179 cin >> n; 1180 L = 4 * n / 3; 1181 1182 for (int i = 0; i < n - 1; i++) { 1183 for (int j = 0; j < n; j++) { 1184 cin >> D[i][j]; 1185 } 1186 } 1187 1188 if (L > n) { 1189 L--; 1190 } 1191 1192 if (L > n) { 1193 L--; 1194 } 1195 1196 if (L > n) { 1197 L--; 1198 } 1199 1200 for (int i = 0; i < n; i++) { 1201 for (int j = 0; j < n - 1; j++) { 1202 cin >> R[i][j]; 1203 } 1204 } 1205 1206 for (int i = 0; i < n; i++) 1207 for (int j = 0; j < n; j++) 1208 if (i + j == L) { 1209 limpa(); 1210 rec_in(0, 0, i, j, 0); 1211 rec_out(n - 1, n - 1, i, j, 0); 1212 } 1213 1214 cout << ANS << '\n'; 1215 1216 } 1217 1218 signed main() { 1219 ios::sync_with_stdio(false); 1220 cin.tie(NULL); 1221 1222 int t = 1; 1223 cin >> t; 1224 1225 while (t--) { 1226 solve(); 1227 } 1228 1229 return 0; 1230 } 1231 ``` 1232 1233 [2002H — Counting 101](https://codeforces.com/contest/2002/problem/H) 1234 1235 idea: [le0n](/profile/le0n "International Grandmaster le0n"), [xcyle](/profile/xcyle "International Grandmaster xcyle"), solution: [le0n](/profile/le0n "International Grandmaster le0n"), [xcyle](/profile/xcyle "International Grandmaster xcyle") 1236 1237 **Hint 1** 1238 1239 Try to solve Problem 101 with any approach. 1240 1241 **Hint 2** 1242 1243 Can you express the states in the solution for Problem 101 with some simple structures? Maybe dp of dp? 1244 1245 **Hint 3** 1246 1247 Try finding some unnecessary states and pruning them, to knock a $n$ off the complexity. 1248 1249 **Tutorial** 1250 1251 We analyse Problem 101 first. A dp solution will be, let $f_{l,r,v}$ be the minimum number of elements left after some operations, if we only consider elements in $a[l:r]$, without creating any elements $ \gt v$. If $\max(a[l:r]) \lt v$, then the answer is $1$ if $r-l+1$ is odd, and $2$ otherwise. We simply repeatedly perform operations with middle element as the center. It is easy to see that this is optimal. 1252 1253 If $\max(a[l:r])=v$, then $a[l:r]$ will be partitioned into blocks by elements equal to $v$. Denote the length of the blocks as $y_1,y_2,\cdots,y_l$. Let $b_i$ be the number of operations that has the $i$-th element with value $v$ as its center. 1254 1255 We can perform a dp as follows: let $g_{i,j}$ be the minimum number of elements left if we have already considered the first $i$ blocks, and $b_i=j$. 1256 1257 When adding a new block, we need to know several things: 1258 1259 * $[l^\prime,r^\prime]$, the minimum/maximum number of elements of the new block after some operations, without creating an element greater than $v-1$. 1260 * $j_2$, the value of $b_{i+1}$. 1261 1262 The transition of the dp will be: $g_{i+1,j_2}=g_{i,j_1}+cost(j_1+j_2,l^\prime,r^\prime)$, where $cost(j,l,r)$ is defined as follows: 1263 1264 $ cost(j,l,r)=\left\{ \begin{aligned} +\infty,&&j \gt r\\ 0,&&l\le j\le r, j\equiv l\pmod2\\ 1,&&j\le r,j\not\equiv l\pmod2\\ 2,&&j \lt l, j\equiv l\pmod2\\ \end{aligned} \right. $ 1265 1266 The $cost$ function follows from the case where $\max(a) \lt v$. 1267 1268 Now, we have a solution to Problem 101. We now consider generalizing it to Counting 101. 1269 1270 We make some observations regarding the structure of $g$. If you printed a table of $g$, you would discover that for each $g_i$, if you subtract the minimum element from all $g_{i,j}$ in this row, you will get something like: $[\cdots,2,1,2,1,2,1,0,1,0,1,0,1,0,1,2,1,2,\cdots]$. 1271 1272 We can prove this by induction and some casework, which is omitted for brevity. If a $g_i$ satisfies this property, then we can express it with a triple $(l,r,mn)$, where $mn$ is the minimum element of $g_i$, and $l,r$ are the minimum/maximum $j$ such that $g_{i,j}=mn$. 1273 1274 Now that we can express the structure of each $g_i$ with a triple $(l,r,mn)$, we can run a dp of dp. Our state will be $dp_{i,v,l,r,mn}$, where $i$ is the current length, $v$ is the upper bound, and $(l,r,mn)$ describes the current $g$. For each transition, we need to enumerate $l^\prime,r^\prime$, and the new $(l,r,mn)$ can be found in $O(1)$ with some casework. This gives us an $O(n^6m)$ solution. 1275 1276 Now to optimize the solution. We optimize the solution by reducing the number of viable states. Suppose we have a state $+(l,r,mn)$, we claim, that the answer will remain the same if we replace it with $+(l,\infty,mn)+(l\bmod2,r,mn)-(l\bmod2,\infty,mn)$. 1277 1278 We prove this by examining their behaviour when we add any number of blocks after them. If the answer remains unchanged for any blocks we can add, then the claim stands. Suppose we are at $g_i$, and we will add a sequence of blocks $S$ after $g_i$. The final answer can be found by running a backwards dp similar to $g$, on $\text{rev}(S)$, and merging with $g_i$ in the middle. 1279 1280 If we denote the backwards dp as $g^\prime$, then the answer will be $\min(g_j+g^\prime_j)$ over all $j$. It can be shown after some brief casework (using $g$'s structure), that there exists an optimal $j$ where $g_{i,j}$ is the minimum of $g_i$, thus the answer is just a range (with a certain parity) min of $g^\prime$, plus $mn$. Because $g^\prime$ also follow $g$'s structure, any range will be first decreasing, then increasing. It can be shown with these properties, $\min(g^\prime[l:r])=\min(g^\prime[l:\infty])+\min(g^\prime[l\bmod2:r])-\min(g^\prime[l\bmod2:\infty])$. Thus, our answer will not change when substituting the states. 1281 1282 After substituting, the total number of different $l,r$ pairs will be $O(n)$, which yields an $O(n^5m)$ solution. 1283 1284 The solution can also be optimized to $O(n^4m)$ using Lagrange Interpolation, but it actually runs slower than $O(n^5m)$ because of large constants (or bad implementation by setters). 1285 1286 **Solution (orzdevinwang)** 1287 1288 ``` 1289 #include <bits/stdc++.h> 1290 #pragma comment(linker, "/stack:200000000") 1291 #pragma GCC optimize("Ofast") 1292 #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") 1293 #define L(i, j, k) for(int i = (j); i <= (k); ++i) 1294 #define R(i, j, k) for(int i = (j); i >= (k); --i) 1295 #define ll long long 1296 #define vi vector <int> 1297 #define sz(a) ((int) (a).size()) 1298 #define me(f, x) memset(f, x, sizeof(f)) 1299 #define ull unsigned long long 1300 #define pb emplace_back 1301 using namespace std; 1302 const int N = 133, mod = 1e9 + 7; 1303 struct mint { 1304 int x; 1305 inline mint(int o = 0) { 1306 x = o; 1307 } 1308 inline mint &operator = (int o) { 1309 return x = o, *this; 1310 } 1311 inline mint &operator += (mint o) { 1312 return (x += o.x) >= mod && (x -= mod), *this; 1313 } 1314 inline mint &operator -= (mint o) { 1315 return (x -= o.x) < 0 && (x += mod), *this; 1316 } 1317 inline mint &operator *= (mint o) { 1318 return x = (ll) x * o.x % mod, *this; 1319 } 1320 inline mint &operator ^= (int b) { 1321 mint w = *this; 1322 mint ret(1); 1323 1324 for (; b; b >>= 1, w *= w) 1325 if (b & 1) 1326 ret *= w; 1327 1328 return x = ret.x, *this; 1329 } 1330 inline mint &operator /= (mint o) { 1331 return *this *= (o ^= (mod - 2)); 1332 } 1333 friend inline mint operator + (mint a, mint b) { 1334 return a += b; 1335 } 1336 friend inline mint operator - (mint a, mint b) { 1337 return a -= b; 1338 } 1339 friend inline mint operator * (mint a, mint b) { 1340 return a *= b; 1341 } 1342 friend inline mint operator / (mint a, mint b) { 1343 return a /= b; 1344 } 1345 friend inline mint operator ^ (mint a, int b) { 1346 return a ^= b; 1347 } 1348 }; 1349 inline mint qpow(mint x, int y = mod - 2) { 1350 return x ^ y; 1351 } 1352 mint fac[N], ifac[N], inv[N]; 1353 void init(int x) { 1354 fac[0] = ifac[0] = inv[1] = 1; 1355 L(i, 2, x) inv[i] = (mod - mod / i) * inv[mod % i]; 1356 L(i, 1, x) fac[i] = fac[i - 1] * i, ifac[i] = ifac[i - 1] * inv[i]; 1357 } 1358 mint C(int x, int y) { 1359 return x < y || y < 0 ? 0 : fac[x] * ifac[y] * ifac[x - y]; 1360 } 1361 inline mint sgn(int x) { 1362 return (x & 1) ? mod - 1 : 1; 1363 } 1364 1365 int n, m; 1366 mint f[N][N]; 1367 mint g[N][N]; 1368 mint h1[N][N][N]; 1369 mint h2[N][N][N]; 1370 mint pw[N][N]; 1371 int ans[N][N][N]; 1372 int main() { 1373 ios :: sync_with_stdio(false); 1374 cin.tie(0); 1375 cout.tie(0); 1376 n = 130, m = 30; 1377 // n = m = 10; 1378 L(i, 0, max(n, m)) { 1379 pw[i][0] = 1; 1380 L(j, 1, max(n, m)) pw[i][j] = pw[i][j - 1] * i; 1381 } 1382 f[0][0] = 1; 1383 int c1 = 0, c2 = 0; 1384 L(test, 1, m) { 1385 me(g, 0); 1386 int up = n; 1387 L(i, 0, up + 1) L(j, 0, i) L(l, 0, i) h1[i][j][l] = h2[i][j][l] = 0; 1388 h2[0][0][0] = 1; 1389 L(i, 0, up + 1) { 1390 L(j, 0, i) L(l, 0, i) h1[i][j][l & 1] -= h1[i][j][l]; 1391 L(j, 0, i) { 1392 for (int l = (i - j) & 1; l <= i; l += 2) 1393 if (h1[i][j][l].x) { 1394 L(k, 0, up - i) { 1395 if (l > k) { 1396 int tr = k - !(l & 1); 1397 1398 if (tr < 0) 1399 h2[i + k + 1][j + 3][0] += h1[i][j][l] * pw[test - 1][k]; 1400 else 1401 h2[i + k + 1][j + 2][tr] += h1[i][j][l] * pw[test - 1][k]; 1402 } else { 1403 h2[i + k + 1][j + 1][k - l] += h1[i][j][l] * pw[test - 1][k]; 1404 } 1405 } 1406 } 1407 1408 for (int r = (i - j) & 1; r <= i; r += 2) 1409 if (h2[i][j][r].x) { 1410 int l = r & 1; 1411 L(k, 0, up - i) { 1412 if (l > k) { 1413 int tr = k - !(r & 1); 1414 1415 if (tr < 0) 1416 h2[i + k + 1][j + 3][0] += h2[i][j][r] * pw[test - 1][k]; 1417 else 1418 h2[i + k + 1][j + 2][tr] += h2[i][j][r] * pw[test - 1][k]; 1419 } else { 1420 h2[i + k + 1][j + 1][k - l] += h2[i][j][r] * pw[test - 1][k]; 1421 1422 L(d, r + 1, k) if (f[k][d].x) 1423 h1[i + k + 1][j + 1][d - r] += h2[i][j][r] * f[k][d]; 1424 } 1425 } 1426 } 1427 } 1428 } 1429 // cout << "H = " << h[1][1][0][0].x << endl; 1430 L(i, 1, up + 1) 1431 L(j, 1, i) { 1432 1433 L(l, 0, i) if (h1[i][j][l].x) { 1434 if (!l) 1435 g[i - 1][j - 1] += h1[i][j][l]; 1436 else 1437 g[i - 1][j - 1 + (l % 2 == 0 ? 2 : 1)] += h1[i][j][l]; 1438 } 1439 1440 L(r, 0, i) if (h2[i][j][r].x) { 1441 if (!(r & 1)) 1442 g[i - 1][j - 1] += h2[i][j][r]; 1443 else 1444 g[i - 1][j - 1 + (r % 2 == 0 ? 2 : 1)] += h2[i][j][r]; 1445 } 1446 } 1447 L(i, 1, up) { 1448 mint vl = 0; 1449 1450 if (i == 1) 1451 vl = test; 1452 else if (i % 2 == 1) { 1453 vl += pw[test - 1][i]; 1454 L(p, 1, i - 2) { 1455 int l = p, r = i - p - 1; 1456 1457 if (l > r) 1458 swap(l, r); 1459 1460 L(j, 1, l) { 1461 vl += f[r][j] * pw[test - 1][l]; 1462 } 1463 } 1464 } 1465 1466 g[i][1] = vl; 1467 mint sum = 0; 1468 L(j, 1, i) sum += g[i][j]; 1469 int pos = (i & 1) ? 3 : 2; 1470 g[i][pos] += pw[test][i] - sum; 1471 } 1472 swap(f, g); 1473 1474 for (int i = 0; i <= n; i++) { 1475 for (int j = 0; j <= n; j++) { 1476 ans[test][i][j] = f[i][j].x; 1477 } 1478 } 1479 } 1480 // cout << "clock = " << clock() << endl; 1481 int T; 1482 cin >> T; 1483 1484 while (T--) { 1485 int N, M; 1486 cin >> N >> M; 1487 L(i, 0, (N - 1) / 2) 1488 cout << ans[M][N][N - i * 2] << " "; 1489 cout << '\n'; 1490 } 1491 1492 return 0; 1493 } 1494 ```