UOJ272 -【清华集训2016】石家庄的工人阶级队伍比较坚强

题解以及~~卡常记录~~

题意

经过一系列的转化就变成了矩阵乘法 $B^T f$ 。

题解

我们先从矩阵的性质着手。

定义三进制不退位减 $a \ominus b$ : 设 $a = \sum A_i \cdot 3^i, b = \sum B_i \cdot 3^i, 0 \le A_i, B_i \lt 3$ , 则 $a \ominus b = \sum ((A_i - B_i) \bmod 3) \cdot 3^i$

同理定义三进制不进位加 $a \oplus b = \sum ((A_i + B_i) \bmod 3) \cdot 3^i$ 。可以发现两者为互逆运算。

由 B 矩阵的定义以及石头剪刀布的性质易证： $\forall k \lt 3^m, B_{i \oplus k, j \oplus k} = B_{i, j}$ 。

那么我们可以发现 $B_{i, j} = B_{i \ominus j, 0}$

除此之外，这个结论可以推广到 $B^n$ （数学归纳法）：

B^n_{i, j} = \sum_{k} B^{n - 1}_{i, k} B_{k, j} = \sum_{k} B^{n - 1}_{i \oplus t, k \oplus t} B_{k \oplus t, j \oplus t} = \sum_{k', k = k' \ominus t} B^{n - 1}_{i \oplus t, k'} B_{k', j \oplus t} = B^n_{i \oplus t, j \oplus t}

那么，对于 $f_n = B^Tf$ ,

f_{n, i} = \sum_j B^T_{i, j} f_{j} = \sum_j B^T_{i \ominus j, 0} f_{j} = \sum_{x, y} [x \oplus y = i] B^T_{x, 0} f_y

我们发现，它可以被表示成卷积的形式。这启示我们将矩阵乘法转化成为卷积来计算。

我们来看一下，前面的矩阵乘法（只看第一列）：

B^n_{i, 0} = \sum_j B^{n - 1}_{i, j} B_{j, 0} = \sum_j B^{n - 1}_{i \ominus j, 0} B_{j, 0} = \sum_{x, y} [x \oplus y = i] B^{n - 1}_{x, 0} B_{y, 0}

所以我们发现，只需要对 $B$ 的第一列做 $T$ 次卷积，再和 $f$ 做一次卷积就可以求出答案。

那么我们只需要找到一个变换将 $B$ 变成“点值表达”即可。

考虑类似 FFT 和 FWT 来构造这样的变换。

~~（话说，我的集合幂级数这篇东西有很多东西讲翔了，不要去看，比如下面的内容）~~

卷积复合定理(名字瞎凑的，定理内容直接拖 zrf 课件)：

假设变换 $T_1$ 对 $\circ_1$ 定义的卷积满足卷积定理, $T_2$ 对 $\circ_2$ 定义的卷积满足卷积定理,则这两个变换的复合 $T$ 对 $\circ$ 定义的卷积满足卷积定理。（ $\circ$ 表示一种下标运算，例如本题中的 $\oplus$ ）
即：满足卷积定理的两个卷积的复合仍满足卷积定理。

其中，卷积定理：

对于变换 $T$ 和任意数组 $A, B$ ,如果有:
$T(A) \cdot T(B) = T(A \* B)$
则称变换 $T$ 对于卷积 $\*$ 满足卷积定理。

证明略（证明思路直接暴力推）。

根据这个定理，我们可以将 FWT（对应下标操作为异或的变换）认为是在 $n$ 维下标为 $[0, 1]$ 的空间的变换。那么 FWT 就可以解释为在每一维上做长度为 2 的 DFT。（需要注意到 DFT 实际上对应的下标操作是循环卷积，且异或实际就是模 2 意义的加法）

同样的，我们可以创造出一个变换：

$\ldots$ $n$ 维下标的 $[0, 2]$ 的空间的变换， $\ldots$ 做长度为 3 的 DFT。

只需要类似 FWT 做即可。

另外还有一个问题，三次单位根 $\omega$ 是 $e ^ {\frac{2}{3} \pi i} = -\frac{1}{2} + \frac{\sqrt{3}}{2} i$ , 所以需要模拟复数:

定义数对 $(a, b) = a + \sqrt{3} b i$ ，那么可以定义它的加减乘。

最后需要说明的是奇怪的模数。

因为求单位根需要除 $2$ ，最后 IFWT 的时候要除 $3 ^ m$ 。所以模数对 $2, 3$ 要有逆元。

即 $\gcd(2, p) = 1, \gcd(3, p) = 1 \Rightarrow 2 \nmid p, 3 \nmid p$ 。

题目条件能满足以上条件。(反证，考虑 $\displaystyle \frac{1}{p} + \frac{1}{\frac{p}{2}} = \frac{3}{p}$ 和 $\displaystyle k = \frac{p}{3}, \frac{1}{k + 1} + \frac{1}{k(k + 1)} = \frac{1}{k} = \frac{3}{p}$ )

时间复杂度 $O(3^m (m + \log t))$

~~接下来讲卡常。~~

最慢代码 ~8000ms。

首先乘法取模优化，DFT 部分每个值放在一起乘用 long long 存。(5100ms)

减掉 DFT 中无用枚举。(4800ms)

另外，我们可以删掉一些 $\omega^0 = 1$ 的无用乘法 (4300ms)

根据这个思路，我们可以重定义复数 $(a, b) = a + b \omega$ ，乘法根据 $\omega ^ 2 + \omega + 1 = 0$ 来定义。这样子 DFT 的时候所有的系数都是 $0$ / $1$ / $-1$ , 可以不取模。（3000ms）

最后发现 B 矩阵 DFT 后的本质不同的值很少（只有 $\frac{m(m + 1)}{2}$ 项，即读入的 b[][] 数组大小，证明不会），快速幂的时候拿个 std::map 存下来。（复杂度 $O(3^m m + m^2 \log t)$ ， 900ms）

然而有一个 bug 不知道怎么回事: 看这里，把特判放里面贼慢，拿出来立刻跑快了。。。

最后写个快读应该就是最快代码了（没有实现，700ms）

Code

见上面的提交记录。

然而前 2 份代码 1 2 是假的,

可以看这里

inline int sub(int x) { return x < p ? x + p : x; }

instead of

inline int sub(int x) { return x < 0 ? x + p : x; }

然而 hack 不掉。。。

谁来 hack 一下？

（也许能够让它爆 long long）