精华内容
下载资源
问答
  • 题意:求一个次数界为n的多项式在模P并模x^m的...多项式逆元的含义以及求逆元的方法:http://blog.miskcoo.com/2015/05/polynomial-inverse 公式推导一下。主要还是NTT的使用,我NTT写错了调了半天,太zz了。 ...

    http://172.20.6.3/Problem_Show.asp?id=2042

    题意:求一个次数界为n的多项式在模P并模x^m的意义下的逆元。P=7*17*2^23+1。

    多项式逆元的含义以及求逆元的方法:http://blog.miskcoo.com/2015/05/polynomial-inverse

    公式推导一下。主要还是NTT的使用,我NTT写错了调了半天,太zz了。

     

     1 #include<iostream>
     2 #include<cstdio>
     3 #include<cstring>
     4 #include<algorithm>
     5 #include<cmath>
     6 #include<complex>
     7 using namespace std;
     8 #define LL long long
     9 const LL P=(LL)7*17*(1<<23)+1;
    10 const int maxn=530010;
    11 LL a[maxn]={},b[maxn]={},e[maxn]={},zz[20][maxn]={};
    12 int bel[maxn]={};
    13 int bt,s,tot=0;
    14 LL mpow(LL x,LL k){
    15     if(k<0){x=mpow(x,P-2);k=-k;}
    16     LL z=1;
    17     while(k){
    18         if(k&1)z=(z*x)%P;
    19         x=(x*x)%P;
    20         k/=2;
    21     }return z;
    22 }
    23 inline void getit(){ for(int i=0;i<s;i++)bel[i]=((bel[i>>1]>>1)|((i&1)<<(bt-1))); }
    24 inline void ntt(LL *c,int n,int dft){
    25     for(int i=0;i<n;i++)if(bel[i]>i)swap(c[bel[i]],c[i]);
    26     for(int step=1;step<n;step<<=1){
    27         LL w=mpow(3,((P-1)/(step*2))*dft);
    28         for(int j=0;j<n;j+=(step<<1)){
    29             LL z=1;
    30             for(int i=j;i<j+step;++i){
    31                 LL x=c[i],y=(c[i+step]*z)%P;
    32                 c[i]=(x+y)%P;
    33                 c[i+step]=((x-y)%P+P)%P;
    34                 z=(z*w)%P;
    35             }
    36         }
    37     }
    38     if(dft==-1){
    39         LL mon=mpow(n,P-2);
    40         for(int i=0;i<n;i++)c[i]=(c[i]*mon)%P;
    41     }
    42 }
    43 inline void dontt(LL *c,LL *d,int x,int y){
    44     bt=1;s=2;int z=x+y-1;
    45     for(;s<z;++bt)s<<=1;
    46     getit();
    47     ntt(c,s,1);ntt(d,s,1);
    48     for(int i=0;i<s;i++)c[i]=(c[i]*d[i])%P;
    49     ntt(c,s,-1);ntt(d,s,1);
    50 }
    51 inline void doit(int n,int m){
    52     if(m==1){++tot; zz[tot][0]=mpow(a[0],P-2); return ;}
    53     doit(n,(m+1)/2);int siz=(m+1)/2; ++tot;
    54     for(int i=0;i<s;i++)e[i]=b[i]=bel[i]=0;
    55     for(int i=0;i<siz;i++){zz[tot][i]=(zz[tot-1][i]*2)%P;b[i]=zz[tot-1][i];}
    56     for(int i=min(n,m)-1;i>=0;--i)e[i]=a[i];
    57     dontt(zz[tot-1],b,siz,siz); siz=siz+siz-1;
    58     dontt(zz[tot-1],e,siz,min(n,m));
    59     for(int i=0;i<m;i++)zz[tot][i]=((zz[tot][i]-zz[tot-1][i])%P+P)%P;
    60 }
    61 int main(){
    62     //freopen("a.in","r",stdin);
    63     int n,m;scanf("%d%d",&n,&m);
    64     for(int i=0;i<n;i++){scanf("%lld",&a[i]);a[i]=((a[i]%P)+P)%P;}
    65     doit(n,m);
    66     for(int i=0;i<m;i++)printf("%lld ",zz[tot][i]);
    67     printf("\n");
    68     return 0;
    69 }
    View Code

     

    转载于:https://www.cnblogs.com/137shoebills/p/9164339.html

    展开全文
  • 求域上多项式逆元

    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上的逆元。...

    问题描述

    设域 F = Z p [ x ] f ( x ) \mathbb{F}=\mathbb{Z}_p[x]_{f(x)} F=Zp[x]f(x),其中 f ( x ) f(x) f(x) Z p \mathbb{Z}_p Zp上的不可约多项式,多项式 g ( x ) ∈ F g(x)\in\mathbb{F} g(x)F,求 g ( x ) g(x) g(x) F \mathbb{F} F上的逆元。

    求逆过程

    先做辗转相除法:令 r 0 = f ( x ) , r 1 = g ( x ) r_0=f(x),r_1=g(x) r0=f(x),r1=g(x)
    r 0 = r 1 q 1 + r 2   … … 1 r 1 = r 2 q 2 + r 3   … … 2 … r n − 2 = r n − 1 q n − 1 + r n   … … n − 1 r n − 1 = r n q n + r n + 1   , 其 中 r n + 1 = 0   … … n \begin{aligned} r_0&=r_1q_1+r_2\ \dots\dots1\\ r_1&=r_2q_2+r_3\ \dots\dots2\\ &\dots\\ r_{n-2}&=r_{n-1}q_{n-1}+r_n\ \dots\dots n-1\\ r_{n-1}&=r_nq_n+r_{n+1}\ ,其中r_{n+1}=0\ \dots\dots n \end{aligned} r0r1rn2rn1=r1q1+r2 1=r2q2+r3 2=rn1qn1+rn n1=rnqn+rn+1 ,rn+1=0 n

    方法1:

    因为 s ( x ) f ( x ) + t ( x ) g ( x ) = ( f ( x ) , g ( x ) ) s(x)f(x)+t(x)g(x)=(f(x), g(x)) s(x)f(x)+t(x)g(x)=(f(x),g(x)),当 ( f ( x ) , g ( x ) ) = 1 (f(x),g(x))=1 (f(x),g(x))=1时有:
    ( t ( x ) g ( x ) ) f ( x ) = ( 1 − s ( x ) f ( x ) ) f ( x ) = 1 (t(x)g(x))_{f(x)}=(1-s(x)f(x))_{f(x)}=1 (t(x)g(x))f(x)=(1s(x)f(x))f(x)=1所以 t ( x ) t(x) t(x)即为 g ( x ) g(x) g(x)在域 F \mathbb{F} F上的逆元。

    其中 b i = b i − 2 − b i − 1 ∗ q n − i b_i=b_{i-2}-b_{i-1}*q_{n-i} bi=bi2bi1qni t ( x ) = b n − 1 t(x)=b_{n-1} t(x)=bn1

    方法2:

    b 1 = q n − 1 b_1=q_{n-1} b1=qn1,计算:

    其中 b i = b i − 2 + b i − 1 ∗ q n − i b_i=b_{i-2}+b_{i-1}*q_{n-i} bi=bi2+bi1qni
      当 n n n为奇数时, t ( x ) = b n − 1 t(x)=b_{n-1} t(x)=bn1
      当 n n n为偶数时, t ( x ) = − b n − 1 t(x)=-b_{n-1} t(x)=bn1

    展开全文
  • 多项式逆元模板

    千次阅读 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
  • 目录 一、多项式逆元 二、多项式ln 三、关于牛顿迭代式 1.泰勒(Taylor)展开式 2.牛顿迭代 四、多项式exp 五、多项式快速幂 1.指数较小时 2.指数较大时
  • matlab的M函数文件,附带了函数的使用说明了
  • 逆元已知多项式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&...
  • 那么,我们需要的fn只需要对右边的式子求一个多项式逆元即可。具体见代码(偷了HNU emofunx的板子,实在是太全了) #include #define LL long long using namespace std; const int mod = 998244353;//(119 )...
  • AES:有限域的多项式乘法逆元求解

    千次阅读 2017-11-07 17:23:00
    题目: 求解算法, 扩展的欧几里得算法 ...cout多项式(";...cout)的乘法逆元是(";polynomialtostring(x);cout)"; system("pause"); return 0; } 运行结果如下图
  • 最近在复习现代密码理论中的AES,AES中的字节变换的核心操作就是求GF(28)GF(2^8)GF(28)上的多项式逆元,这个问题困扰了我一段时间,今天终于得到解决,其实计算方式和数论中求两个数的Bezout算法是一样的,这里感谢...
  • 有限域 GF(28282^8)上的元素满足加法交换群、线性空间,所以,是和整数有限域上的运算等价的,所以可以直接重载扩展欧几里得来计算多项式逆元 /* &amp;gt; Problem:main &amp;gt; Author: ...
  • 我们要求的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...
  • 用C语言简单实现乘法逆元计算的代码(!只能计算正整数)
  • 文章目录一、前言二、数学基础1、GF(2⁸)有限域内的多项式2、不可约多项式3、多项式模运算3、乘法逆元三、算法步骤1、扩展欧几里得算法2、多项式除法3、多项式乘法四、代码实现1、多项式除法2、多项式乘法3、...
  • 题面 题意:求出满足两个性质的有根多叉树的数量(结点无标号,孩子有顺序) ①共有 n 个叶子结点(n ≤ 1e5) ②每个非叶结点的儿子数量∈ S(1∉S) 设答案为fi,f_i,生成函数为FF 它要么是叶子,f1=1f_1=1 ...
  • 多项式求逆

    千次阅读 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 意义下的逆元。 注意...
  • 一. 洛谷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
  • [原]有限域的多项式乘法逆元求解

    千次阅读 2012-05-15 22:13:00
    cout)的乘法逆元是(";polynomialtostring(x);cout)"; system("pause"); return 0; } 运行结果如下图 作者:wjh200821 发表于2012-5-15 22:13:00 原文链接 阅读:2 评论:0 查看评论 转载...
  • 用c语言实现逆元的计算,通过自己设计算法代码实现。
  • 多项式模2运算及求逆元

    千次阅读 2017-10-13 22:59:00
    在GF(28)域上,多项式相加相减结果相同,均为异或操作 x3+x2+1 对应的二进制为 1101 用整数表示就是 13 x2+x+1 对应的二进制为 0111 用整数表示就是 7 x3+x2+1 + x2+x+1 =x3+2x2+x+2 = x3+x 等同于1101⊕0111 = ...
  • 案例:gcd(45,257) step1:gcd(45,257)=gcd(45,45*5+32)=gcd(32,45)=...=gcd(13,13*3+6)=gcd(6,13)=gcd(6,2*6+1)=gcd(1,6)=1,所以45关于257存在乘法逆元 step2:1=13-(6*2)=13-((32-2*13)*2)=13*5-32*2=(4...
  • 【笔记】多项式求逆

    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的逆元在膜质数意义...
  • 目录 @0 - 参考资料@ @1 - 前置技能@ @2 - 一些概念@ @3 - 多项式逆元@ @理论推导@ @参考代码@ @例题与应用@ @4 - 多项式除法与取余@ @理论推导@ ...
  • /*********************************************************************************  该程序实现对n维输入x,n维输出y,给出n阶多项式拟合系数,功能和matlab
  • 很好的东西,很实用的东西,你懂的。基于Gf的多项式求乘法逆元,在很多时候都能够用到。
  • 代码:扩展欧几里得求逆元代码 #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)...
  • 密码学考试复习(关于快速指数算法和扩展欧几里得求逆元),之前考试自己整理的,今天又要学了。里面的算法还能看,还整理的比较透彻当时。备用了留在这。不知道为什么之前上传的xmind一点就跳转到别的页面了,这次...
  • 扩展扩展欧几里得算法求逆元

    千次阅读 2018-07-30 20:30:54
    若a*x≡1(mod b) ,a,b互质,则称x为a的逆元。 根据逆元的定义,则可以转化为a*x+b*y=1。这样就可以用扩展欧几里得算法求x了。 注意:在gcd不为1说明逆元不存在(因为c=1,c%gcd==0为有整数解的充分必要条件),若...
  • 扩展欧几里得算法: 1.扩展欧几里得算法可以求逆元 2.扩展欧几里得算法可以求类似ax+by=m,的所有整数解,当m%...逆元的定义:ax1(mod b) (注意gcd(a,b)==1的时候才能保证a的逆元是x)ax%b=1ax-by=1(是不是和上面...

空空如也

空空如也

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

多项式逆元