首页 > 其他分享 >多项式半家桶，但是未封装

多项式半家桶，但是未封装

时间：2023-01-09 19:44:48浏览次数：43  
标签：封装 pmod 多项式 ll 半家桶 int 2m equiv

多项式乘法逆

题意：

给定 \(n-1\) 次多项式 \(F(x)\) ，求多项式 \(G(x)\)，使得 \(F(x) G(x) \equiv 1 \pmod {x^n}\)

思路：

设 :

\[F(x) g(x) \equiv 1 \pmod {x^m} \\ \ \\ F(x) G(x) \equiv 1 \pmod {x^{2m}} \]

已知 \(g(x)\) ，考虑如何求解 \(G(x)\) 。

因为：

\[F(x) G(x) \equiv 1\pmod {x^{2m}} \]

因此有：

\[F(x) G(x) \equiv 1 \pmod {x^{m}} \]

两者相减，于是有：

\[F(x)(G(x)-g(x)) \equiv 0 \pmod {x^{m}} \\ \ \\ G(x)-g(x) \equiv 0 \pmod {x^{m}} \]

再平方（注意此时模数变为了原来的二倍）：

\[(G(x)-g(x) )^2\equiv 0 \pmod {x^{2m}} \\ \ \\ G(x)^2-2G(x) g(x)+g(x)^2\equiv 0 \pmod {x^{2m}} \]

左右两边同乘 \(F(x)\) ：

\[F(x)G(x)^2-2F(x)G(x) g(x)+F(x)g(x)^2\equiv 0 \pmod {x^{2m}} \\ \ \\ G(x)-2 g(x)+F(x)g(x)^2\equiv 0 \pmod {x^{2m}} \\ \ \\ G(x) \equiv 2 g(x)-F(x)g(x)^2 \pmod {x^{2m}} \\ \ \\ G(x) \equiv g(x)(2-F(x)g(x)) \pmod {x^{2m}} \\ \]

将 \(g_0\) 要初始化成 \(F_0\) 的乘法逆元，递推或者递归求解 \(G(x)\) 。

注意事项：

  1. 边界问题，即 \(F(x)\) 应该取到 \(2m-1\) 次方， \(g(x)\) 应该取到 \(m-1\) 次方，求得的 \(G(x)\) 应该取到 \(2m-1\) 次方（超出的设为 \(0\)） ，进行多项式乘法时至少要使长度 \(lim > 4m\)

  2. 递归求解时要先求 \(\bmod \lceil \frac{n}{2}\rceil\) 意义下的 \(g(x)\) ，再求 \(\bmod n\) 意义下的 \(G(x)\)


多项式开根

题意：

给定 \(n-1\) 次多项式 \(F(x)\) ，求多项式 \(G(x)\)，使得 \(G(x)^2 \equiv F(x) \pmod {x^n}\) 。

保证 \(F_0=1\) 。

思路：

延续着多项式求逆倍增的思路，我们依然设：

\[g(x) ^2\equiv F(x) \pmod {x^m} \\ \ \\ G(x) ^2\equiv F(x) \pmod {x^{2m}} \]

已知 \(g(x)\) ，考虑如何求解 \(G(x)\) 。

因为：

\[ G(x)^2 \equiv F(x)\pmod {x^{2m}} \]

因此有：

\[ G(x)^2 \equiv F(x) \pmod {x^{m}} \\ \ \\ G(x) \equiv g(x) \pmod {x^{m}} \\ \ \\ G(x)-g(x) \equiv 0 \pmod {x^{m}} \]

两边平方：

\[ (G(x)-g(x))^2 \equiv 0 \pmod {x^{2m}} \\ \ \\ G(x)^2-2G(x)g(x)+g(x)^2 \equiv 0 \pmod {x^{2m}} \]

用 \(F(x)\) 替换 \(G(x)^2\) ：

\[ F(x)-2G(x)g(x)+g(x)^2 \equiv 0 \pmod {x^{2m}} \\ \ \\ 2G(x)g(x) \equiv F(x)+g(x)^2 \pmod {x^{2m}} \\ \ \\ G(x) \equiv \frac{F(x)+g(x)^2}{2g(x)} \pmod {x^{2m}} \]

初始化 \(g_0=1\)，递推或递归求解 \(G(x)\) 。

注意事项跟多项式求逆差不多。

但如果不封装的话，注意求逆时数组混用的问题。

当 \(F_0 \ne 1\) 时，需要求解 \(F_0\) 在 \(\bmod p\) 意义下的二次剩余作为初始值。


多项式求导

