闲话 26.7.28

闲话

怎么又三个月没写闲话了！
真没东西可写啊（

P&KU3 中，太神太神了。
day1：好厚的题……
day2：这题都什么玩意啊……
day3：？！！！
day4：？！！！！！！！
我忘却了一切……所见皆是奇迹……
哎打完的那一刻就自动产生戒断反应了
CCBC17怎么还有两周多才开啊

wp 不知道会不会存在啊，很可能不会！
蜡笔糖以最少通过题数完赛后就自动失去了 wp 撰写资格了（什么

依旧推歌：
野鹤 by TN163;
所以我先逃走 by UM feat.洛天依;
概率雨 by 及時作夢 feat. 言和;
河 by 苦以忧 feat. 诗岸;
往生水族馆 by Sakura_Rain feat. 诗岸;
通路 by MaxXSoft et al.;
风之子 by 洛天依;
这次推的还是比较杂/新的！大家可以听听看（

一道使劲拆结构的非(?)多项式数学题

可能是验题人题解？我也不知道。

2026 HDU 多校（1）1009

给定 \(n,m,k\)，以及长为 \(n\) 的序列 \(\{a_i\}\) 和长为 \(2^w\) 的数组 \(H[0\dots 2^w-1]\)。对 \(1\le v \le n\) 定义

\[C_v = \sum_{\bm b} H\left[\left(\sum_{i=1}^m a_{b_i}\right)\bmod 2^w\right] \cdot \left(\sum_{i=1}^m [b_i = v]\right)^k \]

其中 \(\bm b\) 遍历全部长为 \(m\) 的序列 \(\{b_i\}\)（\(1\le b_i\le n\)）。你需要求出全体 \(C_v \bmod 998244353\)。

\(1\le n \le 10^6, 0\le w, k \le 20, 1\le m \le 10^9, 0\le a_i, H[i] < 2^w.\)

std 好像用的是超级 \(n\) 元 GF 啊，看不懂！先使劲做一下化简试试。

\[\begin{aligned} C_v &= \sum_{\bm b} H\left[\left(\sum_{i=1}^m a_{b_i}\right)\bmod 2^w\right] \cdot \sum_{t = 0}^k {k\brace t} \left(\sum_{i=1}^m [b_i = v]\right)^{\underline t} \\ &= \sum_{t = 0}^k {k\brace t} \sum_{\bm b} H\left[\left(\sum_{i=1}^m a_{b_i}\right)\bmod 2^w\right] \cdot \left(\sum_{i=1}^m [b_i = v]\right)^{\underline t} \end{aligned}\]

而最后一项的组合意义本质上就是有序的选择 \(\{b_i\}\) 中 \(t\) 项值为 \(v\) 的元素。因此我们不妨首先选择出一列下标 \(\{i_j\}\)，强制只有这些位置 \(=v\) 的序列才会被计算贡献。由于 \(\bm b\) 遍历全体可能的序列，最终的贡献统计是正确的。式子上，可以写作

\[\begin{aligned} &= \sum_{t = 0}^k {k\brace t} \sum_{\bm b} H\left[\left(\sum_{i=1}^m a_{b_i}\right)\bmod 2^w\right] \sum_{i_1, \dots, i_t} \prod_{j = 1}^t [b_{i_j} = v] \\ &= \sum_{t = 0}^k {k\brace t} \sum_{i_1, \dots, i_t} \sum_{\bm b} H\left[\left(t a_v + \sum_{i \not\in \{i_j\}} a_{b_i}\right)\bmod 2^w\right] \end{aligned}\]

此时，\(b\) 中下标不在 \(\{i_j\}\) 里的部分已经没有任何限制了，而在其中的部分需要强制为 \(v\)，因此可以重写一下 \(b\) 的限制，将其改为一个长为 \(m-t\)、值域不变的序列，仍记作 \(b\)：

\[\begin{aligned} &= \sum_{t = 0}^k {k\brace t} m^{\underline t} \sum_{\lvert\bm b\rvert = m - t} H\left[\left(t a_v + \sum_{i = 1}^{m-t} a_{b_i}\right)\bmod 2^w\right] \end{aligned}\]

此时为了拆贡献，不妨考虑 $$d_k(v) = \sum_{\lvert\bm b \rvert = k} \left[\left(\sum_{i = 1}^k a_{b_i}\right) \bmod 2^w = v\right]$$ 令 $$A(x) = \sum_{i = 1}^n x^{a_i \bmod 2^w}$$ 则 \(d_k\) 的生成函数无非就是 \(A(x)^k \bmod (x^{2^w}-1)\)，即循环卷积，这可以在 \(O(w2^w)\) 复杂度内计算。而回到原式，我们就可以将对 \(b\) 的枚举直接换为对 \(d_{m-t}\) 的枚举了，即

\[\begin{aligned} &= \sum_{t = 0}^k {k\brace t} m^{\underline t} \sum_{i = 0}^{2^w-1} H\left[\left(t a_v + i\right)\bmod 2^w\right]\cdot d_{m-t}(i) \end{aligned}\]

此时后者就是一个循环卷积（\(H\) 和翻转后的 \(d_{m-t}\) 之间），直接做并提取全部 \(ta_v\) 处值就能做到 \(O(kw2^w)\)。但我们还能做到更好。

记 DFT 为 \(\mathcal L\)。考虑我们最后这段在做什么：我们本质上就是将 \(\mathcal L(H)\) 乘以 \(k+1\) 种 \(\mathcal L(A)^{c}\)，使用 \(\mathcal L^{-1}\) 逆回来，随后做了线性组合。但要知道，\(\mathcal L\) 是线性的！我们何不将线性组合推到点值上做呢？可以预见的是，若我们维护得当，这样可以直接将最终 DFT 中的次数 \(k\) 抹去，只需要 \(O(1)\) 次 DFT，将这复杂度摊到系数的线性组合上。

下面先让 \(A\) 翻转。由于 \(m\) 可能很大，但 \(t\) 很小很小，考虑 \(H\) 和 \(d_{m-t}\) 卷积本质上就是令 \(H\) 卷上 \(A^m\) 后和 \(A^{-t}\) 卷积。令 \(E = \mathcal L(H\oplus A^m), F = \mathcal L(A^{-1})\)，这二者都是可以 \(O(w2^w)\) 计算的。那么从点值上考虑，不过是

\[\begin{aligned} \mathcal L^{-1}(C)_v &= \sum_{t = 0}^k {k\brace t} m^{\underline t} \sum_{i = 0}^{2^w-1} E_i F_i^{-t} \omega^{-i\cdot ta_v} \\ &= \sum_{i = 0}^{2^w-1} \sum_{t = 0}^k {k\brace t} m^{\underline t} E_i F_i^{-t} \left(\omega^{- a_v}\right)^{it} \\ &= \left.\sum_{i = 0}^{2^w-1} \sum_{t = 0}^k {k\brace t} m^{\underline t} E_i F_i^{-t} x^{it \bmod 2^w} \right\rvert_{x=\omega^{-a_v}} \end{aligned}\]

能注意到最后我们在支付 \(O(k2^w)\) 的系数计算开销后，不过是需要对一个长为 \(2^w\) 的多项式做在 \(1,\omega,\omega^2,\dots\) 处的多点求值，而这无非是又一次 DFT，其开销仍然只有 \(O(w2^w)\)。对每一项 \(v\)，由于 \(w\) 的指数以 \(2^w\) 为循环节，DFT 能够得到全部所需的值。

总时间复杂度 \(O\!\left((k+w)2^w + n\right)\)。可能算爆标了，也可能不算，我不知道（

代码不放了，实现难度很小。