题解：AT_abc392_g [ABC392G] Fine Triplets

CuFeO4 · 2025-02-15 21:24:36 · 题解

打过最水的 G 题。

先变式子，变成 A+C=2\times B，发现这是一个卷积的形式，而且值域 \le 10^6，直接上 NTT 或者 FFT 即可。

假设卷积后的结果为 F，枚举 s_i，那么答案就是 \frac{F_{2\times s_i}-1}{2}，减 1 是因为 s_i+s_i=2\times s_i，除以 2 是因为顺序无关。

AC Link。