多项式

多项式部分总结

感觉并无何用

Posted by JU on April 15, 2019

多项式部分总结

$FFT$

struct cp
{
    db real,imag;
    cp (db x=0,db y=0) { real=x,imag=y; }
};
cp operator + (cp A,cp B) { return cp(A.real+B.real,A.imag+B.imag); }
cp operator - (cp A,cp B) { return cp(A.real-B.real,A.imag-B.imag); }
cp operator * (cp A,cp B) { return cp(A.real*B.real-A.imag*B.imag,A.real*B.imag+B.real*A.imag); }
cp operator / (cp A,db B) { return cp(A.real/B,A.imag/B); }
const db PI=acos (-1);
cp w[N];
int rev[N];
void FFT (cp *a,int n,int kind)
{
    for (int i=0; i< n; i++)
        if (i< rev[i]) swap (a[i],a[rev[i]]);
    for (int i=1; i< n; i<<=1)
        for (int j=0,sb=i<<1; j< n; j+=sb)
        {
            int cur=0;
            for (int k=j; k< j+i; k++)
            {
                cp x=a[k],y=w[cur]*a[k+i];
                a[k]=x+y;
                a[k+i]=x-y;
                cur=(cur+kind*n/(i<<1)+n)&(n-1);
            }
        }
    if (kind==-1)
        for (int i=0; i< n; i++)
            a[i]=a[i]/n;
}
int init (int n)
{
    int s=2,bit=1;
    while (s< (n)) s<<=1,++bit;
    for (int i=0; i< s; i++)
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
    for (int i=0; i< s; i++)
        w[i]=cp(cos (2*PI*i/s),sin (2*PI*i/s));
    return s;
}

$NTT$

const int YG=3,P=998244353;//原根
int ksm (int a,int b)
{
	int ans=1;
	while (b)
	{
		if (b&1) ans=1LL*ans*a%P;
		a=1LL*a*a%P;
		b>>=1;
	}
	return ans;
}
int rev[N],nv;
void NTT (int *a,int n,int kind)
{
	for (int i=0; i< n; i++)
		if (i< rev[i]) swap (a[i],a[rev[i]]);
	for (int i=1; i< n; i<<=1)
	{
		const int gn=ksm (YG,(P-1)/(i<<1));
		for (int j=0,sb=i<<1; j< n; j+=sb)
		{
			int g=1;
			for (int k=j; k< j+i; k++)
			{
				const int x=a[k],y=1LL*a[k+i]*g%P;
				a[k]=(x+y)%P;
				a[k+i]=(x-y+P)%P;
				g=1LL*g*gn%P;
			}
		}
	}
	if (kind==-1)
	{
		reverse (a+1,a+n);
		for (int i=0; i< n; i++)
			a[i]=1LL*a[i]*nv%P;
	}
}
int init (int n)
{
	int s=2,bit=1;
	while (s< (n<<1)) s<<=1,++bit;
	for (int i=0; i< s; i++)
		rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
	nv=ksm (s,P-2);
	return s;
}

$F^{-1}$

目标函数: $G$ ,下同.

$G\equiv F^{-1} \pmod {x^n}$ .

设 $H$ 为 $\pmod {x^{\lceil\frac{n}{2}\rceil}}$ 下的 $G$ ,下同. \((G-H)\equiv 0 \pmod {x^{\lceil\frac{n}{2}\rceil}}\)

\[(G-H)^2\equiv 0 \pmod {x^{n}}\] \[F(G^2-2GH+H^2) \equiv G-2H+FH^2 \equiv 0 \pmod {x^n}\] \[G \equiv (2-FH)H \pmod {x^n}\]

边界: $G[0]=inv (F[0])$ .

int f[N];
void getinv (int n,int *F,int *G)
{
	if (n==1) { G[0]=ksm (F[0],P-2); return ; }
	getinv ((n+1)>>1,F,G);
	int s=init (n);
	for (int i=0; i< n; i++)
		f[i]=F[i];
	for (int i=n; i< s; i++)
		f[i]=0;
	NTT (f,s,1),NTT (G,s,1);
	for (int i=0; i< s; i++)
		G[i]=(2LL-1LL*f[i]*G[i]%P+P)%P*G[i]%P;
	NTT (G,s,-1);
	for (int i=n; i< s; i++)
		G[i]=0;
}

$\ln F$

