二次剩余 Cipolla's algorithm
定义
当存在某个 \(x\),式子 \(x^2\equiv a\pmod p\) 成立时,称“\(a\) 是模 \(p\) 的二次剩余(Quadratic residue)”
当存在某个 \(x\),式子 \(x^2\equiv a\pmod p\) 成立时,称“\(a\) 是模 \(p\) 的二次剩余(Quadratic residue)”
常数好大
在有些dp中,转移可以用一种具有结合律的变换描述,并且可以快速合并
因此我们使用数据结构维护,来支持修改并快速得到全局或某个子结构的dp值
封装的代码可以看挑战多项式
写的时候要注意各种清空问题.