#2079. 石家庄的工人阶级队伍比较坚强
石家庄的工人阶级队伍比较坚强
石家庄的工人阶级队伍比较坚强
题目描述
标题: 石家庄的工人阶级队伍比较坚强 - Problem - QOJ.ac
#4555. 石家庄的工人阶级队伍比较坚强
The problem was used in the following contests:
B君和G君在过街天桥上。
B君:「又到冬天啦,算起来到大学已经三年多了」
G君:「是呀」
B君:「街上的情侣又多起来了,想想三年之前,我也是这样……」
G君:「??」
B君:「……在天桥上看情侣的!」
G君:「唔。」
B君:「不过这次有你陪我了呢~」
G君:「……」
B君:「诶诶,我有个问题想问你~」
G君:「问吧」
B君:「假设 n=3m 个人一起玩cei ding ke」
G君:「啊咧?cei ding ke 是什么?」
B君:「就是石头剪刀布~,我们也叫钉钢锤」
G君:「你就问这个?」
B君:「你等会,我还没说完呢」
任务描述
n=3m 个人在玩石头剪刀布, 一共有 t 轮游戏,每轮有 m 次石头剪刀布。
在同一轮的 m 次游戏中,每个人的决策必须是提前确定的,也就是说不能采用随机策略,也不能根据前若干局的结果决定下一局的决策; 这样,显然一共有 n=3m 种决策。
这 n=3m 个人会采取两两不同的决策。 为了方便表达,对于第 x(0≤x<n)个人,将 x 转换成三进制得到一个m位的数。 其中 0 表示剪刀,1 表示石头,2 表示布。就得到了第 x 个人采取的策略。
由于编号是固定的,因此每个人在不同轮的 m 次游戏中都会采取同一套决策。
第 x 个人在最初时有一个分数 f0,x。
在第 i 轮中,他将和另一个人 y 进行 m 次的石头剪刀布的比赛。
我们用 W(x,y) 表示 x 在和 y 的 m 次比赛中赢的次数; 用 L(x,y) 表示 x 在和 y 的 m 次比赛中输的次数。
在第 i 轮结束之后,第 x 个人分数是:
fi,x=∑0≤y<nfi−1,ybu,v
其中 u=W(x,y)=L(y,x),v=L(x,y)=W(y,x),平局不计入次数; bu,v 则是一个给定的评分数组。
注意即使 y 和 x 一样(自己转移到自己)也会乘上一个系数 b0,0(即自己跟自己打全为平局)。
显然随着轮数越来越多,分数也会越来越大, 这个计分系统和我们平时用的计算机一样,也会溢出。 当要储存的分数 f 大于等于 p 的时候,就会变成 fmodp。
B君想知道 t 轮之后所有人的分数,也就是 ft,0,ft,1,…,ft,n−1。
G君:「诶,我发现这个数 p 有特殊的性质诶!不存在两个正整数,使得他们倒数的和等于 3/p!」
B君:「G君好棒!不过这个题怎么做呢?」
输入格式
第一行三个整数,表示 m,t,p。
第二行有 n=3m 个整数,表示 f0,0,f0,1,…,f0,n−1。保证 0≤f0,i<p。
接下来的部分是一个数组 b,第 1 行 m+1 个数,第 2 行 m 个数……第 m+1 行 1 个数。
其中第 i 行的第 j 个数为 bi−1,j−1(i,j≥1,i+j−2≤m),保证 0≤bi,j<p。
不存在两个正整数,使得他们倒数的和等于 3/p。 即不存在正整数 x,y>0,使得 1/x+1/y=3/p。
输出格式
输出 n=3m 行,每行一个整数,表示每个人最终的得分。
其中第 i 行表示第 i 个人的得分 ft,i。
样例一
input
1 1 10009
10 100 1000
2 3
4
output
4320
3240
2430
样例二
input
2 3 103
7 8 9 10 11 12 13 14 15
1 2 3
4 5
6
output
96
8
73
38
53
15
27
42
4
限制与约定
对于所有数据,0≤m≤12,0≤t≤109,1≤p≤109。
测试点mtp1=3≤103无特殊性质2=43=3≤1094=45=56=57=68=79=9≤710=1011=1112=1213=9是质数14=1015=1116=1217=9无特殊性质18=1019=1120=12
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
1 1 10009
10 100 1000
2 3
4
4320
3240
2430
样例 2
2 3 103
7 8 9 10 11 12 13 14 15
1 2 3
4 5
6
96
8
73
38
53
15
27
42
4