矩阵逆元

将原矩阵A和一个单位矩阵I做成$(A,I)$，用初等行变换将大矩阵中的A变为I，则会得到$(I,A^{-1})$的形式

行列式值计算

利用Gauss消元将行列式矩阵转成上三角矩阵，行列式的值则为对角线上所有值的乘积

对于模数为一般数$M$的行列式值，Gauss消元时可以一边$A_i \Leftarrow A_i−A_j(A_{i,k} ~div~ A_{j,k})$一边$swap(A_i,A_j)$来完成消元（交换行时行列式值取反）

FFT

系统自带Complex版

inline void FFT(cd *a, int op)
{
	for(int i=0, j=0; i<n; i++)
	{
		if (i<j) swap(a[i],a[j]);
		int k=n>>1;
		while (j&k) j-=k, k>>=1; j+=k; //取反
	}
	for(int i=2; i<=n; i<<=1)
	{
		cd wn=cd(cos(2.0*pi/i),op*sin(2.0*pi/i));
		for(int j=0; j<n; j+=i)
		{
			cd w=cd(1,0);
			for(int k=j; k<j+i/2; k++)
			{
				cd x=a[k], y=w*a[k+i/2];
				a[k]=x+y, a[k+i/2]=x-y;
				w*=wn;
			}
		}
	}
	if (op==-1) rep(i, 0, n-1) a[i].real()/=n;
}

自制Complex版

struct cp{double r,i;} A[maxn], B[maxn];

inline cp operator + (const cp &A, const cp &B){return (cp){A.r+B.r, A.i+B.i};}
inline cp operator - (const cp &A, const cp &B){return (cp){A.r-B.r, A.i-B.i};}
inline cp operator * (const cp &A, const cp &B){return (cp){A.r*B.r-A.i*B.i, A.r*B.i+A.i*B.r};}

inline void FFT(cp *a, int op)
{
	for(int i=0, j=0; i<n; i++)
	{
		if (i<j) swap(a[i],a[j]);
		int k=n>>1;
		while (j&k) j-=k, k>>=1; j+=k; //取反
	}
	for(int i=2; i<=n; i<<=1)
	{
		cp wn=(cp){cos(2.0*pi/i),op*sin(2.0*pi/i)};
		for(int j=0; j<n; j+=i)
		{
			cp w=(cp){1,0};
			for(int k=j; k<j+i/2; k++)
			{
				cp x=a[k], y=w*a[k+i/2];
				a[k]=x+y, a[k+i/2]=x-y;
				w=w*wn;
			}
		}
	}
	if (op==-1) rep(i, 0, n-1) a[i].r/=n;
}

NTT

速度比 FFT 慢（模运算常数）

无精度误差

在模 $998244353(119*2^{23}+1)$ 的时候，当 $n<=2^{23}$ 时可用，单位变成原根 $g$ 的 $\frac{Q-1}{2^i}$ 次方

int rev[maxn], inv;

inline void dft(int *a, int op)
{
	rep(i, 0, n-1) if (i<rev[i]) swap(a[i],a[rev[i]]);
	for(int i=2; i<=n; i<<=1)
	{
		int wn=Pow(g,op>0?(Q-1)/i:Q-1-(Q-1)/i);
		for(int j=0; j<n; j+=i)
		{
			int w=1;
			for(int x=j,y=j+(i>>1); y<j+i; x++,y++)
			{
				int X=a[x], Y=1LL*a[y]*w%Q;
				a[x]=(X+Y)%Q, a[y]=(X-Y+Q)%Q, w=1LL*w*wn%Q;
			}
		}
	}
	if (op<0) rep(i, 0, n-1) a[i]=1LL*a[i]*inv%Q;
}

Schwartz-Zippel定理

定义在有限域 $F$ 上的 $d$ 次非零多元多项式 $f(x_1,x_2...)$，随机选取 $x_i$ 的值，多项式值为0的概率是 $\frac{d}{|F|}$

判定方法：选取合适的有限域之后多次判断，$c$ 次判断的错误率为 $1-(\frac{d}{|F|})^c$

多项式模

其实就是使得被模的多项式的最高次数小于作为模数的多项式的最高次数，不断增减补补然后删

不可约多项式

$F(x)=x^{28}+x^{27}+x^{26}+x^{25}+...+x+1$

$F(x)=x^{30}+x^5+x^4+x^2+1$（0x20000035）

more