CF1054H Epic Convolution

Editorial 的做法似乎太复杂了？

题意：给出 $a, b$ 序列，求：

$$\sum_{i = 0} ^ {n - 1} a_i b_j c ^ {i ^ 2j ^ 3}$$

对 $P = 490019$ 取模的结果。$n, m\leq 10 ^ 5$，$a_i, b_i\leq 1000$。

其实有非常简洁的做法啊……

考虑如果是下面这种形式怎么做：

$$\sum_{i = 0} ^ {n - 1} \sum_{j = 0} ^ {m - 1} a_ib_j c ^ {ij}$$

这个我们在 BlueStein 算法 中提到过，就是 Chirp-Z 变换，把 $ij$ 拆成 $\binom{i + j}2 - \binom i2 - \binom j2$，可以在 $O(n\log n)$ 的时间内解决。

现在考虑计算原式。一个显然的想法就是我们还是替换成上面的类型。于是，我们把 $a_i$ 贡献到 $i \times i$ 的位置，把 $b_j$ 贡献到 $j\times j\times j$ 的位置。但是注意到贡献的位置 $\bmod P - 1$ 相同则贡献相同，于是只需要贡献到 $i ^ 2\bmod P - 1$ 的位置即可，$j ^ 3$ 同理。

最后我们直接按照上面的做法直接暴力变换，时间复杂度 $O(P\log P)$，可以通过。

int main()
{
	int n, m, c;
	std::cin >> n >> m >> c;
	poly a(Mod - 1), b(Mod - 1);
	for (int i = 0, x; i < n; ++ i)
		scanf("%d", &x), adj(a[(LL) i * i % (Mod - 1)] += x - Mod);
	for (int i = 0, x; i < m; ++ i)
		scanf("%d", &x), adj(b[(LL) i * i * i % (Mod - 1)] += x - Mod);
	for (int i = 0; i < Mod - 1; ++ i)
		a[i] = (LL) a[i] * qpow(c, Mod - 1 - i * (i - 1LL) / 2 % (Mod - 1)) % Mod;
	for (int i = 0; i < Mod - 1; ++ i)
		b[i] = (LL) b[i] * qpow(c, Mod - 1 - i * (i - 1LL) / 2 % (Mod - 1)) % Mod;
	a = a * b;
	for (int i = 0, ed = a.size(); i < ed; ++ i)
		a[i] = (LL) a[i] * qpow(c, i * (i - 1LL) / 2 % (Mod - 1)) % Mod;
	int res = 0;
	for (int &x : a) adj(res += x - Mod);
	std::cout << res << '\n';
	return 0;
}