AT_abc269_f 总结
题目：AT_abc269_f
链接：洛谷，AT，vjudge
题意
-
有一个 \(n\) 行 \(m\) 列的矩阵，第 \(i\) 行第 \(j\) 列上的数为 \((i - 1)n + j\)，但是如果 \(i + j\) 为奇数，上面的数为 \(0\)。给定 \(q\) 组询问，每组询问求一个子矩阵的和，答案对 \(998244353\) 取模。
-
\(1 \le n, m \le 10^9, 1 \le q \le 2 \times 10^5，子矩阵大小 \le n \times m\)。
思路
-
可以发现子矩阵第一列的这些非 \(0\) 的数形成一个等差数列，第二列也是等差数列。然后又可以发现第 \(1\) 列的和，第 \(3\) 列的和，第 \(5\) 列的和 \(\cdots\) 也是等差数列，并且第 \(2\) 列的和，第 \(4\) 列的和 \(\cdots\) 也是等差数列。所以我们只用求出第 \(1,2\) 列的和，再做一遍求和即可。
-
当然我们还要注意一下等差数列 \(/ 2\) 的细节，可以发现 (首项 + 末项) 以及项数必有一个 \(2\) 的倍数，判断一下哪一个为偶数即可，不需要再用乘法逆元算一遍。
-
时间复杂度： \(q\) 组询问，每组 \(O(1)\) 回答。总时间复杂度：\(O(q)\)。