P6673 [Tsinghua Training 2016] The Working Class Team in Shijiazhuang Is Quite Strong

Mr. B and Mr. G are on a pedestrian overpass. Mr. B: “It’s winter again. If I count it, I’ve been in college for more than three years now.” Mr. G: “Yeah.” Mr. B: “There are more couples on the street again. Thinking back to three years ago, I was also like this...” Mr. G: “??” Mr. B: “...watching couples on the overpass!” Mr. G: “Hmm.” Mr. B: “But this time you are with me~” Mr. G: “...” Mr. B: “Hey hey, I have a question for you~” Mr. G: “Ask.” Mr. B: “Suppose $n=3^m$ people play cei ding ke together.” Mr. G: “Huh? What is cei ding ke?” Mr. B: “It’s rock-paper-scissors~ We also call it ding gang chui.” Mr. G: “You’re asking about that?” Mr. B: “Wait, I’m not done yet.”

There are $n=3^m$ people playing rock-paper-scissors. There are a total of $t$ rounds, and in each round there are $m$ games of rock-paper-scissors. Within the $m$ games of the same round, each person’s decisions must be fixed in advance. That is, they cannot use a randomized strategy, and they cannot decide the next game based on the results of previous games. Therefore, there are clearly $n=3^m$ possible strategies. These $n=3^m$ people will all use pairwise different strategies. For convenience, for person $x$ ($0 \le x < n$), convert $x$ to base $3$ to get an $m$-digit number, where $0$ means scissors, $1$ means rock, and $2$ means paper. This gives the strategy used by person $x$. Since the indices are fixed, in the $m$ games of each round, everyone will always use the same set of decisions across different rounds. Person $x$ initially has a score $f_{0,x}$. In round $i$, he will play $m$ games of rock-paper-scissors against another person $y$. Let $W(x,y)$ be the number of wins of $x$ against $y$ in these $m$ games. Let $L(x,y)$ be the number of losses of $x$ against $y$. After round $i$ ends, person $x$’s score is: $$f_{i,x}=\sum_{0 \le y < n} f_{i-1,y} b_{u,v}$$ where $u=W(x,y)=L(y,x)$ and $v=L(x,y)=W(y,x)$. Draws are not counted; $b_{u,v}$ is a given scoring array. Note that even if $y$ is the same as $x$ (transitioning from oneself to oneself), it will still be multiplied by a coefficient $b_{0,0}$ (because playing against oneself results in all draws). Obviously, as the number of rounds increases, the scores will grow larger. This scoring system, like computers in daily use, can overflow. When a score $f$ to be stored is greater than or equal to $p$, it becomes $f \bmod p$. Mr. B wants to know everyone’s scores after $t$ rounds, i.e., $f_{t,0}, f_{t,1}, \ldots, f_{t,n-1}$. Mr. G: “Hey, I found that this number $p$ has a special property! There do not exist two positive integers such that the sum of their reciprocals equals $3/p$!” Mr. B: “Mr. G is amazing! But how do we solve this problem?”

The first line contains three integers $m, t, p$. The second line contains $n=3^m$ integers, representing $f_{0,0}, f_{0,1}, \ldots, f_{0,n-1}$. It is guaranteed that $0 \le f_{0,i} < p$. The following part is an array $b$: the 1st line has $m+1$ numbers, the 2nd line has $m$ numbers, ..., and the $(m+1)$-th line has $1$ number. The $j$-th number in the $i$-th line is $b_{i-1,j-1}$ ($i,j \ge 1, i+j-2 \le m$). It is guaranteed that $0 \le b_{i,j} < p$. There do not exist two positive integers such that the sum of their reciprocals equals $3/p$. That is, there do not exist positive integers $x,y>0$ such that $1/x+1/y=3/p$.

Output $n=3^m$ lines, each containing one integer, representing each person’s final score. The $i$-th line represents the $i$-th person’s score $f_{t,i}$.

For all testdata, $0 \le m \le 12$, $0 \le t \le 10^9$, $1 \le p \le 10^9$. Translated by ChatGPT 5