抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

题解以及卡常记录

题意

我不想抄题了

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

题解

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

定义三进制不退位减 aba \ominus b: 设 a=Ai3i,b=Bi3i,0Ai,Bi<3a = \sum A_i \cdot 3^i, b = \sum B_i \cdot 3^i, 0 \le A_i, B_i \lt 3, 则 ab=((AiBi)mod3)3ia \ominus b = \sum ((A_i - B_i) \bmod 3) \cdot 3^i

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

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

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

除此之外,这个结论可以推广到BnB^n(数学归纳法):

Bi,jn=kBi,kn1Bk,j=kBit,ktn1Bkt,jt=k,k=ktBit,kn1Bk,jt=Bit,jtnB^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}

那么,对于fn=BTff_n = B^Tf,

fn,i=jBi,jTfj=jBij,0Tfj=x,y[xy=i]Bx,0Tfyf_{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

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

我们来看一下,前面的矩阵乘法(只看第一列):

Bi,0n=jBi,jn1Bj,0=jBij,0n1Bj,0=x,y[xy=i]Bx,0n1By,0B^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}

所以我们发现,只需要对 BB 的第一列做 TT 次卷积,再和 ff 做一次卷积就可以求出答案。

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


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

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

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

假设变换 T1T_11\circ_1 定义的卷积满足卷积定理, T2T_22\circ_2 定义的卷积满足卷积定理,则这两个变换的复合 TT\circ 定义的卷积满足卷积定理。(\circ表示一种下标运算,例如本题中的 \oplus
即:满足卷积定理的两个卷积的复合仍满足卷积定理。

其中,卷积定理

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

证明略(证明思路直接暴力推)。

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

同样的,我们可以创造出一个变换:

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

只需要类似 FWT 做即可。

另外还有一个问题,三次单位根ω\omegae23πi=12+32ie ^ {\frac{2}{3} \pi i} = -\frac{1}{2} + \frac{\sqrt{3}}{2} i, 所以需要模拟复数:

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

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

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

gcd(2,p)=1,gcd(3,p)=12p,3p\gcd(2, p) = 1, \gcd(3, p) = 1 \Rightarrow 2 \nmid p, 3 \nmid p

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

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


接下来讲卡常。

最慢代码 ~8000ms。

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

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

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

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

最后发现 B 矩阵 DFT 后的本质不同的值很少(只有m(m+1)2\frac{m(m + 1)}{2}项,即读入的 b[][] 数组大小,证明不会),快速幂的时候拿个 std::map 存下来。(复杂度 O(3mm+m2logt)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