题意
略。
题解
由于每个人在每轮的决策序列都是一样的，设(c_{x, y})为(y)对(x)产生的贡献，则有
其中定义(ominus)为三进制不退位减法。
(cnt_1(x))表示(x)的三进制中1的个数，(cnt_2(x))同理。
记
设(f_{t, i})表示进行了(t)轮游戏后第(i)个人的分数。
考虑(j)对(i)产生的贡献，显然有
由于(ominus)和(oplus)（三进制不进位加法）是逆运算，有
显然这是一个fwt，但是是三进制的fwt。这就涉及到fwt的本质fwt实际上是高维fft，始终满足卷积定理（这才有了fwt！）。
考虑fft的时候使用的变换矩阵——范德蒙德矩阵
其逆矩阵为
其中，当(n = 2)时，实际上就是fwt的矩阵：
而
同理，现在是(n = 3)，理论上只要使用三次单位根就好了，即(omega ^ 2 + omega + 1 = 0)，得(omega = frac{-1 + sqrt 3 i}{2})。
但是问题是现在要做fwt次数比较多，要在模意义下做，不能有浮点运算（精度可能不够）。
但是这个模数(p)又很奇怪。
通过一些奇奇怪怪的分析和结论，得出(-3)在模(p)意义下有二次剩余（根据题目给出(p)的性质）。
但是求出这个二次剩余要用excipolla，所以考虑直接在扩域({a + bsqrt 3 i})下做。
这是做一次fwt的情况。要转移(T)次怎么办？直接把(fwt(C))的每一个点值分别快速幂（(T)次方）即可。
复杂度(mathcal O((n + T) cdot 3 ^ n))，常数较大。
#pragma GCC optimize(2, "Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 13, M = 531441;
int n, m, T, mod, omgs, inv2, inv3, divi, pw3[N], tr[N][N];
inline int power (int a, int b) {
int ret = 1;
for ( ; b; b >>= 1, a = 1ll * a * a % mod) {
if (b & 1) {
ret = 1ll * ret * a % mod;
}
}
return ret;
}
struct cp {
int r, i;
inline cp () {
r = i = 0;
}
inline cp (int a, int b) {
r = a, i = b;
}
inline cp operator * (const cp &o) {
return cp((1ll * r * o.r + 1ll * i * o.i % mod * omgs) % mod, (1ll * r * o.i + 1ll * i * o.r) % mod);
}
inline cp operator + (const cp &o) {
cp t(r + o.r, i + o.i);
if (t.r >= mod) {
t.r -= mod;
}
if (t.i >= mod) {
t.i -= mod;
}
return t;
}
} w, wsq, a[M], b[M];
inline cp power (cp a, int b) {
cp ret(1, 0);
for ( ; b; b >>= 1, a = a * a) {
if (b & 1) {
ret = ret * a;
}
}
return ret;
}
inline void fwt (cp *a, int sgn) {
cp wn = (sgn == 1 ? w : wsq), wns = (sgn == 1 ? wsq : w);
for (int l = 3, m = l / 3; l <= n; m = l, l *= 3) {
for (int i = 0; i < n; i += l) {
for (int j = 0; j < m; ++j) {
cp x = a[i + j], y = a[i + m + j], z = a[i + m + m + j];
a[i + j] = x + y + z;
a[i + m + j] = x + y * wn + z * wns;
a[i + m + m + j] = x + y * wns + z * wn;
}
}
}
}
void tripcnt (int x) {
int r[3] = {0, 0, 0};
for (int i = x; i; i /= 3) {
++r[i % 3];
}
b[x].r = tr[r[1]][r[2]];
}
void prep () {
pw3[0] = 1;
for (int i = 1; i <= n; ++i) {
pw3[i] = pw3[i - 1] * 3;
}
omgs = mod - 3;
inv2 = (mod + 1) >> 1;
inv3 = (mod % 3 == 1 ? mod - mod / 3 : 1ll * inv2 * (mod - mod / 3) % mod);
divi = power(inv3, n);
w = cp(mod - inv2, inv2), wsq = w * w;
}
int main() {
scanf("%d%d%d", &n, &T, &mod);
prep(), m = pw3[n];
for (int i = 0; i < m; ++i) {
scanf("%d", &a[i].r);
}
for (int i = 0; i <= n; ++i) {
for (int j = 0; i + j <= n; ++j) {
scanf("%d", &tr[i][j]);
}
}
n = m;
for (int i = 0; i < n; ++i) {
tripcnt(i);
}
fwt(a, 1), fwt(b, 1);
for (int i = 0; i < n; ++i) {
a[i] = a[i] * power(b[i], T);
}
fwt(a, -1);
for (int i = 0; i < n; ++i) {
printf("%d
", 1ll * a[i].r * divi % mod);
}
return 0;
}
upd：
现在想想最后这个处理方法显然不能叫“扩域”，这个东西在模一个非质数意义下，连一个域都不算。。。
这东西顶多只能算一个暂时性的扩充数系？毕竟本题只要求它的加运算和乘运算和交换、结合、分配率，并且有2的逆元，而事实是，对于任意一个满足题目要求的(p)，都满足这几条。
另外的要求也许是要求这个暂时性的数系和(_p)要同构？（反正只能说类似模意义下的二次剩余）