多项式的基本概念 多项式的度 多项式的乘法 多项式的逆元 若存在 g(x)g(x)g(x) 满足： f(x)g(x)≡1(modxn)f(x)g(x) \equiv 1 \pmod{x^n} f(x)g(x)≡1(modxn) 则称 g(x)g(x)g(x) 为 f(x)f(x)f(x) 在模 xnx^nxn 意义下的逆元，g(x)=f−1(x)g(x)=f^{-1}(x)g(x)=...

传送门 首先，遇到等差数列这种形式，最先要想到移项。 A[k]−A[j]=A[j]−A[i]→A[k]+A[i]=2×A[j]A[k]-A[j]=A[j]-A[i] \to A[k]+A[i]=2 \times A[j]A[k]−A[j]=A[j]−A[i]→A[k]+A[i]=2×A[j] 于是很容易想到固定jjj，而在jjj两边枚举i,ki,ki,k。 注意到如果固定jjj，2×A[j]...

此题恶臭，心态被搞了。 考虑SolveSolveSolve算法，每个点有且仅有一次被当做树的根，于是可以将整个算法的期望时间复杂度变成每个点的树的期望大小之和。 想到这里，你还得有一个更加恶臭的想法，考虑如何表示每个点的树的期望大小，记p[i][j]p[i][j]p[i][j]为jjj在iii子树里面的概率。 那么iii子树的期望大小即是∑j!=ip[i][j]\sum _{j!=i} p[...

传送门 题外话，那个式子巨神ypy说是电磁公式之类的，反正我觉得和电磁力什么很像。 Fj=∑i<jqiqj(i−j)2−∑i>jqiqj(i−j)2F_j=\sum_{i<j}\frac{q_i q_j}{(i-j)^2}-\sum_{i>j}\frac{q_i q_j}{(i-j)^2}Fj​=∑i<j​(i−j)2qi​qj​​−∑i>j​(i−j)2...

ProProPro 你可以把一个数mmm分成不超过nnn个数aia_iai​，每一种方案对答案的贡献是∏f(ai)\prod f(a_i)∏f(ai​)，求最后的贡献值。 SolSolSol 很容易列出O(nm2)O(nm^2)O(nm2)的dpdpdp方程 dp[i][y]=∑dp[i−1][y−x]+f[x]dp[i][y]=\sum dp[i-1][y-x]+f[x]dp[i][y...

前置技能：单位根 我们有一个玄学函数f(x)=∑i=0n−1aixif(x)=\sum _{i=0}^{n-1} a_i x^if(x)=∑i=0n−1​ai​xi 不妨换一个好看的形式：f(x)=a0,a1,a2,...an−1f(x)= \\{a_0,a_1,a_2,...a_{n-1} \\}f(x)=a0​,a1​,a2​,...an−1​ 还有另一个玄学函数g(x)=b0,b1,b...

这两个”根“在多项式乘法里面运用非常广泛。 单位根（FFT） 关于我自己对单位根的理解。 单位根其实就是一些复数，他们的模长为111。 所以单位根一定在单位圆上 假设一个单位根zzz的极角为θ\thetaθ，那么我们可以将zzz表示为cos⁡θ+isin⁡θ\cos \theta +i \sin \thetacosθ+isinθ 数形结合考虑，从圆上某一个点做一条垂线，那么垂线长度为sin...

前置芝士： 牛顿迭代 FFT 首先，我们将运动轨迹画出来： 发现hdxriehdxriehdxrie只能沿半径走，AlthenAlthenAlthen只能沿竖直或横向走。 不妨将AlthenAlthenAlthen的路径平移到两条垂直的线段上，总长不变。 设移动时间为ttt，由勾股定理，我们有(A(x)×t)2=(B(x)×t)2+(C(x)×t)2(A(x) \times t)^2=(...

FFT入门 FFT(快速傅里叶变换)是上个学期学会的东西，由于接下来要玩母函数，所以现在写篇博客复习一下。 FFT可以在O(nlog⁡n)O(n\log n)O(nlogn)的时间内完成多项式乘法。 问题 给定两个十进制数（10510^5105位），求它们的乘积。 不妨把它归为一个多项式乘积的问题：每一位都是一个系数，那么1234*2333就变成了： (x3+2x2+3x+4)∗(2...