【zr25年省选联考day15】B. Prob 做题记录

设 $p=299993$，给定 $n$ 个 $[0,p-1]$ 中的整数对 $(x_i,y_i)$，$q$ 次询问，每次给定一个 $[0,p-1]$ 中的整数 $z$，求满足以下条件的 $[0,p-1]$ 中的整数对 $(x,y)$ 的个数：

$\prod((x-x_i)^2+(y-y_i)^2)\equiv z\pmod p$

$1\le n\le 100$，$1\le q< p$。

考虑找到模 $p$ 域下的“虚数” $t^2\equiv -1\pmod p$，然后应用平方差公式：（和的乘积化为乘积的乘积）

$\begin{aligned} \prod((x-x_i)^2+(y-y_i)^2)&=\prod((x-x_i)^2-(ty-ty_i)^2)\\ &=\prod(x-x_i+ty-ty_i)(x-x_i-ty+ty_i)\\ &=\prod((x+ty)-(x_i+ty_i))\prod((x-ty)-(x_i-ty_i))\\ \end{aligned}$

注意到有序对 $(x,y)$ 和 $(x+ty,x-ty)$ 构成双射，故仅需关心 $x+ty$ 和 $x-ty$。

设 $G(x)=\prod(x-(x_i+ty_i))$，$H(x)=\prod (x-(x_i-ty_i))$，那么 $F(\frac{x+y}{2},\frac{x-y}{2t})=G(x)H(y)$。

所以只需要求有多少个 $(x,y)$ 满足 $G(x)H(y)=z$。

一个个代入求出 $G([0,p-1])$ 和 $H([0,p-1])$，再做 FFT 即可。注意这里是 $a_ib_j$ 贡献到 $c_{ij}$，故需要对原根取对数。

感觉一下答案不会很大，所以直接做 NTT 也可以。