精华内容
下载资源
问答
  • 多项式逆元模板

    千次阅读 2018-01-15 22:54:50
    多项式逆元具体概念及求法可见这里,本文主要提供模板。 本文提供的是模998244353下保留0~nn次项,即mod(xn+1)mod(x^{n+1})意义下的模板。 #include #define ll long long using namespace std; int getint() {...

    多项式求逆元具体概念及求法可见这里,本文主要提供模板。

    本文提供的是模998244353下保留0~ n 次项,即mod(xn+1)意义下的模板。

    #include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    
    int getint()
    {
        int i=0,f=1;char c;
        for(c=getchar();c!='-'&&(c<'0'||c>'9');c=getchar());
        if(c=='-')f=-1,c=getchar();
        for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';
        return i*f;
    }
    
    const int N=500005,p=998244353,g=3;
    int n,a[N],b[N],pos[N],w[N],inv[N];
    
    int Pow(int x,int y)
    {
        int res=1;
        for(;y;y>>=1,x=(ll)x*x%p)
            if(y&1)res=(ll)res*x%p;
        return res;
    }
    
    void Init()
    {
        int len=1,num=0;
        while(len<((n+1)<<1))
        {
            len<<=1;
            w[++num]=Pow(g,(p-1)/len);
            inv[num]=Pow(w[num],p-2);
        }
    }
    
    void NTT(int f[],int len,int on)
    {
        for(int i=1;i<len;i++)
            pos[i]=(i&1)?pos[i>>1]>>1|(len>>1):pos[i>>1]>>1;
        for(int i=1;i<len;i++)
            if(i<pos[i])swap(f[i],f[pos[i]]);
        for(int i=1,num=1;i<len;i<<=1,num++)
        {
            int wn=(on==1?w[num]:inv[num]);
            for(int j=0;j<len;j+=(i<<1))
            {
                int wi=1;
                for(int k=j;k<j+i;k++)
                {
                    int u=f[k],v=(ll)wi*f[k+i]%p;
                    f[k]=(u+v)%p,f[k+i]=(u-v+p)%p;
                    wi=(ll)wi*wn%p;
                }
            }
        }
        if(on==-1)
            for(int i=0;i<len;i++)
                f[i]=(ll)f[i]*Pow(len,p-2)%p;
    }
    
    void Poly_inv(int a[],int b[],int deg)
    {
        if(deg==1)
        {
            b[0]=Pow(a[0],p-2);
            return;
        }
        Poly_inv(a,b,(deg+1)>>1);
        static int tmp[N];
        int len=1;
        while(len<(deg<<1))len<<=1;
        for(int i=0;i<deg;i++)tmp[i]=a[i];
        for(int i=deg;i<len;i++)tmp[i]=0;
        for(int i=(deg+1)>>1;i<len;i++)b[i]=0;
        NTT(tmp,len,1),NTT(b,len,1);
        for(int i=0;i<len;i++)b[i]=(ll)b[i]*((2-(ll)tmp[i]*b[i]%p+p)%p)%p;
        NTT(b,len,-1);
    }
    
    int main()
    {
        //freopen("lx.in","r",stdin);
        n=getint();
        Init();
        for(int i=0;i<=n;i++)a[i]=getint();
        Poly_inv(a,b,n+1);
        for(int i=0;i<=n;i++)cout<<b[i]<<' ';
        return 0;
    }
    展开全文
  • 多项式逆元是一个非常重要的知识点,许多多项式操作都需要用到该算法,包括多项式取模,除法,开跟,求ln,求exp,快速幂。用快速傅里叶变换和倍增法可以在$O(n log n)$的时间复杂度下求出一个$n$次多项式逆元。...

    概述

    多项式求逆元是一个非常重要的知识点,许多多项式操作都需要用到该算法,包括多项式取模,除法,开跟,求ln,求exp,快速幂。用快速傅里叶变换和倍增法可以在$O(n log n)$的时间复杂度下求出一个$n$次多项式的逆元。

     

    前置技能

    快速数论变换(NTT),求一个数$x$在模$p$意义下的乘法逆元。

     

    多项式的逆元

    给定一个多项式$A(x)$,其次数为$deg_A$,若存在一个多项式$B(x)$,使其满足$deg_B≤deg_A$,且$A(x)\times B(x) \equiv 1 (mod\ x^n)$,则$B(x)$即为$A(x)$在模$x^n$意义下的的乘法逆元。

     

    求多项式的逆元

    我们不妨假设,$n=2^k,k∈N$。

    若$n=1$,则$A(x)\times B(x) \equiv a_0\times b_0 \equiv 1 (mod\ x^1)$。其中$a_0$,$b_0$表示多项式$A$和多项式$B$的常数项。

    若需要求出$b_0$,直接用费马小定理求出$a_0$的乘法逆元即可。

    当$n>1$时:

    我们假设在模$x^{\frac{n}{2}}$的意义下$A(x)$的逆元$B'(x)$我们已经求得。

    依据定义,则有

    $A(x)B'(x)\equiv 1 (mod\ x^{\frac{n}{2}})$          $(1)$

    对$(1)$式进行移项得

    $A(x)B'(x)-1\equiv 0 (mod\ x^{\frac{n}{2}})$          $(2)$

    然后对$(2)$式等号两边平方,得

    $A^2(x)B'^2(x)-2A(x)B'(x)+1\equiv 0(mod\ x^{n})$          $(3)$

    将常数项移动到等式右侧,得

    $A^2(x)B'^2(x)-2A(x)B'(x)\equiv -1(mod\ x^{n})$          $(4)$

    将等式两边去相反数,得

    $2A(x)B'(x)-A^2(x)B'^2(x)\equiv 1(mod\ x^{n})$          $(5)$

    下面考虑回我们需要求的多项式$B(x)$,依据定义,其满足

    $A(x)B(x)\equiv 1(mod\ x^{n})          $(6)$

    将$(5)-(6)$并移项,得

    $A(x)B(x)\equiv 2A(x)B'(x)-A^2(x)B'^2(x)(mod\ x^{n})$          $(7)$

    等式两边约去$A(x)$,得

    $B(x)\equiv 2B'(x)-A(x)B'^2(x)(mod\ x^{n})$          $(8)$

     

     

    显然,我们可以用上述式子求出$B(x)$。

    这一步的计算我们可以使用$NTT$,时间复杂度为$O(n log n)$。

    我们可以通过递归的方法,求解出$B(x)$。

    时间复杂度$T(n)=T(\dfrac{n}{2})+O(n log n)=O(n log n)$。

     

    洛谷上有一道题目就叫做多项式求逆元(点这里),可以先做下那一题。

    模板如下:

     

     1 #include<bits/stdc++.h>
     2 #define M (1<<19)
     3 #define L long long
     4 #define MOD 998244353
     5 #define G 3
     6 using namespace std;
     7 
     8 L pow_mod(L x,L k){
     9     L ans=1;
    10     while(k){
    11         if(k&1) ans=ans*x%MOD;
    12         x=x*x%MOD; k>>=1;
    13     }
    14     return ans;
    15 }
    16 
    17 void change(L a[],int n){
    18     for(int i=0,j=0;i<n-1;i++){
    19         if(i<j) swap(a[i],a[j]);
    20         int k=n>>1;
    21         while(j>=k) j-=k,k>>=1;
    22         j+=k;
    23     }
    24 }
    25 void NTT(L a[],int n,int on){
    26     change(a,n);
    27     for(int h=2;h<=n;h<<=1){
    28         L wn=pow_mod(G,(MOD-1)/h);
    29         for(int j=0;j<n;j+=h){
    30             L w=1;
    31             for(int k=j;k<j+(h>>1);k++){
    32                 L u=a[k],t=w*a[k+(h>>1)]%MOD;
    33                 a[k]=(u+t)%MOD;
    34                 a[k+(h>>1)]=(u-t+MOD)%MOD;
    35                 w=w*wn%MOD;
    36             }
    37         }
    38     }
    39     if(on==-1){
    40         L inv=pow_mod(n,MOD-2);
    41         for(int i=0;i<n;i++) a[i]=a[i]*inv%MOD;
    42         reverse(a+1,a+n);
    43     }
    44 }
    45 
    46 void getinv(L a[],L b[],int n){
    47     if(n==1){b[0]=pow_mod(a[0],MOD-2); return;}
    48     static L c[M],d[M];
    49     memset(c,0,n<<4); memset(d,0,n<<4);
    50     getinv(a,c,n>>1);
    51     for(int i=0;i<n;i++) d[i]=a[i];
    52     NTT(d,n<<1,1); NTT(c,n<<1,1);
    53     for(int i=0;i<(n<<1);i++) b[i]=(2*c[i]-d[i]*c[i]%MOD*c[i]%MOD+MOD)%MOD;
    54     NTT(b,n<<1,-1);
    55     for(int i=0;i<n;i++) b[n+i]=0;
    56 }
    57 L a[M]={0},b[M]={0};
    58 int main(){
    59     int n,N; scanf("%d",&n);
    60     for(int i=0;i<=n;i++) scanf("%lld",a+i);
    61     for(N=1;N<=n;N<<=1);
    62     getinv(a,b,N);
    63     for(int i=0;i<=n;i++) printf("%lld ",b[i]);
    64 }

     

    转载于:https://www.cnblogs.com/xiefengze1/p/9107752.html

    展开全文
  • 多项式逆元

    千次阅读 2017-11-07 17:21:25
    Contents [hide] 1 概述2 基本概念3 多项式的...多项式逆元多项式除法和多项式取模的必要过程,在竞赛中,有时候多项式逆元的应用比多项式的除法还要多,用快速傅里叶变换以及倍增算法可以做到在 O(nlogn
     
    

    概述

    多项式求逆元是多项式除法和多项式取模的必要过程,在竞赛中,有时候多项式求逆元的应用比多项式的除法还要多,用快速傅里叶变换以及倍增算法可以做到在  O(nlogn) O(nlog⁡n) 的时间内求出一个多项式的逆元

    基本概念

    在介绍多项式的逆元之前,先说明一些概念:多项式的度、多项式的逆元、多项式的除法和取余

    对于一个多项式  A(x) A(x),称其最高项的次数为这个多项式的(degree),记作  degA degA

    对于多项式  A(x),B(x) A(x),B(x),存在唯一的  Q(x),R(x) Q(x),R(x) 满足  A(x)=Q(x)B(x)+R(x) A(x)=Q(x)B(x)+R(x),其中  degR<degB degR<degB,我们称  Q(x) Q(x) 为  B(x) B(x) 除  A(x) A(x) 的 R(x) R(x) 为  B(x) B(x) 除  A(x) A(x) 的余数,可以记作

    A(x)R(x)(modB(x)) A(x)≡R(x)(modB(x))

    多项式的逆元

    对于一个多项式  A(x) A(x),如果存在  B(x) B(x) 满足  degBdegA degB≤degA 并且

    A(x)B(x)1(modxn) A(x)B(x)≡1(modxn)

    那么称  B(x) B(x) 为  A(x) A(x) 在  modxn modxn 意义下的逆元(inverse element),记作  A1(x) A−1(x)

    求解过程

    现在考虑如何求  A1(x) A−1(x),当  n=1 n=1 时, A(x)c(modx) A(x)≡c(modx) c c 是一个常数,这样, A1(x) A−1(x) 就是  c1 c−1

    对于  n>1 n>1 的情况,设  B(x)=A1(x) B(x)=A−1(x) 由定义可以知道

    A(x)B(x)1(modxn)(1) (1)A(x)B(x)≡1(modxn)

    假设在  modxn2 modx⌈n2⌉ 意义下  A(x) A(x) 的逆元是  B(x) B′(x) 并且我们已经求出,那么

    A(x)B(x)1(modxn2)(2) (2)A(x)B′(x)≡1(modx⌈n2⌉)

    再将  (1) (1) 放到  modxn2 modx⌈n2⌉ 意义下

    A(x)B(x)1(modxn2)(3) (3)A(x)B(x)≡1(modx⌈n2⌉)

    然后  (2)(3) (2)−(3) 就可以得到

    B(x)B(x)0(modxn2) B(x)−B′(x)≡0(modx⌈n2⌉)

    两边平方

    B2(x)2B(x)B(x)+B2(x)0(modxn) B2(x)−2B′(x)B(x)+B′2(x)≡0(modxn)

    这里解释一下平方后为什么模的  xn2 x⌈n2⌉ 也会平方,这是因为,左边多项式在  modxn modxn 意义下为  0 0,那么就说明其  0 0 到  n1 n−1 次项系数都为  0 0,平方了之后,对于第  0i2n1 0≤i≤2n−1 项,其系数  ai ai 为  ij=0ajaij ∑j=0iajai−j,很明显  j j 和  ij i−j 之间必然有一个值小于  n n,因此  ai ai 必然是  0 0,也就是说平方后在  modx2n modx2n 意义下仍然为  0 0

    然后同时乘上  A(x) A(x),移项可以得到

    B(x)2B(x)A(x)B2(x)(modxn) B(x)≡2B′(x)−A(x)B′2(x)(modxn)

    这样就可以得到  modxn modxn 意义下的逆元了,利用 FFT 加速之后可以做到在  O(nlogn) O(nlog⁡n) 时间内解决当前问题,最后总的时间复杂度也就是

    T(n)=T(n2)+O(nlogn)=O(nlogn) T(n)=T(n2)+O(nlog⁡n)=O(nlog⁡n)

    顺便一提,由这个过程可以看出,一个多项式有没有逆元完全取决于其常数项是否有逆元

    代码实现

    假设我已经有了计算快速傅里叶变换的函数 transform(int deg, complex_t* x, complex_t*w) 以及单位根表 eps 和 inv_eps

    下面是数论版的,并且是完整的代码实现

     应用

    预处理 Bernoulli 数

    Bernoulli 数的指数生成函数(EGF)是

    xex1=i=0Bixii! xex−1=∑i=0∞Bixii!

    将  ex ex 泰勒展开就可以改写成

    xex1=1i=0xi(i+1)! xex−1=1∑i=0∞xi(i+1)!

    然后利用刚刚所说的方法,求出这个多项式的逆元就可以得到 Bernoulli 数了

    计算有标号简单连通无向图个数

    这篇文章,在列出方程后最后可以用多项式求逆优化

    展开全文
  • 目录 一、多项式逆元 二、多项式ln 三、关于牛顿迭代式 1.泰勒(Taylor)展开式 2.牛顿迭代 四、多项式exp 五、多项式快速幂 1.指数较小时 2.指数较大时

    初见安~被多项式毒瘤了这么久终于想起来整理了……QAQ

    目录

    一、多项式逆元

    二、多项式ln

    三、关于牛顿迭代式

    1.泰勒(Taylor)展开式

    2.牛顿迭代

    四、多项式exp

    五、多项式快速幂

    1.指数较小时

    2.指数较大时


    一、多项式逆元

    已知多项式A(x),求\small F(x)满足:

    \small F(x)A(x)\equiv 1(mod~x^n)

    \small mod~x^n的意思是:满足相乘后的多项式前n项除了常数项系数为1其余均为0】

    我们假设已知:(n/2向上取整,下同

    \small F_0(x)A(x)\equiv 1(mod~x^{\frac{n}{2}})

    那么由上文定义可得必有:

    \small F(x)A(x)\equiv 1(mod ~x^{\frac{n}{2}})

    所以两式相减:

    \small F(x)-F_0(x)\equiv0(mod~x^{\frac{n}{2}})

    两边同时平方:

    \small F^2(x)-2F(x)F_0(x)+F_0^2(x)\equiv 0(mod~x^n)
    这里似乎需要解释一下为什么模数也平方了:因为对于前n/2个都是0不用多说,而对于后面的n/2个,比如\small i \in [n/2,n),必有\small a_i=\sum a_ja_{i-j},这两项中必有一项是在n/2里为0,所以成立。

    所以两边再同时根据最开头的两式乘上一个A(x)

    \small F(x) \equiv 2F_0(x)-F_0^2(x)A(x)(mod~x^n)

    接下来递归求解即可。

    代码:

    void get_inv(ll *a, ll *b, int n) {//求a的逆元放进b里
        if(n == 1) {b[0] = pw(a[0], mod - 2); return;}//边界
        get_inv(a, b, (n + 1) >> 1);//这里的n是元素个数,在这种写法下最好上取整
    	len = 1, l = 0;//因为len变化了,每次都要重新处理
    	while(len <= n + n) len <<= 1, l++;
    	for(int i = 1; i <= len; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << l - 1);
    	
    	for(int i = 0; i < n; i++) tmp[i] = a[i];//放进tmp里保证a不改变
    	for(int i = n; i <= len; i++) tmp[i] = 0;//一定要为0
    	
    	NTT(tmp, 1), NTT(b, 1);
    	for(int i = 0; i <= len; i++) b[i] = b[i] * (1ll * 2 - tmp[i] * b[i] % mod + mod) % mod;
    	NTT(b, -1); for(int i = n; i <= len; i++) b[i] = 0;//这里也要记得清0,据定义只有前n项有效
    }

     

    二、多项式ln

    已知多项式A(x),求\small \dpi{120} \small B(x)满足:

    \small B(x)\equiv ln{A(x)}(mod~x^n)

    明显我们直接看这个ln就特别的不友好。有什么转化的方法呢——导数

    导数有基本公式:\small ln'x=\frac{1}{x},若是复合函数整体求导的话外面再乘一个内层函数的导数即可。

    所以我们对这个式子两边同时求导可得:

    \small (lnA(x))'=\frac{A'(x)}{A(x)}

    所以我们要求的东西就转化为了:

    \small \int\frac{A'(x)}{A(x)}

    上面求导,下面求逆元,整体求积分,复杂度为\small O(nlogn)

    对于我这样的蒟蒻,其实第一眼的疑惑不是怎么求,而是:求导和积分怎么整啊【大雾】

    下面简单讲一下这个东西【会者自略】
    求导积分的定义建议去翻百度百科【我也是这么过来的……惨。
    根据求导公式:\small (x^v)'=vx^{v-1}我们将一个多项式求导过后,会少一项。也就是说:对于\small f[v],求导后应为\small f[v+1]*(v+1)
    【第一次看可能会有点混乱, 可以手动把这个多项式写下来,再对应求导后的结果来理解。】
    同样的,在这个递推式的基础上求积分,就是导数的逆变换,乘v+1的逆元即可。

    下面上代码——

    void deriv(ll *a, int n) {for(int i = 1; i < n; i++) a[i - 1] = i * a[i] % mod; a[n - 1] = 0;}
    void integ(ll *a, int n) {for(int i = n - 1; i > 0; i--) a[i] = a[i - 1] * pw(i, mod - 2) % mod; a[0] = 0;}
    
    void get_ln(ll *a, ll *b, int n) {
    	get_inv(a, b, n);//首先要求一次逆元,放到b里面
    	for(int i = 0; i < n; i++) tmp[i] = a[i];//放到tmp是为了应付多次调用ln的情况,尽量不改变a数组
    	for(int i = n; i <= len; i++) tmp[i] = 0;
    	deriv(tmp, n);//求导
    	NTT(tmp, 1), NTT(b, 1);
    	for(int i = 0; i <= len; i++) b[i] = b[i] * tmp[i] % mod;
    	NTT(b, -1); integ(b, n);//积分回来
    }

     

    三、关于牛顿迭代式

    1.泰勒(Taylor)展开式

    不要问我为什么要讲这些东西。百度百科的时候被一群公式原理套娃我也很绝望啊

    泰勒公式就是:

    \small f(x)=\sum_{i=0}^\infty\frac{f^{(i)}(x_0)}{i!}(x-x_0)^i

    其中x_0是可取任意一点,\small f^{(i)}就是f函数的i阶导。这个公式的准确含义及用途我也不是很清楚,但是很有用。

    它有一些比较常用的展开,比如:【后面用不到的,看看就好了,叫做麦克劳林公式

    \small e^x=\sum_{i=0}^\infty\frac{x^i}{i!}

    2.牛顿迭代

    已知\small g(x),求\small f(x),满足:

    \small g(f(x))\equiv 0(mod~x^n)

    这次是复合函数了呢。我们假设已知\small f_0(x):(n/2上取整,下同

    \small g(f_0(x))\equiv0(mod~x^{n/2})

    是不是就和泰勒展开有点点像了?我们把f函数当成变量带入Taylor公式可得:

    \small g(f(x))=\frac{g(f_0(x))}{0!}+\frac{g'(f_0(x))}{1!}(f_(x)-f_0(x))+\frac{g''(f_0(x))}{2!}(f(x)-f_0(x))^2+...\\ ~~~~~~~~~~~~~~~=\frac{g(f_0(x))}{0!}+\frac{g'(f_0(x))}{1!}(f_(x)-f_0(x))

    可以看出从第三项开始就都被省去了。为什么呢?因为都一定可以拆出一项为:\small (f(x)-f_0(x))^2.是不是很眼熟?就刚好是我们前面求多项式逆元的时候证明过的,这个东西满足:\small (f(x)-f_0(x))^2 \equiv 0(mod~x^n)。所以后面的项就都是0了。

    所以就有:

    \small f(x)=f_0(x)-\frac{g(f_0(x))}{g'(f_0(x))}【很可惜最后这一步是怎么化简过来的我也推不出来……】

    最后化简出来的这个公式就是牛顿迭代式。其实到这里的时候,对于化简公式的问题,\small g(x)就只是个形式了。

    一般的运用技巧是:将要求的式子转化成左边一坨,右边同余0的形式,然后将左边的部分全部视作\small g(f(x)),确认变量,带入最后的这个公式即可。

    举个例子——求多项式exp的时候。

     

    四、多项式exp

    已知\small A(x),求\small B(x)满足:

    \small B(x) \equiv e^{A(x)}(mod~x^n)

    又是一个看起来很不友好的式子呢……直接求导作用不大,但我们学了对数,所以两边同时取对:

    \small lnB(x)-A(x) \equiv 0(mod`x^n)

    将左边那一坨都当成\small g(f(x)),即\small f(x)=B(x),带入牛顿迭代式就有:

    \small B(x)=B_0(x)-\frac{lnB_0(x)-A(x)}{\frac{1}{B_0(x)}}

    p.s:因为牛顿迭代中,下面部分求导,其中\small A(x)我们已知视作常数,所以:
    \small (lnB_0(x)-A(x))'=ln'B_0(x)-0=\frac{1}{B_0(x)}

    所以就有:

    \small B(x)=B_0(x)(1-lnB_0(x)+A(x))

    到这里其实我们就可以求解啦!!!ln套前面的对数,后面的括号内是加减法【注意1是常数项】,最后再NTT乘起来。

    也就是说多项式exp包含了多项式ln,多项式ln包含了求导积分和多项式inv……【禁止套娃?雾】

    上代码——

    ll c[maxn];
    void get_exp(ll *a, ll *b, int n) {
    	if(n == 1) {b[0] = 1; return;}//e的0次方是1
    	get_exp(a, b, n + 1 >> 1);
    	memset(c, 0, sizeof c);
    	get_ln(b, c, n);//c = ln(b)
    	c[0] = (1 - c[0] + a[0] + mod) % mod;//第0项因为有1这个常数所以单独处理
    	for(int i = 1; i < n; i++) c[i] = (a[i] - c[i] + mod) % mod;
    	
    	NTT(c, 1), NTT(b, 1);
    	for(int i = 0; i <= len; i++) b[i] = b[i] * c[i] % mod;
    	NTT(b, -1);
    	for(int i = n; i <= len; i++) b[i] = 0;
    }

    也就是说其实每一个部分的代码看起来都是很简单的,记住怎么推导的就好了。

     

    五、多项式快速幂

    已知\small A(x),求\small B(x)满足:

    \small B(x)\equiv A^k(x)(mod~x^n)

    1.指数较小时

    我们知道快速幂的写法,就是将指数二进制拆分,复杂度为一个log。多项式也可以这么整,每次相乘都NTT一下就可以了。

    int n, m, k;
    ll ta[maxn], tb[maxn], tc[maxn];
    void mul(ll *a, ll *b, ll *c) {
        for(int i = 0; i <= len; i++) ta[i] = a[i], tb[i] = b[i];//放到ta,tb,tc里面,不改变原数组
        NTT(ta, 1), NTT(tb, 1);
        for(int i = 0; i <= len; i++) tc[i] = ta[i] * tb[i] % mod;
        NTT(tc, -1);
        for(int i = 0; i < n; i++) c[i] = tc[i];
    }
     
    ll a[maxn], b[maxn];
    signed main() {
    	//略
    	while(len <= n + n) len <<= 1, l++;//这两行是NTT的操作 
        for(int i = 1; i <= len; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << l - 1);
    
        while(k) {//形如快速幂
            if(k & 1) mul(a, b, a);
            mul(b, b, b);
            k >>= 1;
        }
        //略 
    }

    可能你会问,为什么每次乘过去过后都要NTT逆变换回来?很简单,因为我们要求的是前n项,如果一直不NTT回来的话,那么a数组的长度,也就是NTT时的len就会一直变长变长。根据NTT计算方法对半得到的原理,我们明显不能在点值表达啊上强行只看前n项。所以就要NTT回来了。

    这样快速幂的复杂度是\small O(nlogn*logk)

    2.指数较大时

    比如这个题:洛谷P5245 【模板】多项式快速幂

    我们可以看到指数的范围是极其的大,明显不能用log的算法。【可能就我一个人有这种想法】也不能用费马小定理减小指数,因为这是多项式相乘,模\small x^n

    怎么办呢——我们可以考虑:如何把指数给降下来。我们两边同时取对:

    \small lnB(x) \equiv lnA^k(x) \equiv klnA(x)(mod~x^n)

    这样一来我们就把k给降下来啦,并且很明显的是,k作为系数,是可以取余998244353的,我们快读的时候加一个取余的操作就解决k很大的问题了。现在要求\small B(x),两边再一起exp一下就好了。所以就有:

    \small B(x)\equiv e^{klnA(x)}

    直接套用我们前面的exp即可。就不放代码了。时间复杂度\small O(nlogn)

     

    至此就是全部的内容啦!!!!!!!!!!!!!还有多项式开根,除法什么的以后学了再回来完善。

    迎评:)
    ——End——

    展开全文
  • 题意:求一个次数界为n的多项式在模P并模x^m的...多项式逆元的含义以及求逆元的方法:http://blog.miskcoo.com/2015/05/polynomial-inverse 公式推导一下。主要还是NTT的使用,我NTT写错了调了半天,太zz了。 ...
  • matlab的M函数文件,附带了函数的使用说明了
  • 求域上多项式逆元

    千次阅读 2020-05-12 19:04:54
    设域F=Zp[x]f(x)\mathbb{F}=\mathbb{Z}_p[x]_{f(x)}F=Zp​[x]f(x)​,其中f(x)f(x)f(x)为Zp\mathbb{Z}_pZp​上的不可约多项式多项式g(x)∈Fg(x)\in\mathbb{F}g(x)∈F,求g(x)g(x)g(x)在F\mathbb{F}F上的逆元。...
  • 最近在复习现代密码理论中的AES,AES中的字节变换的核心操作就是求GF(28)GF(2^8)GF(28)上的多项式逆元,这个问题困扰了我一段时间,今天终于得到解决,其实计算方式和数论中求两个数的Bezout算法是一样的,这里感谢...
  • 逆元已知多项式F(x)F(x),求F(x)F(x)在保留前n项(当然n要是2的次幂)的情况下的逆元G(x)G(x),也就是: F(x)G(x)≡1(modxn)F(x)G(x)\equiv 1 \pmod{x^n} 首先,如果n=1n=1,那么直接就是常数项的逆元,如果n&...
  • AES:有限域的多项式乘法逆元求解

    千次阅读 2017-11-07 17:23:00
    题目: 求解算法, 扩展的欧几里得算法 ...cout多项式(";...cout)的乘法逆元是(";polynomialtostring(x);cout)"; system("pause"); return 0; } 运行结果如下图
  • 多项式乘法逆元 - NTT

    2021-03-03 11:14:06
    递归求解即可#include using namespace std;#define int long longnamespace NTT {#define pw(n) (1<const int N=4000005; // 4 times!const int mod=998244353,g=3;int n,m,bit,bitnum,a[N+5],b[N+5],rev[N+5];...
  • [原]有限域的多项式乘法逆元求解

    千次阅读 2012-05-15 22:13:00
    cout)的乘法逆元是(";polynomialtostring(x);cout)"; system("pause"); return 0; } 运行结果如下图 作者:wjh200821 发表于2012-5-15 22:13:00 原文链接 阅读:2 评论:0 查看评论 转载...
  • 大致题意:一个数列,如果存在一个i∈[1,n-1],使得前i个数字是1-i的一个排列,那么这个数列和不合法的。现在问1-n的排列中,有多少个不合法的数列。 首先,我们定义一个不合法的序列,它仅被最大的一个i给计算,也...
  • 有限域 GF(28282^8)上的元素满足加法交换群、线性空间,所以,是和整数有限域上的运算等价的,所以可以直接重载扩展欧几里得来计算多项式逆元 /* &amp;gt; Problem:main &amp;gt; Author: ...
  • 多项式乘法逆

    2021-03-03 11:14:36
    给定一个多项式 \(F(x)\) ,请求出一个多项式 \(G(x)\), 满足 \(F(x) * G(x) \...考虑倍增多项式只有一项时就是乘法逆元假设我们现在得到了\[G^{'}(x) \equiv F(x) (mod\ x^{\frac{n}{2}})\]我们需要求\[G(x)\equiv...
  • 一. 洛谷4238: 模998244353,NTT: #include&amp;amp;amp;lt;cstdio&amp;amp;amp;gt; #include&amp;amp;amp;lt;algorithm&amp;amp;amp;gt; #define maxn 400005 #define LL long long ...inline LL k
  • 我们要求的f在左边,求个多项式逆元就可以了。 老是T的NTT #include #include #include #include #include #define mmst(a, b) memset(a,b,sizeof(a)) #define mmcp(a, b) memcpy(a,b,sizeof(a...
  • 题面 题意:求出满足两个性质的有根多叉树的数量(结点无标号,孩子有顺序) ①共有 n 个叶子结点(n ≤ 1e5) ②每个非叶结点的儿子数量∈ S(1∉S) 设答案为fi,f_i,生成函数为FF 它要么是叶子,f1=1f_1=1 ...
  • 文章目录一、前言二、数学基础1、GF(2⁸)有限域内的多项式2、不可约多项式3、多项式模运算3、乘法逆元三、算法步骤1、扩展欧几里得算法2、多项式除法3、多项式乘法四、代码实现1、多项式除法2、多项式乘法3、...
  • 很好的东西,很实用的东西,你懂的。基于Gf的多项式求乘法逆元,在很多时候都能够用到。
  • 多项式全家桶
  • 最近经常会遇到RSA的题目,都会用到扩展欧几里得算法来求逆元,所以去系统的学习了一下这个算法的原理。 先奉上dalao的博客 https://blog.sengxian.com/algorithms/gcd-extgcd 前置说明 a | b 表示:a可以整除b ...
  • 多项式求逆

    千次阅读 2019-10-10 15:32:47
    对于多项式 A(x)A(x)A(x),如果存在 A(x)B(x)≡1(modxn)A(x)B(x)\equiv 1 \pmod {x^n}A(x)B(x)≡1(modxn),那么称 B(x)B(x)B(x) 为 A(x)A(x)A(x) 在模 xnx^nxn 意义下的逆元。 注意,这里的模 xnx^nxn,是指舍弃...
  • 题目: /* @author tilltheendwjx @blog http://blog.csdn.net/wjh200821或者http://www.cnblogs.com/tilltheendwjx/ */ #...cout)的乘法逆元是(";polynomialtostring(x);cout)"("pause"); return 0; } 运行结果如下图
  • 2.多项式逆元每次长度都不确定,不能先预处理二进制反转   #include #include #include #include #include using namespace std; typedef long long ll; const int N=3e5+ 5 ; ...
  • 代码:扩展欧几里得求逆元代码 #include #include using namespace std; int ext_gcd(int a,int b,int &x,int &y){//扩展欧几里得求,一组解x,y if(!b) {x=1,y=0;return a;} int d=ext_gcd(b,a%b,y,x)...
  • 【笔记】多项式求逆

    2018-05-29 22:40:06
    对于一个多项式a(x)a(x)a(x),求其逆元b(x)b(x)b(x),即a(x)∗b(x)≡1(modxn)a(x)∗b(x)≡1(modxn)a(x)*b(x)\equiv 1\pmod {x^n} Solution 对于单个元素的逆元我们是会求的,比如说一个数ttt的逆元在膜质数意义...
  • 意义下的逆元即可。 #include #define ll long long using namespace std; int getint() { int i= 0 ,f= 1 ;char c; for (c=getchar();c!= '-' &&(c< '0' ||c> '9' );c=getchar()); if (c== '-' )...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,111
精华内容 844
关键字:

多项式的逆元存在