CF1054H Epic Convolution

最近突然想做多项式了，就找了些题，这道题用的 2D-FFT 的科技我还不会

首先和式的 $i$ 和 $j$ 除了出现在下标上，就是出现在指数上，并且 $490019$ 是一个质数 $φ (490019) = 490018 = 2 \times 491 \times 499$ 我们就可以想到按照 $i^{2} j^{3}$ 模这些数的值的余数来计算，即答案为 $\sum_{x} \sum_{y} \sum_{z} c^{[x, y, z]} \sum_{i = 0}^{n - 1} \sum_{j = 0}^{n - 1} A_{i} B_{j} [i^{2} j^{2} \mod 491 = x] [i^{2} j^{2} \mod 499 = y] [i^{2} j^{2} \mod 2 = z]$

其中 $[x, y, z]$ 为中国剩余定理的合并

并且我们知道通过离散对数可以很容易把乘变成加，其中 $2$ 的原根为 $1$ ， $491$ 的原根为 $2$ ， $499$ 的原根为 $7$ ， $2$ 其实也可以不搞原根，直接暴力，那么考虑我们最后需要求出的二元函数 $f_{i} (x, y)$ ， $g_{i} (x, y)$ ， $h_{i} (x, y)$ 实际上表示为

$[x^{n} y^{m}] f_{t} = \sum_{i^{2} \mod 2 = t, {ind}_{2}^{491} i^{2} = n, {ind}_{7}^{499} i^{2} = m} A_{i}$

$[x^{n} y^{m}] g_{t} = \sum_{i^{2} \mod 2 = t, {ind}_{2}^{491} i^{3} = n, {ind}_{7}^{499} i^{3} = m} B_{i}$

$[x^{n} y^{m}] h_{t} = \sum_{a & b = t} [x^{n} y^{m}] (f_{a} \times g_{b})$

而后面的 $f_{a}$ 与 $g_{b}$ 为二维卷积，需要用 2D-FFT 优化

其中，2D-FFT 的公式通过如下给出，首先是 DFT

$y_{i, j} = \sum_{k = 0}^{n - 1} \sum_{l = 0}^{m - 1} a_{k, l} ω_{n}^{i k} ω_{n}^{j l}$

而加入我们定列 DFT 为

$z_{i, l} = \sum_{k = 0}^{n - 1} a_{k, l} ω_{n}^{i k}$

很显然

$y_{i, j} = \sum_{l = 0}^{m - 1} ω_{n}^{j l} z_{i, l}$

综上，2D-DFT 即为先做列 DFT 在做行 DFT，颠倒也可以，那么 IDFT 同理

最后需要考虑有一些不存在离散对数的情况，那么这些为 $491$ 或 $499$ 的倍数，需要单独抽出来考虑，我们认为 $n, m$ 同阶的话复杂度有 $O (p \log p + \frac{n^{2}}{\sqrt{p}})$ 需要轻微卡常