P8628 - Cyber Painter

内存限制：128 MB 时间限制：6 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：2 通过：0

In the world of Cyberpunk, all paintings are done by using lasers. As a cyber painter, painting with lasers is your daily job.

You have a laser painting board with rows and $m$ columns of laser emitters. The distance between rows is , and so is the distance between columns. Each laser emitter can emit a laser with a length of in four directions. Specifically, you can set an integer between and as the state value for each laser emitter, which can be denoted by a four-bit binary number $(X_{1} X_{2} X_{3} X_{4})_{2}$ (For example, $(1011)_{2}$ ). The meaning of the state value is as follows:

$X_{1} = 1$ : The laser emitter emits a laser of length $0.5$ in the upward direction.
$X_{2} = 1$ : The laser emitter emits a laser of length $0.5$ in the right direction.
$X_{3} = 1$ : The laser emitter emits a laser of length $0.5$ in the downward direction.
$X_{4} = 1$ : The laser emitter emits a laser of length $0.5$ in the left direction.

Given

n \times m

integers between

and

, you need to assign an integer to each laser emitter as its state value. You are curious about the expectation of the number of squares that can be formed by the laser if the

n \times m

integers are assigned uniformly at random, where the squares can be of arbitrary edge length.

The first line contains an integer $1 \leq T \leq 1 0^{4}$ ), indicating the number of test cases.

The first line of each test case contains two integers and ( $1 \leq n \times m \leq 1 0^{5}$ ), indicating the number of rows and columns of the laser emitters.

The second line of each test case contains integers $a_{0}, a_{1}, \dots, a_{15}$ ( $0 \leq a_{i} \leq n \times m$ , $\sum_{i = 0 15} a_{i} = n \times m$ ), where $a_i$ indicates the number of integer $i$ .

It guaranteed that the sum of $n \times m$ over all test cases won't exceed $1 0^{6}$ .

For each test case, output the expectation of the number of squares that can be formed by the laser in a single line. You should output the answer modulo

1 0^{9} + 7

. Formally, let

M = 1 0^{9} + 7

. It can be shown that the answer can be expressed as an irreducible fraction

\frac{p}{q}

, where

and

are integers and

q！ \equiv 0 (mod M)

. Output the integer equal to

p \times q^{- 1} mod M

. In other words, output such an integer

x

that

0 \leq x < M

and

x \cdot q \equiv p (mod M)

3
2 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4
2 2
0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0
3 3
0 0 0 0 0 0 1 0 0 1 0 1 1 1 2 2

1
41666667
41699736

2022 杭电多校第七场

8628: Cyber Painter

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

分类标签