首页 题库 比赛 评测 排名 讨论 帮助 返回比赛
登录 注册

F. 某少女附中的体育课

内存限制：512 MiB 时间限制：1000 ms 标准输入输出
题目类型：传统 评测方式：文本比较
转到题库 提交记录 返回比赛

题目描述

神犇是某少女附中的高三生。在机房的窗边，神犇和 LCR 一起俯瞰着楼下玩篮球的学生。注视着他们的背影，神犇想起了高一时的一件往事 ……

当时，他的体育老师每节体育课都让同学们玩传球游戏，玩法是这样的：

体育老师有 n 个篮球。一开始，体育老师会把所有学生平均分为 n 组，每组 m 人。组的编号为 0,1,\cdots,n-1 ，每组中学生分别编号为 0,1,\cdots,m-1 。为了方便描述，我们定义 S 为 [0,m) 中的整数集合。

接着，体育老师会使用他手机上的计算器生成一个长为 n 的每个元素属于 S 的伪随机数列 \{s_i\} 。接着对于第 i 组他把球发给该组的 s_i 号学生。

然后体育老师会发给学生一个 m\times m 的表 A 表示传球规则，其中的数都属于 S ，且 A 有一些特殊性质。为了方便描述 A ，我们定义 S 上的二元运算 \circ:i\circ j=A_{i,j} 。另外定义 i^j = \begin{gather}\underbrace{i\circ i\circ \cdots \circ i}\\ j \text{ times} \end{gather} 。
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

然后体育老师会让学生进行 k 轮传球。每一轮传球的方法相同，如下：

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

为了方便，我们用一个 n 位 m 进制数来表示一个长为 n ，下标从 0 开始，每个位置元素属于 S 的数列。具体地，我们用 \sum_{i=0}^n s_i m^i 来表示 \{s_i\} 。显然， [0,m^n) 中的整数与所有可能的该种数列一一对应。

神犇记得，体育老师手机里的随机数生成器生成的每组随机数的 m^n 种结果并不是等可能的（但同一节课内每次使用时生成各结果的概率不变）。我们用一个长 m^n 的序列 \{P_i\} 表示每种结果的概率，设 X=\sum_{i=0}^{m^n-1} P_i ，则生成 i 对应的数列的概率为 \frac{P_i}{X} 。

神犇把这些往事告诉了 LCR。LCR 想知道 k 轮传球后球的持有者的每种情况的概率。于是她希望你 —— 某少女附中著名 OIer —— 来解决这个问题。

设最终编号为 i 的组中篮球在 r_i 号学生手中，那么用 \{r_i\} 对应的 m 进制数来表示这个状态。为了简化计算及避免精度误差，我们只需要求出对于 [0,m^n) 中的每个数 i ， i 所对应的状态的概率与 X^{k+1} 的乘积模 232792561 的值。

输入格式

第一行三个整数 n,m,k 。
接下来 m 行每行 m 个整数，表示 A 。其中第 i+1 行第 j+1 个整数表示 A_{i,j} 。
接下来一行 m^n 个整数，其中第 i+1 个整数表示 P_i 。

输出格式

输出 m^n 行，每行一个整数，其中第 i+1 行表示 k 次传球过后处于 i 所对应的状态的概率与 X^{k+1} 的乘积模 232792561 的值。

样例

样例输入 1

2 2 1
0 1
1 0
3 2 4 1

样例输出 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 号学生手中。

开始时， 0 到 3 对应的状态的概率依次为： 0.3, 0.2, 0.4, 0.1 。

第一轮传球时，生成数列 \{0,0\} 的概率为 0.3 ，若生成了 \{0,0\} ，且当前状态为 0 （即两组的球都在 0 号学生手中），那么，计算传球情况的过程如下：

  • 已知，当前状态每组持球学生的编号数列 \{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 ，对应的数为 0 。

我们再看一组：第一轮传球时，生成数列 \{1,0\} 的概率为 0.2 ，若生成了 \{1,0\} ，且当前状态为 3 （即两组的球都在 1 号学生手中），那么：
当前状态每组持球学生的编号数列 \{a_i\} 为 \{1,1\} ，生成的传球数列 \{s_i\} 是 \{1,0\} ，可以计算出传球后的每组持球学生编号数列 \{b_i\} 为： b_0=A_{1,1}=0,b_1=A_{1,0}=1 。
那么，传球后每组持球学生编号依次为 0,1 ，对应的数为 2 。

以下是所有可能的情况：（行表示传球前状态，列表示传球数列，格内为传球结果，以「状态，概率」格式表示）

# 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

最终， 0 到 3 对应的状态的概率依次为： 0.09+0.04+0.16+0.01=0.3,0.06+0.06+0.04+0.04=0.2,0.12+0.02+0.12+0.02=0.28,0.03+0.08+0.08+0.03=0.22 ，又 X=3+2+4+1=10 ，故分别乘 X^{k+1}=10^2=100 即得输出。

样例输入 2

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

样例输出 2

118
134
118
134
130
114
102
150

样例解释 2

最开始 0 到 7 对应的状态的概率依次为： 0.1, 0.2, 0.1, 0.2, 0.1, 0, 0, 0.3 ；
传球一轮后的概率依次为： 0.2, 0.08, 0.1, 0.14, 0.14, 0.1, 0.14, 0.1 ；
传球两轮后的概率依次为： 0.118, 0.134, 0.118, 0.134, 0.13, 0.114, 0.102, 0.15 。

样例输入 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

样例输出 3

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

数据范围与提示

对于所有数据， 1\le n\le 18,2\le m\le 22,1\le k\le 10^{18},m^n\le 5\times 10^5 ,0\le P_i < 232792561 。

详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：

Subtask # 分值 m n k 特殊限制
1 7 =2 \le 10 \le 10 -
2 8 - A=\begin{bmatrix}1 & 0\\0 & 1\end{bmatrix}
3 10 -
4 9 =3 \le 10 A=\begin{bmatrix}0 & 1 & 2\\1 & 1 & 2\\2 & 2 & 2\end{bmatrix}
5 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 \forall i,i\circ i=i
9 5 \le 8 -
10 7 \le 15
11 13 -

注：特殊限制中的矩阵，从上到下第 i+1 行从左到右第 j+1 列表示 A_{i,j} 。

LibreOJ Powered by SYZOJ.