# #548. 「LibreOJ β Round #7」某少女附中的体育课

#### 题目描述

$A$ 满足的性质如下：

• 交换律，即 $\forall i,j \in S,i\circ j=j\circ i$
• 结合律，即 $\forall i,j,k \in S,(i\circ j)\circ k=i\circ (j \circ k)$
• 循环律，即 $\forall i\in S,\exists j>1$ 使得 $i^j=i$

• 首先体育老师会使用他手机上的计算器生成一个长为 $n$ 的每个元素属于 $S$ 的伪随机数列 $\{s_i\}$
• 对于第 $i$ 组学生，如果当前球在组内编号为 $a_i$ 的学生手上，那么他会把球传给组内 $a_i\circ s_i$ 号学生（当 $a_i = a_i\circ s_i$ 时不传球）。

2 2 1
0 1
1 0
3 2 4 1

30
20
28
22

#### 样例解释 1

$A=\begin{bmatrix}0 & 1\\1 & 0\end{bmatrix}$，故此组数据中由状态和传球方法得出的传球结果即为二者二进制按位异或的结果。

$0$ 对应的数列是 $\{0,0\}$，对应的状态是：两组的球都在组内 $0$ 号学生手中；
$1$ 对应的数列是 $\{1,0\}$，对应的状态是：第 $0$ 组的球都在组内 $1$ 号学生手中，第 $1$ 组的球在组内 $0$ 号学生手中；
$2$ 对应的数列是 $\{0,1\}$，对应的状态是：第 $0$ 组的球都在组内 $0$ 号学生手中，第 $1$ 组的球在组内 $1$ 号学生手中；
$3$ 对应的数列是 $\{1,1\}$，对应的状态是：两组的球都在组内 $1$ 号学生手中。

• 已知，当前状态每组持球学生的编号数列 $\{a_i\}$$\{0,0\}$，生成的传球数列 $\{s_i\}$ 也是 $\{0,0\}$；求传球后的每组持球学生编号数列 $\{b_i\}$
• 传球方法表 $A=\begin{bmatrix}0 & 1\\1 & 0\end{bmatrix}$
• 则对于任意 $i$$b_i=A_{a_i,s_i}$，具体地，$b_0=A_{0,0}=0,b_1=A_{0,0}=0$

# $0,0.3$ $1,0.2$ $2,0.4$ $3,0.1$
$0,0.3$ $0,0.09$ $1,0.06$ $2,0.12$ $3,0.03$
$1,0.2$ $1,0.06$ $0,0.04$ $3,0.08$ $2,0.02$
$2,0.4$ $2,0.12$ $3,0.08$ $0,0.16$ $1,0.04$
$3,0.1$ $3,0.03$ $2,0.02$ $1,0.04$ $0,0.01$

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

118
134
118
134
130
114
102
150

#### 样例输入 3

3 3 1000000000000000000
0 1 0
1 0 1
0 1 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

213274696
208936145
25902863
95562855
217079278
63925718
106613073
183344989
8375316
32956358
199136079
5516750
230547873
170961061
216818160
114420143
15437393
149522201
77102517
62329524
215121795
51813646
230286755
91113233
13573868
80597355
39406187

#### 数据范围与提示

Subtask # 分值 $m$ $n$ $k$ 特殊限制
$1$ $7$ $=2$ $\le 10$ $\le 10$ -
$2$ $8$ $=2$ - $\le 10$ $A=\begin{bmatrix}1 & 0\\0 & 1\end{bmatrix}$
$3$ $10$ $=2$ - - -
$4$ $9$ $=3$ - $\le 10$ $A=\begin{bmatrix}0 & 1 & 2\\1 & 1 & 2\\2 & 2 & 2\end{bmatrix}$
$5$ $9$ $=3$ - $\le 10$ $A=\begin{bmatrix}0 & 1 & 0\\1 & 0 & 1\\0 & 1 & 2\end{bmatrix}$
$6$ $10$ $\le 8$ - - $(S,\circ)$循环群
$7$ $11$ - - - $(S,\circ)$
$8$ $11$ - - - $\forall i,i\circ i=i$
$9$ $5$ $\le 8$ - - -
$10$ $7$ $\le 15$ - - -
$11$ $13$ - - - -