CF453D Little Pony and Elements of Harmony

题目描述

题意翻译：

谐律精华是六个超自然的神器，它们代表着"和谐"自身主观的意志。它们被认为是小马国最强大的力量。

谐律精华的内部，可以被看作是一个有 $n$ 个节点的完全图，从 $0$ 到 $n-1$ 标号，$n$ 是一个二的幂次，等于 $2^m$ 。

上图是六个谐律精华。

谐律精华中的能量在不断变化。根据古籍记载，节点 $u$ 在时间 $i$ 时的能量(记作 $e_i[u]$ )为：

$e_i[u]=\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$ 取模的结果。

输入输出样例 #1

输入 #1

2 2 10000
4 1 2 3
0 1 0

输出 #1

14
6
6
14