302354: CF453D. Little Pony and Elements of Harmony
Memory Limit：256 MB
Time Limit：6 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Little Pony and Elements of Harmony
题意翻译
题意翻译： 谐律精华是六个超自然的神器，它们代表着"和谐"自身主观的意志。它们被认为是小马国最强大的力量。 谐律精华的内部，可以被看作是一个有 $n$ 个节点的完全图，从 $0$ 到 $n-1$ 标号，$n$ 是一个二的幂次，等于 $2^m$ 。  上图是六个谐律精华。 谐律精华中的能量在不断变化。根据古籍记载，节点 $u$ 在时间 $i$ 时的能量(记作 $e_i$ )为： $e_i=\sum_ve_{i-1}[v]\cdot b[f(u,v)]$ 。这里 $b[]$ 称作变换系数——一个有 $m+1$ 个元素的数组。而 $f(u,v)$ 为二进制数 $(u\;xor\;v)$ 中 $1$ 的个数。 给定变换系数 $b[]$ 和在时间 $0$ 时的初始能量分布 $e_0[]$ 。帮助暮光闪闪预测在时刻 $t$ 时的能量分布。答案可能非常大，你只要输出答案除以 $p$ 的余数即可。 **输入格式：** 第一行三个整数 $m,t,p$ $(1\le m\le 20,0\le t\le10^{18},2\le p\le10^9)$ 。 接下来一行 $n$ $(n=2^m)$ 个整数 $e_0[i]$ $1\le e_0[i]\le 10^9,0\le i<n$ 。 接下来一行 $m+1$ 个整数 $b[i]$ $(0\le b[i]\le 10^9,0\le i\le m)$ 。 **输出格式：** 输出 $n$ 行，第 $i$ 行包含一个整数表示 $e_t[i]$ 对 $p$ 取模的结果。题目描述
The Elements of Harmony are six supernatural artifacts representing subjective aspects of harmony. They are arguably the most powerful force in Equestria. The inside of Elements of Harmony can be seen as a complete graph with $ n $ vertices labeled from 0 to $ n-1 $ , where $ n $ is a power of two, equal to $ 2^{m} $ . The energy in Elements of Harmony is in constant movement. According to the ancient book, the energy of vertex $ u $ in time $ i $ $ (e_{i}) $ equals to: Here $ b[] $ is the transformation coefficient — an array of $ m+1 $ integers and $ f(u,v) $ is the number of ones in the binary representation of number $ (u xor v) $ . Given the transformation coefficient and the energy distribution at time 0 $ (e_{0}[]) $ . Help Twilight Sparkle predict the energy distribution at time $ t $ $ (e_{t}[]) $ . The answer can be quite large, so output it modulo $ p $ .输入输出格式
输入格式
The first line contains three integers $ m $ , $ t $ and $ p $ ( $ 1<=m<=20; 0<=t<=10^{18}; 2<=p<=10^{9} $ ). The following line contains $ n $ ( $ n=2^{m} $ ) integers $ e_{0}[i] $ ( $ 1<=e_{0}[i]<=10^{9}; 0<=i<n $ ). The next line contains $ m+1 $ integers $ b[i] $ ( $ 0<=b[i]<=10^{9}; 0<=i<=m $ ).
输出格式
Output $ n $ lines, the $ i $ -th line must contain a single integer $ e_{t}[i] $ modulo $ p $ .
输入输出样例
输入样例 #1
2 2 10000
4 1 2 3
0 1 0
输出样例 #1
14
6
6
14