102695: [AtCoder]ABC269 F - Numbered Checker
Description
Score : $500$ points
Problem Statement
We have a grid with $N$ rows and $M$ columns. The square $(i,j)$ at the $i$-th row from the top and $j$-th column from the left has an integer $(i-1) \times M + j$ written on it.
Let us perform the following operation on this grid.
- For every square $(i,j)$ such that $i+j$ is odd, replace the integer on that square with $0$.
Answer $Q$ questions on the grid after the operation.
The $i$-th question is as follows:
- Find the sum of the integers written on all squares $(p,q)$ that satisfy all of the following conditions, modulo $998244353$.
- $A_i \le p \le B_i$.
- $C_i \le q \le D_i$.
Constraints
- All values in the input are integers.
- $1 \le N,M \le 10^9$
- $1 \le Q \le 2 \times 10^5$
- $1 \le A_i \le B_i \le N$
- $1 \le C_i \le D_i \le M$
Input
The input is given from Standard Input in the following format:
$N$ $M$ $Q$ $A_1$ $B_1$ $C_1$ $D_1$ $A_2$ $B_2$ $C_2$ $D_2$ $\vdots$ $A_Q$ $B_Q$ $C_Q$ $D_Q$
Output
Print $Q$ lines.
The $i$-th line should contain the answer to the $i$-th question as an integer.
Sample Input 1
5 4 6 1 3 2 4 1 5 1 1 5 5 1 4 4 4 2 2 5 5 4 4 1 5 1 4
Sample Output 1
28 27 36 14 0 104
The grid in this input is shown below.
This input contains six questions.
- The answer to the first question is $0+3+0+6+0+8+0+11+0=28$.
- The answer to the second question is $1+0+9+0+17=27$.
- The answer to the third question is $17+0+19+0=36$.
- The answer to the fourth question is $14$.
- The answer to the fifth question is $0$.
- The answer to the sixth question is $104$.
Sample Input 2
1000000000 1000000000 3 1000000000 1000000000 1000000000 1000000000 165997482 306594988 719483261 992306147 1 1000000000 1 1000000000
Sample Output 2
716070898 240994972 536839100
For the first question, note that although the integer written on the square $(10^9,10^9)$ is $10^{18}$, you are to find it modulo $998244353$.
Sample Input 3
999999999 999999999 3 999999999 999999999 999999999 999999999 216499784 840031647 84657913 415448790 1 999999999 1 999999999
Sample Output 3
712559605 648737448 540261130
Input
题意翻译
给定一个 $N\times M$ 的矩阵 $A$,有 $$A_{i,j}= \begin{cases} (i-1)M+j&((i+j)\bmod 2=0) \\ 0&((i+j)\bmod 2=1) \end{cases} $$ 给定 $Q$ 次询问,每次询问给出 $X_1,X_2,Y_1,Y_2$。求以 $(X_1,Y_1)$ $(X_2,Y_2)$ 为左上角和右下角的矩形的元素之和。对 $998244353$ 取模。Output
分数:$500$分
问题描述
我们有一个包含$N$行和$M$列的网格。左上角的第$(i-1)$行和第$j$列的正方形上写着$(i-1) \times M + j$。
- 对于每个满足$i+j$为奇数的正方形$(i,j)$,将其上的整数替换为$0$。
回答操作后网格上的$Q$个问题。
- 找到满足以下所有条件的正方形$(p,q)$上写的整数的和(对$998244353$取模)。
- $A_i \le p \le B_i$。
- $C_i \le q \le D_i$。
限制条件
- 输入中的所有值都是整数。
- $1 \le N,M \le 10^9$
- $1 \le Q \le 2 \times 10^5$
- $1 \le A_i \le B_i \le N$
- $1 \le C_i \le D_i \le M$
输入
输入通过标准输入以以下格式给出:
$N$ $M$ $Q$ $A_1$ $B_1$ $C_1$ $D_1$ $A_2$ $B_2$ $C_2$ $D_2$ $\vdots$ $A_Q$ $B_Q$ $C_Q$ $D_Q$
输出
打印$Q$行。
第$i$行应包含第$i$个问题的答案(为整数)。
样例输入1
5 4 6 1 3 2 4 1 5 1 1 5 5 1 4 4 4 2 2 5 5 4 4 1 5 1 4
样例输出1
28 27 36 14 0 104
这个输入中的网格如下所示。
这个输入包含六个问题。
- 第一个问题的答案是$0+3+0+6+0+8+0+11+0=28$。
- 第二个问题的答案是$1+0+9+0+17=27$。
- 第三个问题的答案是$17+0+19+0=36$。
- 第四个问题的答案是$14$。
- 第五个问题的答案是$0$。
- 第六个问题的答案是$104$。
样例输入2
1000000000 1000000000 3 1000000000 1000000000 1000000000 1000000000 165997482 306594988 719483261 992306147 1 1000000000 1 1000000000
样例输出2
716070898 240994972 536839100
对于第一个问题,需要注意的是,虽然写在正方形$(10^9,10^9)$上的整数是$10^{18}$,但你需要对$998244353$取模。
样例输入3
999999999 999999999 3 999999999 999999999 999999999 999999999 216499784 840031647 84657913 415448790 1 999999999 1 999999999
样例输出3
712559605 648737448 540261130