2275.md (22175B)
1 Source: https://codeforces.com/blog/entry/157528 2 3 Thank you all for participating! 4 5 [2275A - In Search of Convenience](/contest/2275/problem/A "Codeforces Round 1125 (Div. 3)") 6 7 **Solution** 8 9 The point $(x_0 - R, y_0)$ always lies on the circle because $(x_0 - (x_0 - R))^2 + (y_0 - y_0)^2 = R^2$ holds for every $R$: after expanding the parentheses, we get $R^2 = R^2$. 10 11 **Code** 12 13 ``` 14 #include <bits/stdc++.h> 15 using namespace std; 16 #define all(x) x.begin(), x.end() 17 18 signed main() { 19 int tt; 20 cin >> tt; 21 while (tt --> 0) { 22 int x, y, R; 23 cin >> x >> y >> R; 24 cout << x - R << " " << y << endl; 25 } 26 } 27 ``` 28 29 [2275B - Did Not Go to Print](/contest/2275/problem/B "Codeforces Round 1125 (Div. 3)") 30 31 **Solution** 32 33 Let us create a boolean array $\text{used}$ and use it to mark which documents have been printed. For an operation of type 3, we simply set $\text{used}_i = 1$. Operations of types 1 and 2 are essentially the push and pop operations of a stack. Let us also create a stack $\operatorname{memory}$. For an operation of type 1, we push the document number onto the stack. For an operation of type 2, we pop the top element and set $\text{used}[\operatorname{memory}.\text{top}()] = 1$. We should also handle the case when $\operatorname{memory}$ is empty. Finally, we iterate over the $\text{used}$ array and output all unmarked elements. The time complexity is $O(n)$. 34 35 **Code** 36 37 ``` 38 #include <bits/stdc++.h> 39 using namespace std; 40 #define all(x) x.begin(), x.end() 41 42 int main() { 43 int t; 44 cin >> t; 45 while (t --> 0) { 46 int n; 47 string s; 48 cin >> n >> s; 49 vector<int> stack_; 50 vector<bool> used(n); 51 for (int i = 0; i < n; ++i) { 52 if (s[i] == '1') { 53 stack_.push_back(i); 54 } else if (s[i] == '2') { 55 if (stack_.empty()) { 56 used[i] = true; 57 } else { 58 used[stack_.back()] = true; 59 stack_.pop_back(); 60 } 61 } else { 62 used[i] = true; 63 } 64 } 65 vector<int> res; 66 for (int i = 0; i < n; ++i) { 67 if (!used[i]) { 68 res.push_back(i + 1); 69 } 70 } 71 cout << res.size() << '\n'; 72 for (auto &x : res) { 73 cout << x << " "; 74 } 75 cout << '\n'; 76 } 77 return 0; 78 } 79 ``` 80 81 [2275C - Unrequited Love](/contest/2275/problem/C "Codeforces Round 1125 (Div. 3)") 82 83 **Solution** 84 85 Let $f(x) = a_x + a_{x+2} - a_{x+4}$ be the value of the triad starting at $x$. Two triads $x \lt y$ intersect only if $y - x = 2$ or $y - x = 4$. Therefore, the answer is the number of pairs $x \lt y$ such that $f(x) = f(y)$, minus the pairs satisfying the same equality for which $y - x \in {2, 4}$. 86 87 We process $y$ from left to right and use a map to store how many times each value of $f$ has occurred. We add the number of previous occurrences of $f(y)$ to the answer. Then we separately subtract $1$ if $f(y - 2) = f(y)$ and another $1$ if $f(y - 4) = f(y)$: these pairs have just been counted, but their triads intersect. The answer can be as large as $\sim 2\cdot10^{10}$, so a 64-bit integer type (`long long`) is required. 88 89 The time complexity is $O(n \log n)$ due to the use of a map. 90 91 **Code** 92 93 ``` 94 #include <bits/stdc++.h> 95 using namespace std; 96 #define int long long 97 #define all(x) x.begin(), x.end() 98 99 signed main() { 100 int tt; 101 cin >> tt; 102 while (tt --> 0) { 103 int n; 104 cin >> n; 105 vector<int> a(n); 106 for (auto &x : a) cin >> x; 107 vector<int> arr; 108 map<int, int> mp; 109 int ans = 0; 110 for (int i = 0; i < n - 4; i++) { 111 int cur = a[i] + a[i + 2] - a[i + 4]; 112 ans += mp[cur]; 113 if (i >= 2 && arr[i - 2] == cur) ans--; 114 if (i >= 4 && arr[i - 4] == cur) ans--; 115 mp[cur]++; 116 arr.push_back(cur); 117 } 118 cout << ans << endl; 119 } 120 } 121 ``` 122 123 [2275D - Precision Alignment](/contest/2275/problem/D "Codeforces Round 1125 (Div. 3)") 124 125 **Solution** 126 127 There are formally three cases: 128 129 * $a_i = b_i = c_i$: the triple does not change, so the answer cannot become greater than $a_i + b_i + c_i$; 130 * $a_i \le b_i \le c_i$: to leave this state, we have to use operations that decrease some elements (more details below); 131 * $a_i \gt b_i \ \lor \ a_i \gt c_i \ \lor \ b_i \gt c_i$: we can simply keep increasing the sum indefinitely because only the third element changes, while the other two remain unchanged. 132 133 What should we do in a state with $a_i \le b_i \le c_i$? 134 135 We need to obtain either $c_i = b_i - 1$ or $b_i = a_i - 1$. After that, we can increase the sum indefinitely. 136 137 Therefore, in this case, the cost of increasing $S = a_i + b_i + c_i$ to $m$ can be written as 138 139 $\mathrm{cost}(m) \;=\; \begin{cases} 0, & S \ge m, \\ +\infty, & S \lt m,\ a=b=c, \\ (m-S) + 2e, & \text{otherwise}, \end{cases}$ 140 141 where $e = \min(b-a,c-b)+1$. 142 143 This function is monotonic, so we can binary-search the answer while handling all triples with $a_i = b_i = c_i$ separately. The time complexity is $O(n \log k)$. 144 145 **Code** 146 147 ``` 148 #include <bits/stdc++.h> 149 using namespace std; 150 #define int long long 151 152 signed main() { 153 int t; 154 cin >> t; 155 while (t --> 0) { 156 int n; 157 int k; 158 cin >> n >> k; 159 160 vector<int> S(n), E(n); 161 vector<int> dead(n); 162 163 const int BIG = numeric_limits<int>::max() / 4; 164 int lo = BIG, cap = BIG; 165 166 vector<int> A(n), B(n), C(n); 167 for (int i = 0; i < n; i++) cin >> A[i] >> B[i] >> C[i]; 168 169 for (int i = 0; i < n; i++) { 170 int a = A[i], b = B[i], c = C[i]; 171 S[i] = a + b + c; 172 dead[i] = (a == b && b == c); 173 E[i] = (a <= b && b <= c) ? min(b - a, c - b) + 1 : 0LL; 174 lo = min(lo, S[i]); 175 if (dead[i]) cap = min(cap, S[i]); 176 } 177 178 int hi = min(cap, lo + k) + 1; 179 180 auto is_ok = [&](int m){ 181 int total = 0; 182 for (int i = 0; i < n; i++) { 183 if (S[i] >= m) continue; 184 if (dead[i]) return 0; 185 total += (m - S[i]) + 2 * E[i]; 186 if (total > k) return 0; 187 } 188 return 1; 189 }; 190 191 while (hi - lo > 1) { 192 int mid = (hi + lo) / 2; 193 if (is_ok(mid)) lo = mid; 194 else hi = mid; 195 } 196 cout << lo << '\n'; 197 } 198 } 199 ``` 200 201 [2275E - Repentance Is Already on the Way](/contest/2275/problem/E "Codeforces Round 1125 (Div. 3)") 202 203 **Solution** 204 205 The roads connect only buildings on opposite sides, so the route alternates between the two sides, uses exactly $2n - 1$ roads, and has length $2n - 1 + (\text{the number of roads connecting buildings of the same company})$. Let us determine which routes are possible. Suppose K1o0n is at $a_k$, and all columns to the left have already been visited. If he moves to $b_k$, the only remaining move from there is to $a_{k+1}$, and we reach the same situation in column $k+1$. If instead he moves diagonally to $b_{k+1}$, then the only remaining unvisited neighbor of $b_k$ is $a_{k+1}$, so $b_k$ must be an endpoint of the route. From this point on, the entire route is forced: first, follow the zigzag $a_k \to b_{k+1} \to a_{k+2} \to \ldots$ to the end, cross to the other side using the road $a_n-b_n$, and then follow the second zigzag back to $b_k$. Therefore, every route is determined by a single number $k$: first, it follows the “snake” $a_1 \to b_1 \to a_2 \to \ldots \to b_{k-1} \to a_k$, and then forms a loop to the end and back. 206 207  208 209 There are $n$ possible routes in total. We first calculate the length for $k=1$ (two zigzags and the road $a_n-b_n$). Moving from $k$ to $k+1$ replaces exactly one road: $a_k-b_{k+1}$ is replaced with $a_k-b_k$. Thus, we can obtain the length of each next route from the previous one in $O(1)$ time and take the maximum. The total time complexity is $O(n)$. 210 211 **Code** 212 213 ``` 214 #include <bits/stdc++.h> 215 using namespace std; 216 217 signed main() { 218 auto f = [](int x, int y) { 219 return 1 + (x == y); 220 }; 221 int tt; 222 cin >> tt; 223 while (tt --> 0) { 224 int n; 225 cin >> n; 226 227 vector<int> a(n), b(n); 228 for (auto &x : a) cin >> x; 229 for (auto &x : b) cin >> x; 230 231 int current = f(a.back(), b.back()); 232 for (int i = 0; i + 1 < n; i++) { 233 current += f(a[i + 1], b[i]); 234 current += f(a[i], b[i + 1]); 235 } 236 237 int answer = current; 238 239 for (int i = 0; i + 1 < n; i++) { 240 current -= f(a[i], b[i + 1]); 241 current += f(a[i], b[i]); 242 answer = max(answer, current); 243 } 244 245 cout << answer << '\n'; 246 } 247 } 248 ``` 249 250 [2275F - Tea Blend](/contest/2275/problem/F "Codeforces Round 1125 (Div. 3)") 251 252 **Solution** 253 254 Let us determine when a number $x$ has an odd number of divisors. Consider its prime factorization $x = p_1^{d_1} p_2^{d_2} \ldots p_k^{d_k}$. The number of divisors is $\prod (d_i + 1)$. For it to be odd, every factor must be odd, which means that every exponent $d_i$ must be even. $F(i, j)$ is the product of two values, and every prime occurs in it with an even exponent if and only if the sets of primes occurring with odd exponents in the two factors are equal. For every prefix, we will store the set of primes that occur in its product with odd exponents. 255 256 Note that we do not have to store all such sets. If a set contains more than $7$ primes, their product is guaranteed to be greater than any $a_i$, while a single spoonful would have to contain all of them at once. Therefore, such a prefix cannot be turned into a perfect square using any single $a_i$. Thus, we maintain a map only for suitable sets rather than for all of them. The answer is then the sum, over all $a_i$, of the number of prefixes whose set of primes with odd exponents is equal to that of $a_i$. The time complexity is $O(n \log (7n))$; here, the constant $7$ denotes the maximum possible number of distinct prime divisors of a number not exceeding $10^6$. 257 258 **Code** 259 260 ``` 261 #include <bits/stdc++.h> 262 using namespace std; 263 #define all(x) x.begin(), x.end() 264 265 signed main() { 266 vector<int> primes; 267 vector<bool> is_prime(32000 + 1, 1); 268 is_prime[0] = is_prime[1] = 0; 269 for (int i = 2; i <= 32000; i++) { 270 if (is_prime[i]) { 271 primes.push_back(i); 272 for (int j = i * i; j <= 32000; j += i) { 273 is_prime[j] = 0; 274 } 275 } 276 } 277 278 int t; 279 cin >> t; 280 while (t --> 0) { 281 int n; 282 cin >> n; 283 vector<int> a(n); 284 for (auto &x : a) cin >> x; 285 286 vector<vector<int>> ker(n); 287 for (int i = 0; i < n; i++) { 288 int x = a[i]; 289 for (int j = 0; j < primes.size() && primes[j] * primes[j] <= x; j++) { 290 if (x % primes[j] == 0) { 291 int e = 0; 292 while (x % primes[j] == 0) { x /= primes[j]; e++; } 293 if (e & 1) ker[i].push_back(primes[j]); 294 } 295 } 296 if (x > 1) ker[i].push_back(x); 297 } 298 299 map<vector<int>, int> mp; 300 set<int> odd; 301 for (int i = 0; i < n; i++) { 302 for (int p : ker[i]) 303 if (!odd.insert(p).second) odd.erase(p); 304 if (odd.size() <= 7) 305 mp[vector<int>(all(odd))]++; 306 } 307 308 long long ans = 0; 309 for (int i = 0; i < n; i++) { 310 auto it = mp.find(ker[i]); 311 if (it != mp.end()) ans += it->second; 312 } 313 cout << ans << "\n"; 314 } 315 } 316 ``` 317 318 [2275G - Copper Squander](/contest/2275/problem/G "Codeforces Round 1125 (Div. 3)") 319 320 **Solution** 321 322 First, let us determine which cables should be kept. Suppose that $r$ old cables remain in the end and form a forest. Then the forest has $n-r$ connected components, so the crew will have to install $n-r-1$ new cables. We sell everything that we do not keep. Therefore, for a fixed $r$, it is optimal to keep the cheapest $r$ cables that still form a forest. These are exactly the first $r$ edges selected by Kruskal's algorithm, that is, the $r$ cheapest edges of the minimum spanning forest. 323 324 This gives us the solution. For each connected component, construct a minimum spanning tree and immediately sell every edge that does not belong to these trees: keeping such an edge is never useful for any value of $x$. If there are $c$ components, connecting them requires $c-1$ new cables and costs $x + 2x + \ldots + (c-1)x = x \cdot \frac{c(c-1)}{2}$. 325 326 We can then sell some edges of the spanning forest as well, starting with the most expensive ones. Each removed edge splits one component into two, so one additional cable has to be installed: the first such cable costs $x \cdot c$, the second costs $x \cdot (c+1)$, and so on. Let the edges of the spanning forest be sorted in non-increasing order: $e_1 \ge e_2 \ge \ldots$. Removing the $i$-th edge is beneficial exactly when $e_i \gt x \cdot (c+i-1)$. The left-hand side decreases while the right-hand side increases, so the beneficial edges form a prefix. For each scenario, we find the length of this prefix using binary search. Prefix sums of $e_i$ then allow us to calculate the answer in $O(1)$. 327 328 The total time complexity is $O(m \log m)$ for Kruskal's algorithm and $O(\log n)$ per scenario. The profit may be negative if there are many components, and the installation costs can reach $5 \cdot 10^8 \cdot \frac{10^5 \cdot (10^5-1)}{2} \approx 2.5 \cdot 10^{18}$, so a 64-bit integer type is required. 329 330 **Code** 331 332 ``` 333 #include <bits/stdc++.h> 334 using namespace std; 335 #define int long long 336 #define all(x) x.begin(), x.end() 337 338 struct Dsu { 339 vector<int> p, rank_; 340 explicit Dsu(int n) : p(n), rank_(n, 0) { iota(p.begin(), p.end(), 0); } 341 int find(int x) { 342 while (p[x] != x) x = p[x] = p[p[x]]; 343 return x; 344 } 345 bool unite(int a, int b) { 346 a = find(a); b = find(b); 347 if (a == b) return false; 348 if (rank_[a] < rank_[b]) swap(a, b); 349 p[b] = a; 350 if (rank_[a] == rank_[b]) ++rank_[a]; 351 return true; 352 } 353 }; 354 355 signed main() { 356 int t; 357 cin >> t; 358 while (t --> 0) { 359 int n, m, q; 360 cin >> n >> m >> q; 361 vector<array<int, 3>> edges(m); // {d, u, v} 362 int total = 0; 363 for (int i = 0; i < m; i++) { 364 int u, v, d; 365 cin >> u >> v >> d; 366 edges[i] = {d, u - 1, v - 1}; 367 total += d; 368 } 369 sort(edges.begin(), edges.end()); 370 371 Dsu dsu(n); 372 vector<int> w; 373 w.reserve(min(m, n - 1)); 374 for (auto &e : edges) 375 if (dsu.unite(e[1], e[2])) w.push_back(e[0]); 376 int top = w.size(); 377 vector<int> pref(top + 1, 0); 378 for (int i = 0; i < top; i++) pref[i + 1] = pref[i] + w[i]; 379 380 for (int i = 0; i < q; i++) { 381 int x; 382 cin >> x; 383 int lo = 0, hi = top; 384 while (lo < hi) { 385 int mid = lo + (hi - lo) / 2; 386 if (w[mid] - x * (n - mid - 1) >= 0) hi = mid; 387 else lo = mid + 1; 388 } 389 int k = n - lo - 1; 390 int cost = pref[lo] + x * (k * (k + 1) / 2); 391 cout << total - cost << " "; 392 } 393 cout << endl; 394 } 395 } 396 ``` 397 398 [2275H - A Problem to Warm Up the Eyebrows](/contest/2275/problem/H "Codeforces Round 1125 (Div. 3)") 399 400 **Solution** 401 402 For the submatrix $[lx, ly, rx, ry]$, write $S^2$ as 403 404 $ (a_{lx,ly}+\ldots+a_{rx,ry}) (a_{lx,ly}+\ldots+a_{rx,ry}). $ 405 406 Let us change the order of summation: we will choose a pair of cells $(i,j)$ and $(x,y)$ and consider the contribution of this pair to the total sum. It is equal to 407 408 $ \sum_{p=0}^{\min(i,x)} \sum_{q=\max(i,x)}^{n-1} \sum_{r=0}^{\min(j,y)} \sum_{s=\max(j,y)}^{m-1} (-1)^{q-p+1+s-r+1}a_{i,j}a_{x,y}. $ 409 410 Since only the parity of the exponent matters, this expression is equal to 411 412 $ a_{i,j}a_{x,y} \sum_{p=0}^{\min(i,x)} \sum_{q=\max(i,x)}^{n-1} \sum_{r=0}^{\min(j,y)} \sum_{s=\max(j,y)}^{m-1} (-1)^{p+q+r+s}. $ 413 414 Let us group the factors: 415 416 $ a_{i,j}a_{x,y} \left(\sum_{p=0}^{\min(i,x)}(-1)^p\right) \left(\sum_{q=\max(i,x)}^{n-1}(-1)^q\right) \left(\sum_{r=0}^{\min(j,y)}(-1)^r\right) \left(\sum_{s=\max(j,y)}^{m-1}(-1)^s\right). $ 417 418 Notice that only the parity of the minimum and maximum row and column indices matters. Rewriting the expression, we obtain 419 420 $ \begin{aligned} (-1)^{n+m} \sum_{i,j}\sum_{x,y} a_{i,j}a_{x,y} &[\min(i,x)\equiv_2 0] [n-\max(i,x)\equiv_2 1] \\ &\cdot[\min(j,y)\equiv_2 0] [m-\max(j,y)\equiv_2 1]. \end{aligned} $ 421 422 Let us calculate the sum over pairs of distinct cells $(x,y) \lt (i,j)$, where pairs are compared lexicographically. We multiply their contribution by $2$ and then separately add the contribution of pairs consisting of the same cell: 423 424 $ \sum_{i,j} a_{i,j}^2. $ 425 426 We divide the contribution of pairs of distinct cells into two more cases: $i=x$ and $x \lt i$. 427 428 **Cells in the same row.** 429 430 We calculate the first contribution separately for each row. We iterate over the row from left to right, maintain the sum of the elements in even-numbered columns, and add this sum multiplied by $a_{i,j}$ if $(n-i)\equiv_2 1$. 431 432 **Cells in different rows.** 433 434 We calculate the second contribution by processing the rows in increasing order. For an element $(i,j)$, we separately consider elements from previous rows whose column index is greater than $j$ and those whose column index is at most $j$. Depending on this comparison, different parity conditions are imposed on $j$ and $y$. 435 436 We maintain prefix and suffix sums over cells whose column indices have the required parity in all previous rows. After processing the current row, we calculate these prefix and suffix sums for it and add them to the accumulated sums. 437 438 The total time complexity is $O(nm)$. 439 440 **Code** 441 442 Credits: [Noobish_Monk](/profile/Noobish_Monk "Master Noobish_Monk") 443 444 ``` 445 #include <bits/stdc++.h> 446 447 using namespace std; 448 449 using ll = long long; 450 using pii = pair<int, int>; 451 452 template <uint32_t MOD> 453 struct ModularInt { 454 int x = 0; 455 456 ModularInt() {} 457 458 ModularInt(int x) : x(x < 0 ? x + MOD : x % MOD) {} 459 460 ModularInt(const ModularInt &other) : x(other.x) {} 461 462 ModularInt operator+=(const ModularInt &other) { 463 x += other.x; 464 if (x >= MOD) 465 x -= MOD; 466 return *this; 467 } 468 469 ModularInt operator-=(const ModularInt &other) { 470 x -= other.x; 471 if (x < 0) 472 x += MOD; 473 return *this; 474 } 475 476 ModularInt operator*=(const ModularInt &other) { 477 x = ((ll)x * other.x) % MOD; 478 return *this; 479 } 480 481 ModularInt power(ll pw) const { 482 ModularInt a(*this); 483 ModularInt b = 1; 484 for (; pw; pw >>= 1, a *= a) 485 if (pw & 1) 486 b *= a; 487 return b; 488 } 489 490 ModularInt inv() const { 491 return power(MOD - 2); 492 } 493 494 ModularInt operator/=(const ModularInt &other) { 495 x = ((ll)x * other.inv().x) % MOD; 496 return *this; 497 } 498 499 bool operator==(const ModularInt &other) { 500 return x == other.x; 501 } 502 503 bool operator!=(const ModularInt &other) { 504 return x != other.x; 505 } 506 507 friend ModularInt operator+(const ModularInt &a, const ModularInt &b) { 508 return ModularInt(a) += b; 509 } 510 511 friend ModularInt operator-(const ModularInt &a, const ModularInt &b) { 512 return ModularInt(a) -= b; 513 } 514 515 friend ModularInt operator*(const ModularInt &a, const ModularInt &b) { 516 return ModularInt(a) *= b; 517 } 518 519 friend ModularInt operator/(const ModularInt &a, const ModularInt &b) { 520 return ModularInt(a) /= b; 521 } 522 523 friend istream& operator>>(istream& in, ModularInt& other) { 524 int x; 525 in >> x; 526 if (x < 0) 527 x += MOD; 528 x %= MOD; 529 other = x; 530 return in; 531 } 532 533 friend ostream& operator<<(ostream& out, const ModularInt& other) { 534 return out << other.x; 535 } 536 }; 537 538 const int mod = 1e9 + 7; 539 using mint = ModularInt<mod>; 540 541 mint calc_row(const vector<mint> &a) { 542 int n = a.size(); 543 mint ans = 0; 544 mint sum = 0; 545 for (int i = 0; i < n; i++) { 546 if ((n - i) % 2 == 1) 547 ans += sum * a[i]; 548 if (i % 2 == 0) 549 sum += a[i]; 550 } 551 return ans; 552 } 553 554 inline void solve() { 555 int n, m; 556 cin >> n >> m; 557 vector a(n, vector<mint>(m)); 558 for (int i = 0; i < n; i++) 559 for (int j = 0; j < m; j++) 560 cin >> a[i][j]; 561 mint ans = 0; 562 int sgn = 1; 563 if (n % 2 == 1) 564 sgn *= -1; 565 if (m % 2 == 1) 566 sgn *= -1; 567 for (int i = 0; i < n; i++) 568 if (i % 2 == 0 && (n - i) % 2 == 1) 569 ans += calc_row(a[i]); 570 vector<mint> psum_min(m), psum_max(m), tmp(m); 571 for (int i = 0; i < n; i++) { 572 if ((n - i) % 2 == 1) { 573 for (int j = 0; j < m - 1; j++) 574 if (j % 2 == 0) 575 ans += a[i][j] * psum_max[j + 1]; 576 for (int j = 0; j < m; j++) 577 if ((m - j) % 2 == 1) 578 ans += a[i][j] * psum_min[j]; 579 } 580 if (i % 2 == 0) { 581 for (int j = 0; j < m; j++) 582 tmp[j] = j % 2 == 0 ? a[i][j] : 0; 583 for (int j = 1; j < m; j++) 584 tmp[j] += tmp[j - 1]; 585 for (int j = 0; j < m; j++) 586 psum_min[j] += tmp[j]; 587 for (int j = 0; j < m; j++) 588 tmp[j] = (m - j) % 2 == 1 ? a[i][j] : 0; 589 for (int j = m - 2; j >= 0; j--) 590 tmp[j] += tmp[j + 1]; 591 for (int j = 0; j < m; j++) 592 psum_max[j] += tmp[j]; 593 } 594 } 595 ans *= 2; 596 for (int i = 0; i < n; i++) 597 for (int j = 0; j < m; j++) 598 if (i % 2 == 0 && (n - i) % 2 == 1 && j % 2 == 0 && (m - j) % 2 == 1) 599 ans += a[i][j] * a[i][j]; 600 ans *= sgn; 601 cout << ans << '\n'; 602 } 603 604 signed main() { 605 cin.tie(nullptr)->sync_with_stdio(0); 606 int tt = 1; 607 cin >> tt; 608 for (int test_id = 1; test_id <= tt; test_id++) { 609 solve(); 610 } 611 } 612 ```