求导: 对 $f[g(x)]$ 求导得到 $f^{‘}(g(x))*g^{‘}(x)$ .
\(G \equiv \ln[F(x)] \equiv \int_{}{}\frac {F^{'}}{F} \text{d}x \pmod {x^n}\)

void qiudao (int n,int *F,int *G)
{
	for (int i=1; i< n; i++)
		G[i-1]=1LL*i*F[i]%P;
}
int inv[N];
void initinv (int n)
{
	inv[0]=inv[1]=1;
	for (int i=2; i<=n; i++)
		inv[i]=1LL*(P-P/i)*inv[P%i]%P;
}
void jifen (int n,int *F,int *G)
{
	G[0]=0;
	for (int i=0; i< n; i++)
		G[i+1]=1LL*F[i]*inv[i+1]%P;
}
int F_[N];
void getln (int n,int *F,int *G)
{
	initinv (n);
	getinv (n,F,G);
	qiudao (n,F,F_);
	
	int s=init (n);
	NTT (F_,s,1),NTT (G,s,1);
	for (int i=0; i< s; i++)
		F_[i]=1LL*G[i]*F_[i]%P;
	NTT (F_,s,-1);
	for (int i=n; i< s; i++)
		F_[i]=0;
	jifen (n,F_,G);
}

牛顿迭代

$F(G) \equiv 0 \pmod {x^{n}}$ .

泰勒展开: 在 $x_0$ 处展开: $f(x)=f(x_0)+\frac{f^{‘}(x_0)}{1!}(x-x_0)+\frac{f^{‘’}(x_0)}{2!}(x-x_0)^2+…$

将 $F(G)$ 在 $H$ 处展开:

\[F(G)=F(H)+F^{'}(H)(G-H)+\frac{F^{''}(H)}{2}(G-H)^2+...\]

$\because G与H的前\lceil \frac{n}{2} \rceil项相等$

$\therefore (G-H)^i\equiv 0 \pmod {x^n},i>=2$

\[\therefore F(G)\equiv F(H)+F^{'}(H)(G-H) \pmod{x^n}\] \[F(H)+F^{'}(H)(G-H) \equiv 0 \pmod{x^n}\] \[G\equiv H-\frac{F(H)}{F^{'}(H)}\pmod {x^n}\]

$\sqrt A$

$G^2\equiv A \pmod{x^n}$ .

牛顿迭代,设 $F(G)=G^2-A\pmod {x^n}$

当 $F(G)\equiv 0$

$G\equiv H-\frac{F(H)}{F^{‘}(H)} \equiv \frac{H+\frac {A}{H}}{2}\pmod {x^n}$

边界: $当A[0]=1,G[0]=1$ .

int f[N],H[N],inv2;
void getsqrt (int n,int *F,int *G)
{
    if (n==1) { G[0]=1; return ; }
    getsqrt ((n+1)>>1,F,G);
    int s=init (n);
    for (int i=0; i< s; i++)
        H[i]=0;
    getinv (n,G,H);
    for (int i=0; i< n; i++)
        f[i]=F[i];
    for (int i=n; i< s; i++)
        f[i]=0;
    NTT (f,s,1),NTT (G,s,1),NTT (H,s,1);
    for (int i=0; i< s; i++)
        G[i]=1LL*(G[i]+1LL*f[i]*H[i]%P)%P*inv2%P;
    NTT (G,s,-1);
    for (int i=n; i< s; i++)
        G[i]=0;
}

$e^A$

$G\equiv e^A\pmod{x^n}$ .

即 $\ln G-A\equiv 0 \pmod{x^n}$ .

类似 $\sqrt A$ 可得 $G\equiv H(1-\ln H+A)\pmod{x^n}$ .

(注意"1"为常数项)

int H[N];
void getexp (int n,int *A,int *G)
{
	if (n==1) { G[0]=1; return ; }
	getexp ((n+1)>>1,A,G);
	int s=init (n);
	for (int i=0; i< s; i++)
		H[i]=0;
	getln (n,G,H);
	for (int i=0; i< n; i++)
		H[i]=(-H[i]+A[i]+P)%P;
	(++H[0])%=P;
	for (int i=n; i< s; i++)
		H[i]=0;
	NTT (G,s,1),NTT (H,s,1);
	for (int i=0; i< s; i++)
		G[i]=1LL*G[i]*H[i]%P;
	NTT (G,s,-1);
	for (int i=n; i< s; i++)
		G[i]=0;
}

$F^k$

$\text{1.}$ 直接普通快速幂, $O(n\log n \log k)$ .

//已大力卡常...
B[0]=1;
NTT (A,1),NTT (B,1);
while (k)
{
    if (k&1)
    {
        for (int i=0; i< S; i++)
            B[i]=1LL*B[i]*A[i]%P;
        NTT (B,-1);
        for (int i=n; i< S; i++)
            B[i]=0;
        NTT (B,1);
    }
    if (k==1) break;
    for (int i=0; i< S; i++)
        A[i]=1LL*A[i]*A[i]%P;
    NTT (A,-1);
    for (int i=n; i< S; i++)
        A[i]=0;
    NTT (A,1);
    k>>=1;
}
NTT (B,-1);

$\text{2.}$ 先两边取 $\ln$ 后 $*k$ 再 $exp$ 回来.

int lnF[N];
void getksm (int n,int k,int *F,int *G)
{
	getln (n,F,lnF);
	for (int i=0; i< n; i++)
		lnF[i]=1LL*lnF[i]*k%P;
	getexp (n,lnF,G);
}

此法默认常数项为 $1$ .

否则需去除最低次项连续 $zero$ 个 $0$ ,并记录新多项式的常数项 $sb$ ,输出时给最低项加上 $zero*k$ 个 $0$ ,还要给每一项乘 $sb^k$ .

while (!F[zero]) ++zero;
for (int i=zero; i< n; i++)
    F[i-zero]=F[i];
for (int i=n-zero; i< n; i++)
    F[i]=0;
int w=zero;
if (1LL*w*k>=n) w=n;
else w*=k;
int sb=ksm (F[0],k);
getksm (n,k,F,G);
for (int i=0; i< w; i++)
    pr(0);
for (int i=0; i< n-w; i++)
    pr(1LL*G[i]*sb%P);

$FWT$

int mo(int x) { return (x>=P)?(x-P):x; }
void fwt (int *a,int n,int kind,char c)
{
    for (int i=1; i< n; i<<=1)
        for (int j=0,sb=i<<1; j< n; j+=sb)
            for (int k=j; k< j+i; k++)
            {
                int x=a[k],y=a[k+i];
                if (c=='o')
                    a[k+i]=(kind==1)?mo(y+x):mo(y-x+P);
                if (c=='a')
                    a[k]=(kind==1)?mo(x+y):mo(x-y+P);
                if (c=='x')
                {
                    a[k]=mo(x+y),a[k+i]=mo(x-y+P);
                    if (kind==-1) a[k]=(LL)a[k]*inv2%P,a[k+i]=(LL)a[k+i]*inv2%P;
                }
            }
}

子集卷积

用 $orFWT$ 实现.

int bi[1<<N];//二进制有多少个1
int f[N][1<<N],g[N][1<<N],h[N][1<<N];
int main()
{
	//freopen (".in","r",stdin);
	//freopen (".out","w",stdout);
	int n; sc(n); int s=1<<n;
	for (int i=1; i< s; i++)
		bi[i]=bi[i>>1]+(i&1);
	for (int i=0; i< s; i++)
		sc(f[bi[i]][i]);
	for (int i=0; i< s; i++)
		sc(g[bi[i]][i]);
	for (int i=0; i<=n; i++)
		fwt (f[i],s,1),fwt (g[i],s,1);
	for (int i=0; i<=n; i++)
		for (int j=0; j<=i; j++)
			for (int k=0; k< s; k++)
				h[i][k]=mo(h[i][k]+(LL)f[j][k]*g[i-j][k]%P);
	for (int i=0; i<=n; i++)
		fwt (h[i],s,-1);
	for (int i=0; i< s; i++)
		pr(h[bi[i]][i]);
	return 0;
}

有的是通过自己本身推过来的:

fwt (f[0],s,1);
for (int i=1; i<=n; i++)
{
    for (int j=0; j< i; j++)//不能等于
        for (int k=0; k< s; k++)
            f[i][s]=mo(f[i][s]+(LL)f[j][s]*g[i-j][s]%P);
    fwt (f[i],s,-1);
    //得到二进制位有i个1的答案
    fwt (f[i],s,1);
}
CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：多项式部分总结”
CATALOG
    FRIENDS