给定 \(n-1\) 次多项式 \(F(x)\) ，求 \(F'(x) \pmod {x^n}\) 。

因为

\[(x^n)'=nx^{n-1} \]

所以 ：

\[ F'(x)=\sum_{i=0}^{n-2} (i+1) F_{i+1} x^i \]

code 
inline void Diff(ll *a,int len){
    for(Reg int i=0;i<len-1;++i) a[i]=a[i+1]*(i+1)%mod; 
    a[len-1]=0;
}

多项式积分

给定 \(n-1\) 次多项式 \(F(x)\) ，求 \(F(x)\) 的不定积分 \(G(x)\) 。

因为：

\[\int x_a dx= \frac{1}{a+1} x^{a+1} \]

所以

\[G(x)=\sum_{i=1}^{n-1} \frac{ G_{i-1} } {i} x^i \]

code 
inline void Inte(ll *a,int len){
    for(Reg int i=len-1;i>0;--i) a[i]=a[i-1]*qpow(i,mod-2)%mod; 
    a[0]=0;
}

多项式对数函数 (ln)

题意：

给定 \(n-1\) 次多项式 \(F(x)\) ，求多项式 \(G(x)\)，使得 \(G(x) \equiv \ln {F(x)} \pmod {x^n}\) 。

保证 \(F_0=1\) 。

思路：

考虑同时对两边求导，有：

\[G'(x) \equiv \frac{F'(x)}{F(x)} \pmod {x^n} \]

再同时对两边做不定积分：

\[\int G'(x) \equiv \int \frac{F'(x)}{F(x)} \pmod {x^n} \\ \ \\ G(x) \equiv \int \frac{F'(x)}{F(x)} \pmod {x^n} \]

对 \(F(x)\) 求导和求乘法逆，相乘再积分即可求得 \(G(x)\) 。


多项式指数函数 (exp)

题意：

给定 \(n-1\) 次多项式 \(F(x)\) ，求多项式 \(G(x)\)，使得 \(G(x) \equiv e^{F(x)} \pmod {x^n}\) 。

保证 \(F_0=0\) 。

思路：

不会牛顿迭代，麻。

对两边求导：

\[G'(x) \equiv F'(x)e^{F(x)} \pmod {x^n} \]

用 \(G(x)\) 将 \(e^{F(x)}\) 替换：

\[G'(x) \equiv F'(x)G(x) \pmod {x^n} \]

对两边做不定积分：

\[\int G'(x) \equiv \int F'(x)G(x) \pmod {x^n} \\ \ \\ G(x) \equiv \int F'(x)G(x) \pmod {x^n} \]

设 \(T(x)=F'(x)G(x)\) ，那么对于 \(G(x)\) 的第 \(i\) 项系数 \(G_i\) 有：

\[G_i=\frac{ T_{i-1}}{i} \]

也就是：

\[G_i=\frac{ \sum_{j=0}^{i-1} F_j G_{i-1-j}}{i} \]

然后就可以半在线卷积了，复杂度 \(O(n\log ^2 n)\) 。

留坑待补。


多项式快速幂

题意：

给定 \(n-1\) 次多项式 \(F(x)\) 与整数 \(k\) 。求多项式 \(G(x)\)，使得 \(G(x) \equiv \ {F(x)}^k \pmod {x^n}\) 。

其中 $ 0\le k\le 10^{100000}, F_0=1 $

思路：

首先想的应该是对指数取模，直接模 \(mod\) 即可。

这时好像可以写倍增，但可以有复杂度更优的做法，考虑转化题意。

对两边取自然对数：

\[\ln G(x) \equiv \ln F(x)^k \pmod {x^n} \\ \ \\ \ln G(x) \equiv k\ln F(x) \pmod {x^n} \\ \]

然后再取指数：

\[G(x) \equiv e^{k\ln F(x)} \pmod {x^n} \]

于是一次 \(\ln\) 一次 \(\exp\) 就做完了。

当 $F_0=1 $ 时, $ \ln F_0=0$ ，所以 \(\exp\) 时 $G_0 $ 应该设为 \(1\) 。

当 \(F_0\ne 1\) 时的 \(G_0\) 应为 $F_0^k \bmod mod $ ，特别注意 \(F_0=0\) 时没有 \(\ln F_0\) （不存在），因此要找到一个系数为 \(0\) 的前缀长度 \(len\) ，乘上 \(k\) 即为 \(G(x)\) 前缀 为 \(0\) 的长度。




代码

code 
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define Reg register
#define ll long long
using namespace std;
const int maxn=411000;
const int G=3,mod=998244353;
int n,p,R[maxn];
ll A[maxn],B[maxn],C[maxn],D[maxn],E[maxn];
ll f[maxn],g[maxn];
inline ll read(int typ){
    ll s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        if(typ) s=(s*10%mod+(ch^48))%mod;
        else s=(s<<1)+(s<<3)+(ch^48);
        ch=getchar();
    }
    return s*w;
}
inline ll qpow(ll A,ll B){
    ll Ans=1;
    while(B){
        if(B&1) Ans=Ans*A%mod;
        A=A*A%mod;
        B>>=1;
    }
    return Ans;
}
inline ll upd(ll A,ll B){
    A+=B;
    return A>=mod?A-mod:A;
}
inline ll dow(ll A,ll B){
    A-=B;
    return A<0?A+mod:A;
}
inline void Getr(int len,int L){
    for(Reg int i=0;i<len;++i) R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
}
inline void NTT(ll *a,int lim,ll typ){
    for(Reg int i=0;i<lim;++i){
        if(i<R[i]) swap(a[i],a[R[i]]);
    } 
    for(Reg int j=1,p=2;j<lim;j<<=1,p<<=1){
        ll t=qpow(G,(typ*((mod-1)/p)+mod-1)%(mod-1));
        for(Reg int k=0;k<lim;k+=p){
            ll T=1;
            for(Reg int l=0;l<j;++l,T=T*t%mod){
                ll Nx=a[k+l],Ny=T*a[k+l+j]%mod;
                a[k+l]=upd(Nx,Ny);
                a[k+l+j]=dow(Nx,Ny);
            }
        }
    }
    if(typ==-1){
        ll r=qpow(lim,mod-2);
        for(Reg int i=0;i<lim;++i) a[i]=a[i]*r%mod;
    }
}
inline void Diff(ll *a,int len){
    for(Reg int i=0;i<n-1;++i) a[i]=a[i+1]*(i+1)%mod; 
    a[len-1]=0;
}
inline void Inte(ll *a,int len){
    for(Reg int i=n-1;i>0;--i) a[i]=a[i-1]*qpow(i,mod-2)%mod; 
    a[0]=0;
}
inline void Getinv(ll *a,ll *b,int len){
    b[0]=qpow(a[0],mod-2),void();
    int lim=1,L=0,lstlim=0;
    while(lim<2*len){
        lstlim=lim;
        lim<<=1,++L,Getr(lim,L);
        memset(D,0,sizeof(ll)*(lim+10));
        memset(E,0,sizeof(ll)*(lim+10));
        for(Reg int i=0;i<lstlim;++i) D[i]=a[i],E[i]=b[i];
        NTT(D,lim,1),NTT(E,lim,1);
        for(Reg int i=0;i<lim;++i) D[i]=(2-D[i]*E[i]%mod+mod)%mod*E[i]%mod;
        NTT(D,lim,-1);
        for(Reg int i=0;i<lstlim;++i) b[i]=D[i];
    }
}
inline void Getsqrt(ll *a,ll *b,int len){
    b[0]=1;
    int lim=1,L=0,lstlim=0;
    while(lim<2*len){
        lstlim=lim;
        lim<<=1,++L,Getr(lim,L);
        memset(A,0,sizeof(ll)*(lim+10));
        memset(B,0,sizeof(ll)*(lim+10));
        memset(C,0,sizeof(ll)*(lim+10));
        for(Reg int i=0;i<lstlim;++i) A[i]=a[i],B[i]=b[i];
        NTT(A,lim,1),NTT(B,lim,1);
        for(Reg int i=0;i<lstlim;++i) b[i]=2*b[i]%mod;
        Getinv(b,C,lstlim);
        NTT(C,lim,1);
        for(Reg int i=0;i<lim;++i) A[i]=(A[i]+B[i]*B[i]%mod+mod)%mod*C[i]%mod;
        NTT(A,lim,-1);
        for(Reg int i=0;i<lstlim;++i) b[i]=A[i];
    }
}
inline void Ln(ll *a,ll *b,int len){
    Getinv(a,C,len),Diff(a,len);
    int lim=1,L=0;
    while(lim<=2*len) lim<<=1,++L;Getr(lim,L);
    NTT(a,lim,1),NTT(C,lim,1);
    for(Reg int i=0;i<lim;++i) a[i]=a[i]*C[i]%mod;
    NTT(a,lim,-1);
    for(Reg int i=0;i<len;++i) b[i]=a[i];
    Inte(b,len);
}
inline void calc(ll *a,ll *b,int lim){
    NTT(a,lim,1),NTT(b,lim,1);
    for(Reg int i=0;i<lim;++i)  a[i]=a[i]*b[i]%mod;
    NTT(a,lim,-1);
}
inline void Solve(ll *a,ll *b,int l,int r){
    if(l==r){
         //printf("%lld\n",f[l]);
        if(l) a[l]=a[l]*qpow(l,mod-2)%mod;
        else a[l]=1;
        return;
    }
    int mid=(l+r)>>1;
    Solve(a,b,l,mid);
    int up=r-l+1,lim=1,L=0;
    while(lim<=2*up) lim<<=1,++L;Getr(lim,L);
    memset(A,0,sizeof(ll)*(lim+10));
    memset(B,0,sizeof(ll)*(lim+10));
    for(Reg int i=0;i<mid-l+1;++i) A[i]=a[i+l];
    for(Reg int i=1;i<=r-l;++i) B[i]=b[i-1];
    calc(A,B,lim);
    for(Reg int i=mid-l+1;i<=r-l;++i) a[i+l]=(a[i+l]+A[i])%mod;
    Solve(a,b,mid+1,r);
} 
inline void Exp(ll *a,ll *b,int len){
    Diff(a,len);
    Solve(b,a,0,len-1);
}
inline void Polyqpow(ll *a,ll *b,ll p,int len){
    Ln(a,a,len);
    for(Reg int i=0;i<len;++i) a[i]=a[i]*p%mod;
    Exp(a,b,len);
}
int main(){
    n=read(0);//p=read(1);
    for(Reg int i=0;i<n;++i) f[i]=read(0);
    //Getinv(f,g,n),Getsqrt(f,g,n),Ln(f,g,n),Exp(f,g,n),Polyqpow(f,g,p,n);
    for(Reg int i=0;i<n;++i) printf("%lld ",g[i]);
    printf("\n");
    return 0;
}

标签：封装,pmod,多项式,ll,半家桶,int,2m,equiv
From： https://www.cnblogs.com/Broken-Eclipse/p/17035941.html

相关文章

  • ACM&OI 多项式算法专题
    ACM&OI基础数学算法专题一、FFT基础拉格朗日插值复数的运算性质和几何性质单位根和单位根反演快速傅里叶变换（FFT）的分治实现快速傅里叶逆变换（IFFT）快速傅里叶变换的......
  • vue2 element-ui组件二封-表单组件-按钮封装
    这里是一段我们公司过往项目的代码(增删改查项目中的查询/重置按钮)<el-button@click="query()"type="primary"size="mini"><iclass="el-icon-search">查询</i><......
  • 学习笔记：多项式半家桶
    已经吃撑了多项式求逆对于多项式\(A(x)\)，求多项式\(B(x)\)，满足\(A(x)*B(x)\equiv1\pmod{x^n}\)。递归求解。求模\(x^n\)的逆元时，假设先求出了模\(x^{\l......
  • 封装，继承和多态
    1.封装：属性私有，get/set 记住快捷键alt+insert2,继承 extends继承是类和类之间的关系，除此之外，类和类之间的关系还有依赖，组合，聚合等继承关系的两个类，子类（派生类）---父......
  • 多项式乘法（FTT、NTT），但主要是习题
    诈尸。摆了一个多月没写boke的BE是屑。基础知识/模板因为太屑了所以就直接放巨佬们的博客力。快速傅立叶变换[学习笔记&教程]信号,集合,多项式,以及各种......
  • 学习笔记：多项式变换
    多项式学习笔记卷积形式：一般卷积形式\[F_i=\sum_{j\circk=i}a_jb_k\]当\(\circ\)为\(+\)是为常见的多项式加法卷积，\(\times\)有时也能转为加法，位运算是FWT,整除是狄......
  • 封装
    1.我们程序设计追求“高内聚，低耦合”。高内聚就是类的内部数据操作细节自己完成，不允许外部干涉；低耦合：仅暴露少量的方法给外部使用。2.封装（数据的隐藏）通常，应禁止直接......
  • cocos creator教程：框架 - 封装
    【muzzik教程】：框架-封装遇到的问题部分接口/属性不想暴露给外部外部引用方式框架加载方式部分接口/属性不想暴露给外部exportclassprivate_test{ test_b=......
  • spring boot——Mybatis中的多表查询之用户与账户（一对多和一对一/多对一）---结果集封装
    Mybatis中的多表查询之用户与账户（一对多和一对一/多对一）---结果集封装到对象---立即加载与延迟加载Mybatis表之间关系有三种：1、 一对一：人和身份证号是一对一2、 一......
  • 重学多项式
    重学多项式目录重学多项式更好的阅读体验戳此进入写在前面关于这篇Blog单位根定义复数意义下的的求法性质等比数列求和公式FFT本质目的离散傅里叶变换快速傅里叶变换优化C......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99