省选模拟赛 #52 T3 补题记录

link

被教育了，不过还是想吐槽一下为什么不给 \(\mathcal O(m\log n \cdot 7^4)\) 这档分。

下面称最高位为第一位，以此类推。

先找到第一个满足 \(l\) 与 \(r\) 不同的位 \(st\)，称一个大于 \(l\) 且小于 \(r\) 的数第一个与 \(l\) 和 \(r\) 都不同的位为过渡位，过渡位后面都是自由位。那么我们可以枚举最小的过渡位 \(i(i\ge st)\)，那么对于 \(i + 1\sim n\) 位，因为有自由位，只需要将算出的方案数乘上 \((\dfrac 1k) ^ {m - i}\)。然后每个数可以取 \(l_i\) 或者 \(r_i\) 或者过渡位，每种取法都有对应的方案数，满足最终所有数第 \(i\) 位的总和模 \(7\) 余数为 \(s_i\)，显然可以快速幂循环卷积。

但是对于 \(i\ge st + 1\)，每个数如果是过渡位，还分为由 \(l\) 过渡或者由 \(r\) 过渡，且满足 \(n\) 个数中取 \(l\) 和由 \(l\) 过渡的数的个数模 \(7\) 等于一个常数 \(c\)，这是因为第 \(st\) 位会有限制，满足 \(l_{st} \cdot c + r_{st} \cdot (n - c) \equiv s_{st} \pmod 7\)（如果存在 \(j\in [st + 1, i - 1]\) 满足 \(l_j \cdot c + r_j \cdot (n - c) \not \equiv s_j \pmod 7\) 则已经不合法）。所以我们需要快速幂里面做二维循环卷积，时间复杂度 \(\mathcal O(m\log n \cdot b^4)\)，其中 \(b = 7\)。

时间复杂度显然太劣，考虑单位根反演。

快速幂二维循环卷积只需要单点求值，不妨记为 \((u, v)\)。

那么我们需要求：

\[\begin{aligned} & \quad \sum_{\{i\}}\sum_{\{j\}} \left ( \prod_{k = 1} ^ n a_{i_k, j_k} \right ) [\sum_{k = 1} ^ n i_k \bmod 7 = u] [\sum_{k = 1} ^ n j_k \bmod 7 = v] \\ &= \frac 1 {49} \sum_{p = 0} ^ 6 \sum_{q = 0} ^ 6 \sum_{\{i\}}\sum_{\{j\}} \left ( \prod_{k = 1} ^ n a_{i_k, j_k} \right ) \omega ^ {p\sum_{k = 1} ^ n i_k - u} \omega ^ {q\sum_{k = 1} ^ n j_k - v} \\ &= \frac 1 {49} \sum_{p = 0} ^ 6 \sum_{q = 0} ^ 6 \omega ^ {-pu - qv} \sum_{\{i\}}\sum_{\{j\}} \left ( \prod_{k = 1} ^ n a_{i_k, j_k} \omega ^ {i_kp + j_kq} \right) \end{aligned}\]

记 \(S_{p, q} = \sum\limits_{i = 0} ^ 6\sum\limits_{j = 0} ^ 6 a_{i, j} \omega ^ {ip + jq}\)，那么结果为 \(\dfrac 1 {49} \sum\limits_{p = 0} ^ 6 \sum\limits_{q = 0} ^ 6 \omega ^ {-pu - qv} S_{p, q} ^ n\)。

就可以 \(\mathcal O(\log n \cdot p^2)\) 算了。

同样的，一维循环卷积也可以类似优化，时间复杂度降为 \(\mathcal O(m\log n \cdot p^2)\)。