codeforces-scrape

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

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 ![Illustration](/predownloaded/d8/f3/d8f32ae03373053436ae8e55b8650795dc20e724.png)
    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 ```