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

    ID: 5094 传统题 1500ms 512MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>难度分类NOI/NOI+/CTS多项式与生成函数卷积转化线性代数与代数Gauss–Jordan 消元矩阵求逆矩阵乘法数论原根快速幂交换矩阵族同时对角化CF3300

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

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

题目描述

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

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

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

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

然后体育老师会发给学生一个 m×mm\times m 的表 AA 表示传球规则,其中的数都属于 SS,且 AA 有一些特殊性质。为了方便描述 AA,我们定义 SS 上的二元运算 ∘:i∘j=Ai,j\circ:i\circ j=A_{i,j}。另外定义 $i^j=\underbrace{i\circ i\circ\cdots\circ i}_{j\text{ 次}}$。
AA 满足的性质如下:

  • 交换律,即 ∀i,j∈S,i∘j=j∘i\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)$
  • 循环律,即 ∀i∈S,∃j>1\forall i\in S,\exists j>1 使得 ij=ii^j=i

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

  • 首先体育老师会使用他手机上的计算器生成一个长为 nn 的每个元素属于 SS 的伪随机数列 {si}\{s_i\}。
  • 对于第 ii 组学生,如果当前球在组内编号为 aia_i 的学生手上,那么他会把球传给组内 ai∘sia_i\circ s_i 号学生(当 ai=ai∘sia_i = a_i\circ s_i 时不传球)。

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

神犇记得,体育老师手机里的随机数生成器生成的每组随机数的 mnm^n 种结果并不是等可能的(各次生成相互独立,且同一节课内每次使用时生成各结果的概率不变)。我们用一个长 mnm^n 的序列 {Pi}\{P_i\} 表示每种结果的概率,设 X=∑i=0mn−1PiX=\sum_{i=0}^{m^n-1} P_i,则生成 ii 对应的数列的概率为 PiX\frac{P_i}{X}。

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

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

输入格式

第一行三个整数 n,m,kn,m,k。
接下来 mm 行每行 mm 个整数,表示 AA。其中第 i+1i+1 行第 j+1j+1 个整数表示 Ai,jA_{i,j}。
接下来一行 mnm^n 个整数,其中第 i+1i+1 个整数表示 PiP_i。

输出格式

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

样例输入 1

2 2 1
0 1
1 0
3 2 4 1

样例输出 1

30
20
28
22

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

样例输入 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 # 分值 mm nn kk 特殊限制
11 77 =2=2 ≤10\le 10 ≤10\le 10 -
22 88 - A=[1001]A=\begin{bmatrix}1 & 0\\0 & 1\end{bmatrix}
33 1010 -
44 99 =3=3 ≤10\le 10 $A=\begin{bmatrix}0 & 1 & 2\\1 & 1 & 2\\2 & 2 & 2\end{bmatrix}$
55 $A=\begin{bmatrix}0 & 1 & 0\\1 & 0 & 1\\0 & 1 & 2\end{bmatrix}$
66 1010 ≤8\le 8 - (S,∘)(S,\circ) 是循环群
77 1111 - (S,∘)(S,\circ) 是群
88 ∀i,i∘i=i\forall i,i\circ i=i
99 55 ≤8\le 8 -
1010 77 ≤15\le 15
1111 1313 -

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