[ABC269F] Numbered Checker
题意
有一个 \(n \times m\) 的矩阵,有:
\(a_{ij} = \begin{cases}(i - 1)m + j&i + j\equiv0\pmod{2}\\0&i + j\equiv1\pmod{2}\end{cases}\)
给定 \(a, b, c, d\) 问从 \((a, c)\) 到 \((b, d)\) 的数字和是多少。
思路
数学,我们可以发现,每一行可以表示为:\(x, 0, x + 2, 0, x + 4 \dots\) 或是 \(0, y, 0, y + 2, 0, y + 4 \dots\)所以我们发现每一行的和是可以用等差数列来求的,再看列
x, 0, x + 2, 0, x + 4
0, y, 0, y + 2, 0
x + 2 * m, 0, x + 2 + 2 * m, 0, x + 4 + 2 * m
0, y + 2 * m, 0, y + 2 + 2 * m, 0
发现每一行的和按列来看也是等差数列,所以分类讨论然后用等差数列求和即可。
代码
#include <iostream>
using namespace std;
using ll = long long;
const int mod = 998244353;
ll n, m, q, a, b, c, d, x, y, fh, sh, oh, eh;
ll F(__int128_t a, __int128_t d, __int128_t n) {
return ((((a % mod) * n % mod)) % mod + (n * (n - 1) / 2 * d) % mod) % mod;
}
ll num(__int128_t x, __int128_t y) {
return ((((x - 1) % mod) * (m % mod)) % mod + y) % mod;
}
int main() {
for (cin >> n >> m >> q; q; q--) {
cin >> a >> b >> c >> d;
if ((a + c) % 2) {
x = (d - c + 1) / 2, fh = F(num(a, c + 1), 2, x);
y = (d - c) / 2 + 1, sh = F(num(a + 1, c), 2, y);
} else {
x = (d - c) / 2 + 1, fh = F(num(a, c), 2, x);
y = (d - c + 1) / 2, sh = F(num(a + 1, c + 1), 2, y);
}
cout << (F(fh, x * 2 * m % mod, (b - a) / 2 + 1) + F(sh, y * 2 * m % mod, (b - a + 1) / 2)) % mod << endl;
}
return 0;
}
标签:Numbered,__,ABC269F,Checker,num,int128,ll,mod
From: https://www.cnblogs.com/ybtarr/p/17410541.html