codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ![image-20240808190606837](/predownloaded/7d/f8/7df8b1f86c41d8f9fa1cf41187105821f00ac315.png)
    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 ```