[ABC269F] Numbered Checker Solution

更好的阅读体验戳此进入

题面

存在 $n\times m$$n \times m$ 的网格图，在里面按照从左至右，从上至下的顺序填写 $[1,n\times m]$$[1, n \times m]$ 所有数，然后使所有行数与列数之和为奇数的格子中的数推平为 $0$$0$。$q$$q$ 次询问求子矩形权值和。

Solution

尝试简单推一下式子，显然对于奇数行，为 $1+km,3+km,5+km,\cdots$$1 + km, 3 + km, 5 + km, \cdots$，偶数行同理。对于多行相加，奇数行则 $k=0,2,4,\cdots$$k = 0, 2, 4, \cdots$，偶数行同理。也就是说我们讨论奇偶之后，对一行里做一下等差数列求和然后乘上奇数行行数，对 $k$$k$ 做一遍等差数列求和然后乘上奇数列列数和 $m$$m$ 即可。

同时注意对于偶数的求和需要全部转为偶数，反之全部转为奇数。

同时也可以用简单的容斥思想，每次计算左上角为 $1$$1$ 的四个矩形的值并处理，但实现难度与此方法接近。

同时整个过程中仅需 long long 即可，等差数列求和的除以 $2$$2$ 不需要用逆元，适当取模后也不需要用 __int128_t。

Code

xxxxxxxxxx
84
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define MOD (998244353ll)
23

24
template < typename T = int >
25
inline T read(void);
26

27
int N, M;
28

29
ll QueryOdd(ll l, ll r){
30
    if(!(l & 1))++l;
31
    if(!(r & 1))--r;
32
    if(l > r)return 0;
33
    return (((l + r) * (((r - l) >> 1) + 1)) >> 1) % MOD;
34
}
35
ll QueryEven(ll l, ll r){
36
    if(l & 1)++l;
37
    if(r & 1)--r;
38
    if(l > r)return 0;
39
    return (((l + r) * (((r - l) >> 1) + 1)) >> 1) % MOD;
40
}
41
ll CntOdd(ll l, ll r){
42
    if(!(l & 1))++l;
43
    if(!(r & 1))--r;
44
    if(l > r)return 0;
45
    return (((r - l) >> 1) + 1) % MOD;
46
}
47
ll CntEven(ll l, ll r){
48
    if(l & 1)++l;
49
    if(r & 1)--r;
50
    if(l > r)return 0;
51
    return (((r - l) >> 1) + 1) % MOD;
52
}
53

54
int main(){
55
    N = read(), M = read();
56
    int Q = read();
57
    while(Q--){
58
        ll ans(0);
59
        int a = read(), b = read(), c = read(), d = read();
60
        (ans += QueryOdd(c, d) * CntOdd(a, b) % MOD) %= MOD;
61
        (ans += ((QueryOdd(a, b) - CntOdd(a, b) + MOD) % MOD) * CntOdd(c, d) % MOD * M % MOD) %= MOD;
62
        (ans += QueryEven(c, d) * CntEven(a, b) % MOD) %= MOD;
63
        (ans += ((QueryEven(a, b) - CntEven(a, b) + MOD) % MOD) * CntEven(c, d) % MOD * M % MOD) %= MOD;
64
        printf("%lld\n", ans);
65
    }
66
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
67
    return 0;
68
}
69

70
template < typename T >
71
inline T read(void){
72
    T ret(0);
73
    int flag(1);
74
    char c = getchar();
75
    while(c != '-' && !isdigit(c))c = getchar();
76
    if(c == '-')flag = -1, c = getchar();
77
    while(isdigit(c)){
78
        ret *= 10;
79
        ret += int(c - '0');
80
        c = getchar();
81
    }
82
    ret *= flag;
83
    return ret;
84
}

UPD

update-2023_01_25 初稿