CometOJ contest#13「火鼠的皮衣 -不焦躁的内心-」(单位根反演),给定n,a,b,pn,a,b,pn,a,b,p,求∑i=0n2aibn−i∗2(n2∗i)\sum_{i=0}^{\frac{n}{2}}
发现原式貌似十分可二项式定理,然后发现确实如此 我们把aiai替换成√a2ia2i然后发现原式求的就是 :(√a+b)n(a+b)n展开后的偶数项 而这些偶数项有个性质,就是他们都不包含√aa,所以我们可以把(√a+b)(a+b)转换到复平面上的点,bb做第一维,√aa做第二维 这样,每次第二维坐标相乘的时候 乘上 A 丢给...