【数论】矩阵、多项式运算、FFT

NanoApe posted @ 2016年1月05日 20:08 in 蒟蒻不撕烤智熵何来 , 1182 阅读

将原矩阵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)$ 来完成消元（交换行时行列式值取反）

系统自带Complex版

FFT-Slow
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24	`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.0pi/i),opsin(2.0pi/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=wa[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版

FFT-Fast
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30	`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.rB.r-A.iB.i, A.rB.i+A.iB.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.0pi/i),opsin(2.0pi/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=wa[k+i/2];` `a[k]=x+y, a[k+i/2]=x-y;` `w=wwn;` `}` `}` `}` `if` `(op==-1) rep(i, 0, n-1) a[i].r/=n;` `}`

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

无精度误差

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

NTT
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20	`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=1LLa[y]w%Q;` `a[x]=(X+Y)%Q, a[y]=(X-Y+Q)%Q, w=1LLwwn%Q;` `}` `}` `}` `if` `(op<0) rep(i, 0, n-1) a[i]=1LLa[i]*inv%Q;` `}`

定义在有限域 $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）

NanoApe's Blog