CF2275H.A Problem to Warm Up the Eyebrows

提高+/省选-

通过率:0%

时间限制:1.50s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

K1o0n came up with this amusing game for his friend Noobish_Monk. They take a rectangular table of integers, and for every solid rectangular piece of this table Noobish_Monk either gets something or, on the contrary, loses something — depending on the shape of the piece. Figuring out how much he gets in total became Noobish_Monk's task, but once again he misread the statement 998244353 times, which caused him to get stuck on an insignificant piece.

We invite you to try your hand at this game as well!

You are given a table of integers AA with nn rows and mm columns. A submatrix is any solid rectangular piece of the table; it is determined by the indices of its first and last rows and the indices of its first and last columns. Suppose a submatrix occupies aa consecutive rows and bb consecutive columns, and the sum of all numbers in it is SS. If a+ba+b is even, then Noobish_Monk gets S2S^2, and if it is odd, he loses S2S^2. This quantity is called the price of the submatrix:

(−1)a+b S2.(-1)^{a+b}\,S^2.

The price of the table is the sum of the prices of all its submatrices, including the whole table. Help him: find the price of table AA. It can be negative and can also be very large in magnitude, so output it modulo 109+7\mathbf{10^9+7}.

K1o0n 为他的朋友 Noobish_Monk 设计了这个有趣的益智游戏。他们取一个由整数组成的矩形表格,对其中每一个实心矩形子块(即连续的行与列构成的子矩阵),Noobish_Monk 要么获得一些东西,要么相反地损失一些东西——这取决于该子块的形状。计算他最终总共获得或损失多少,便成了 Noobish_Monk 的任务;但不幸的是,他再次把题目读错了 998244353 次,结果卡在了一个微不足道的小地方。

我们也诚邀你来尝试这一游戏!

给定一个含 nn 行 mm 列的整数表格 AA。所谓子矩阵,是指表格中任意一个实心矩形区域;它由其首行、末行的行号以及首列、末列的列号唯一确定。设某子矩阵占据 aa 个连续的行和 bb 个连续的列,且其中所有数字之和为 SS。若 a+ba+b 为偶数,则 Noobish_Monk 获得 S2S^2;若 a+ba+b 为奇数,则他损失 S2S^2。该值称为该子矩阵的价格:

(−1)a+b S2. (-1)^{a+b}\,S^2.

整个表格的价格,定义为该表格所有子矩阵(包括表格自身)的价格之和。请帮助他:求出表格 AA 的价格。该值可能为负,也可能绝对值极大,因此请输出其对 109+7\mathbf{10^9+7} 取模的结果。

输入格式

The first line contains an integer tt (1≤t≤1041 \le t \le 10^4) — the number of testcases.

The first line of each testcase contains two integers nn and mm (1≤n,m1 \le n, m, 1≤n⋅m≤1061 \le n \cdot m \le 10^6) — the dimensions of the matrix.

The next nn lines contain mm integers each: the jj-th number in the ii-th line equals Ai,jA_{i,j} (−109≤Ai,j≤109-10^9 \le A_{i,j} \le 10^9).

It is guaranteed that the sum of n⋅mn \cdot m over all testcases does not exceed 10610^6.

第一行包含一个整数 tt(1≤t≤1041 \le t \le 10^4)—— 测试用例的数量。

每个测试用例的第一行包含两个整数 nn 和 mm(1≤n,m1 \le n, m,且 1≤n⋅m≤1061 \le n \cdot m \le 10^6)—— 矩阵的维度。

接下来的 nn 行,每行包含 mm 个整数:第 ii 行中的第 jj 个数等于 Ai,jA_{i,j}(−109≤Ai,j≤109-10^9 \le A_{i,j} \le 10^9)。

保证所有测试用例中 n⋅mn \cdot m 的总和不超过 10610^6。

输出格式

For each testcase, output a single integer in a separate line from the range [0,  109+6][0,\;10^9+6] — the remainder of the table price divided by 109+710^9+7.

对于每个测试用例,在单独一行中输出一个范围在 [0,  109+6][0,\;10^9+6] 内的整数——即表格价格对 109+710^9+7 取模所得的余数。

输入输出样例

  • 输入#1

    4
    3 3
    1 5 2
    7 9 8
    3 6 4
    2 4
    1 -1 -2 2
    -2 2 1 -1
    3 2
    4 5
    8 2
    0 0
    4 4
    1 1 1 1
    -1 -1 -1 -1
    1 1 1 1
    -1 -1 -1 -1

    输出#1

    100
    6
    999999967
    999999971

说明/提示

null

输入解题思路,AI测评打分。不知道怎么写?

首页