[清华集训2016] 石家庄的工人阶级队伍比较坚强
题目背景
B 君和 G 君在过街天桥上。
B 君:「又到冬天啦,算起来到大学已经三年多了」
G 君:「是呀」
B 君:「街上的情侣又多起来了,想想三年之前,我也是这样……」
G 君:「??」
B 君:「……在天桥上看情侣的!」
G 君:「唔。」
B 君:「不过这次有你陪我了呢~」
G 君:「……」
B 君:「诶诶,我有个问题想问你~」
G 君:「问吧」
B 君:「假设 $n=3^m$ 个人一起玩 cei ding ke」
G 君:「啊咧?cei ding ke 是什么?」
B 君:「就是石头剪刀布~,我们也叫钉钢锤」
G 君:「你就问这个?」
B 君:「你等会,我还没说完呢」
题目描述
$n=3^m$ 个人在玩石头剪刀布, 一共有 $t$ 轮游戏,每轮有 $m$ 次石头剪刀布。
在同一轮的 $m$ 次游戏中,每个人的决策必须是提前确定的,也就是说不能采用随机策略,也不能根据前若干局的结果决定下一局的决策; 这样,显然一共有 $n=3^m$ 种决策。
这 $n=3^m$ 个人会采取两两不同的决策。 为了方便表达,对于第 $x$($0≤x<n$)个人,将 $x$ 转换成三进制得到一个 $m$ 位的数。 其中 $0$ 表示剪刀,$1$ 表示石头,$2$ 表示布。就得到了第 $x$ 个人采取的策略。
由于编号是固定的,因此每个人在不同轮的 $m$ 次游戏中都会采取同一套决策。
第 $x$ 个人在最初时有一个分数 $f_{0,x}$。
在第 $i$ 轮中,他将和另一个人 $y$ 进行 $m$ 次的石头剪刀布的比赛。
我们用 $W(x,y)$ 表示 $x$ 在和 $y$ 的 $m$ 次比赛中赢的次数; 用 $L(x,y)$ 表示 $x$ 在和 $y$ 的 $m$ 次比赛中输的次数。
在第 $i$ 轮结束之后,第 $x$ 个人分数是:
$$f_{i,x}=∑_{0≤y<n}f_{i−1,y}b_{u,v}$$
其中 $u=W(x,y)=L(y,x),v=L(x,y)=W(y,x)$,平局不计入次数;$b_{u,v}$ 则是一个给定的评分数组。
注意即使 $y$ 和 $x$ 一样(自己转移到自己)也会乘上一个系数 $b_{0,0}$(即自己跟自己打全为平局)。
显然随着轮数越来越多,分数也会越来越大, 这个计分系统和我们平时用的计算机一样,也会溢出。 当要储存的分数 $f$ 大于等于 $p$ 的时候,就会变成 $f\bmod p$。
B 君想知道 $t$ 轮之后所有人的分数,也就是 $f_{t,0},f_{t,1},…,f_{t,n−1}$。
G 君:「诶,我发现这个数 $p$ 有特殊的性质诶!不存在两个正整数,使得他们倒数的和等于 $3/p$!」
B 君:「G 君好棒!不过这个题怎么做呢?」
输入输出格式
输入格式
第一行三个整数,表示 $m,t,p$。
第二行有 $n=3^m$ 个整数,表示 $f_{0,0},f_{0,1},…,f_{0,n−1}$。保证 $0≤f_{0,i}<p$。
接下来的部分是一个数组 $b$,第 $1$ 行 $m+1$ 个数,第 $2$ 行 $m$ 个数……第 $m+1$ 行 $1$ 个数。
其中第 $i$ 行的第 $j$ 个数为 $b_{i−1,j−1}$($i,j≥1,i+j−2≤m$),保证 $0≤b_{i,j}<p$。
不存在两个正整数,使得他们倒数的和等于 $3/p$。 即不存在正整数 $x,y>0$,使得 $1/x+1/y=3/p$。
输出格式
输出 $n=3^m$ 行,每行一个整数,表示每个人最终的得分。
其中第 $i$ 行表示第 $i$ 个人的得分 $f_{t,i}$。
输入输出样例
输入样例 #1
1 1 10009
10 100 1000
2 3
4
输出样例 #1
4320
3240
2430
输入样例 #2
2 3 103
7 8 9 10 11 12 13 14 15
1 2 3
4 5
6
输出样例 #2
96
8
73
38
53
15
27
42
4
说明
对于所有数据,$0≤m≤12$,$0≤t≤10^9$,$1≤p≤10^9$。