最近突然想做多项式了，就找了些题，这道题用的 2D-FFT
的科技我还不会
首先和式的 \(i\) 和 \(j\) 除了出现在下标上，就是出现在指数上，并且 \(490019\) 是一个质数 \(\varphi(490019)=490018=2\times491\times499\) 我们就可以想到按照 \(i^2j^3\) 模这些数的值的余数来计算，即答案为 \[ \sum_x\sum_y\sum_zc^{[x,y,z]}\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}A_iB_j[i^2j^2\operatorname{mod}491=x][i^2j^2\operatorname{mod}499=y][i^2j^2\operatorname{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^ny^m]f_t=\sum_{i^2\operatorname{mod}2=t,\operatorname{ind}_2^{491}i^2=n,\operatorname{ind}_7^{499}i^2=m}A_i \]
\[ [x^ny^m]g_t=\sum_{i^2\operatorname{mod}2=t,\operatorname{ind}_2^{491}i^3=n,\operatorname{ind}_7^{499}i^3=m}B_i \]
\[ [x^ny^m]h_t=\sum_{a\And b=t}[x^ny^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}\omega_n^{ik}\omega_n^{jl} \]
而加入我们定列 DFT 为
\[ z_{i,l}=\sum_{k=0}^{n-1}a_{k,l}\omega_n^{ik} \]
很显然
\[ y_{i,j}=\sum_{l=0}^{m-1}\omega_n^{jl}z_{i,l} \]
综上，2D-DFT 即为先做列 DFT 在做行
DFT，颠倒也可以，那么 IDFT 同理
最后需要考虑有一些不存在离散对数的情况，那么这些为 \(491\) 或 \(499\) 的倍数，需要单独抽出来考虑，我们认为 \(n,m\) 同阶的话复杂度有 \(\operatorname{O}(p\log p+\frac{n^2}{\sqrt p})\) 需要轻微卡常