精华内容
下载资源
问答
  • 题意:求一个次数界为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

    展开全文
  • 目录 一、多项式逆元 二、多项式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——

    展开全文
  • 逆元已知多项式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&...

    多项式求逆元

    已知多项式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&gt;1n&gt;1,那么怎么办?
    设:G(x)G&#x27;(x)使得F(x)G(x)1(modxn/2)F(x)G&#x27;(x)\equiv 1 \pmod{x^{n/2}},且我们已知G(x)G&#x27;(x)
    第一个式子可以变成:F(x)G(x)1(modxn/2)F(x)G(x)\equiv 1 \pmod{x^{n/2}}
    (把模数开了个方,依旧成立)
    把两个式子相减:
    F(x)(G(x)G(x))0(modxn/2)F(x)(G(x)-G&#x27;(x))\equiv 0 \pmod{x^{n/2}}
    G(x)G(x)0(modxn/2)G(x)-G&#x27;(x)\equiv 0 \pmod{x^{n/2}}
    同时平方:(当然模数也平方依旧成立)
    (G(x)G(x))20(modxn)(G(x)-G&#x27;(x))^2\equiv 0 \pmod{x^n}
    G2(x)+G2(x)2G(x)G(x)0(modxn)G^2(x)+G&#x27;^2(x)-2G(x)G&#x27;(x)\equiv 0 \pmod{x^n}
    两边同时乘上F(x)F(x),消掉部分G(x)G(x)
    G(x)+G2(x)F(x)2G(x)0(modxn)G(x)+G&#x27;^2(x)F(x)-2G&#x27;(x)\equiv 0 \pmod{x^n}
    G(x)2G(x)G2(x)F(x)(modxn)G(x)\equiv 2G&#x27;(x)-G&#x27;^2(x)F(x) \pmod{x^n}
    那么,G(x)G(x)就可以快速求出了,
    (同时发现,只要常数项有逆元,这个多项式就有逆元)
    复杂度:T(n)=T(n/2)+O(nlog(n))=O(nlog(n))T(n)=T(n/2)+O(n\log(n))=O(n\log(n))


    多项式开方

    多项式的开方同样可以以这种方法做出来,

    已知多项式F(x)F(x),求F(x)F(x)在保留前n项(当然n要是2的次幂)的情况下的平方根G(x)G(x),也就是:
    G2(x)F(x)(modxn)G^2(x)\equiv F(x) \pmod{x^n}
    首先,如果n=1n=1,那么直接就是常数项的开方,可以暴力枚举,也可以用二次项剩余(CZY的二次剩余Cipolla算法学习小记),

    对于n&gt;1n&gt;1的情况,
    设:G(x)G&#x27;(x)使得G(x)2F(x)(modxn/2)G&#x27;(x)^2\equiv F(x) \pmod{x^{n/2}},且我们已知G(x)G&#x27;(x)
    (把平方写在后面好看QuQ)

    第一个式子可以变成:G2(x)F(x)(modxn/2)G^2(x)\equiv F(x) \pmod{x^{n/2}}
    (把模数开了个方,依旧成立)
    把两个式子相减:
    G2(x)G(x)20(modxn/2)G^2(x)-G&#x27;(x)^2\equiv 0 \pmod{x^{n/2}}
    因式分解:
    (G(x)+G(x))(G(x)G(x))0(modxn/2)(G(x)+G&#x27;(x))(G(x)-G&#x27;(x))\equiv 0 \pmod{x^{n/2}}
    可得G(x)G(x)有两个解(平方嘛),讨论G(x)G(x)0(modxn/2)G(x)-G&#x27;(x)\equiv 0 \pmod{x^{n/2}}的情况,
    G(x)G(x)0(modxn/2)G(x)-G&#x27;(x)\equiv 0 \pmod{x^{n/2}}
    (历史总是惊人的相识)
    同时平方:(当然模数也平方依旧成立)
    (G(x)G(x))20(modxn)(G(x)-G&#x27;(x))^2\equiv 0 \pmod{x^n}
    G2(x)+G(x)22G(x)G(x)0(modxn)G^2(x)+G&#x27;(x)^2-2G(x)G&#x27;(x)\equiv 0 \pmod{x^n}
    因为:G2(x)F(x)(modxn)G^2(x)\equiv F(x) \pmod{x^n}
    F(x)+G(x)22G(x)G(x)0(modxn)F(x)+G&#x27;(x)^2-2G(x)G&#x27;(x)\equiv 0 \pmod{x^n}
    G(x)F(x)+G(x)22G(x)(modxn)G(x)\equiv \frac{F(x)+G&#x27;(x)^2}{2G&#x27;(x)} \pmod{x^n}
    那么,G(x)G(x)就可以快速求出了,
    (同时发现,只要常数项是二次项剩余且有逆元,这个多项式就可以开方)
    复杂度:T(n)=T(n/2)+2O(nlog(n))=O(nlog(n))T(n)=T(n/2)+2*O(n\log(n))=O(n\log(n))


    多项式取模

    已知A(x),B(x)A(x),B(x),求D(x)=A(x)mod&ThinSpace;&ThinSpace;B(x)D(x)=A(x)\mod B(x)
    A(x)=B(x)C(x)+D(x)A(x)=B(x)C(x)+D(x)
    n=A(x)m=B(x)n=A(x)的次数,m=B(x)的次数,显然有mnm\leq n
    上面的等式两边同时乘上xnx^n得:
    xnA(1x)=xmB(1x)xnmC(1x)+xnD(1x)x^nA(\frac{1}{x})=x^mB(\frac{1}{x})x^{n-m}C(\frac{1}{x})+x^nD(\frac{1}{x})
    1x\frac{1}{x}的作用相当于是把多项式头尾翻转一下)

    A(x)=xnA(1x)B(x)=xmB(1x)C(x)=xnmC(1x)D(x)=xnD(1x)A&#x27;(x)=x^nA(\frac{1}{x}),B&#x27;(x)=x^mB(\frac{1}{x}),C&#x27;(x)=x^{n-m}C(\frac{1}{x}),D&#x27;(x)=x^nD(\frac{1}{x})

    可以发现,经过翻转后,
    D(x)D&#x27;(x)中只有次数[nm+1,n]\in[n-m+1,n]的项是有效的,其他项均为0,,
    A(x)A&#x27;(x)中次数[0,n]\in[0,n]的项是有效的,
    B(x)B&#x27;(x)中次数[0,m]\in[0,m]的项是有效的,
    C(x)C&#x27;(x)中次数[0,nm]\in[0,n-m]的项是有效的,

    现在再对原来的等式mod&ThinSpace;&ThinSpace;xnm+1\mod{x^{n-m+1}},也就是
    A(x)=B(x)C(x)+D(x)mod&ThinSpace;&ThinSpace;xnm+1A&#x27;(x)=B&#x27;(x)C&#x27;(x)+D&#x27;(x) \mod{x^{n-m+1}}
    这样D(x)D&#x27;(x)这一项就能模掉了,也就是:
    A(x)=B(x)C(x)mod&ThinSpace;&ThinSpace;xnm+1A&#x27;(x)=B&#x27;(x)C&#x27;(x) \mod{x^{n-m+1}}
    A(x)B(x)=C(x)mod&ThinSpace;&ThinSpace;xnm+1\frac{A&#x27;(x)}{B&#x27;(x)}=C&#x27;(x) \mod{x^{n-m+1}}
    因为C(x)C&#x27;(x)的次数范围刚好在模以内,所以就可以直接求出C(x)C&#x27;(x),变换得C(x)C(x)
    求出了C(x)C(x),剩下直接减就好了
    D(x)=A(x)B(x)C(x)D(x)=A(x)-B(x)C(x)

    复杂度:O(nlog(n))O(n\log(n))


    多项式多点求值

    已知多项式F(x)F(x),给出a1,a2,...,ana_1,a_2,...,a_n,要求F(a1),F(a2),...,F(an)F(a_1),F(a_2),...,F(a_n)

    先抛出一个显然的结论:F(a1)=F(x)mod&ThinSpace;&ThinSpace;(x+a1)F(a_1)=F(x)\mod{(x+a_1)}
    (意思是:多项式F(x)F(x)模多项式(x+a1)(x+a_1)的余数就是当x=a1x=a_1F(x)F(x)的值)

    有这个结论就好办了,
    设多项式Cl,r(x)=i=lr(x+ai)Gl,r(x)=F(x)mod&ThinSpace;&ThinSpace;Cl,r(x)C_{l,r}(x)=\prod_{i=l}^r(x+a_i),G_{l,r}(x)=F(x)\mod{C_{l,r}(x)}
    考虑分治求解,
    显然的:Gl,mid(x)=Gl,r(x)mod&ThinSpace;&ThinSpace;Cl,r(x)G_{l,mid}(x)=G_{l,r}(x)\mod{C_{l,r}(x)},右边同理,
    这样当l=r时Gl,l(x)G_{l,l}(x)就是F(al)F(a_l)的值了,
    做两遍分治FFT,

    复杂度:O(nlog2(n))O(n\log^2(n))


    多项式插值

    给出a1,b1,a2,b2,...,ak,bka_1,b_1,a_2,b_2,...,a_k,b_k,要求多项式F(x)F(x)满足F(ai)=biF(a_i)=b_i

    考虑使用拉格朗日插值法,
    F(x)=i=1kbi(1jk,ijxajaiaj)F(x)=\sum_{i=1}^kb_i(\prod_{1\leq j \leq k,i\ne j }\frac{x-a_j}{a_i-a_j})
    将式子拆成两部分:

    F(x)=i=1kbi(1jk,ij1aiaj)(1jk,ij(xaj))F(x)=\sum_{i=1}^kb_i(\prod_{1\leq j \leq k,i\ne j }\frac{1}{a_i-a_j})(\prod_{1\leq j \leq k,i\ne j }(x-a_j))
    先做前面那一部分:(先取个倒数方便书写)
    Gi=1jk,ij(aiaj)M(x)=j=1k(aiaj)G_i=\prod_{1\leq j \leq k,i\ne j }(a_i-a_j),M(x)=\prod_{j=1}^k(a_i-a_j)
    显然有M(ai)=0M(a_i)=0,

    有:
    Gi=limxaiM(x)M(ai)xajG_i=\lim_{x\to a_i}\frac{M(x)-M(a_i)}{x-a_j}
    我们发现这个东西相当于M(x)M(x)x=aix=a_i处的导数,于是有:

    Gi=limxaiM(x)M(ai)xaj=M(ai)G_i=\lim_{x\to a_i}\frac{M(x)-M(a_i)}{x-a_j}=M&#x27;(a_i)
    所以对M(x)M&#x27;(x)做一次多点求值即可,

    这个东西还可以用洛必达法则证明,
    f(x)=xaif(x)=x-a_i
    已知有limxaiM(x)=0,limxaif(x)=0\lim_{x\to a_i}M(x)=0,\lim_{x\to a_i}f(x)=0
    所以:
    limxaiM(x)f(x)=limxaiM(x)f(x)=M(ai)\lim_{x\to a_i}\frac{M(x)}{f(x)}=\lim_{x\to a_i}\frac{M&#x27;(x)}{f&#x27;(x)}=M&#x27;(a_i)

    现在的原始变成了:
    F(x)=i=1kbiGi(1jk,ij(xaj))F(x)=\sum_{i=1}^kb_iG_i(\prod_{1\leq j \leq k,i\ne j }(x-a_j))
    这个东西可以直接使用分治FFT实现,分治的时候记录两个多项式分别表示是否已经空缺了一位,

    复杂度:O(nlog2(n))O(n\log^2(n))

    多点求值+几遍分治FFT常数爆炸


    多项式牛顿迭代

    已知多项式G(x)G(x),要求多项式FF使得G(F)=0mod&ThinSpace;&ThinSpace;xnG(F)=0\mod{x^n}

    前置技能:

    泰勒展开

    对于多项式f(x)f(x)它在x0x_0处的泰勒展开为:
    f(x)=f(x0)+f(x)1!(xx0)+f(x)2!(xx0)2+.....f(x)=f(x_0)+\frac{f&#x27;(x)}{1!}(x-x_0)+\frac{f&#x27;&#x27;(x)}{2!}(x-x_0)^2+.....

    考虑倍增求FF

    现在要求的FFmod&ThinSpace;&ThinSpace;x2n\mod x^{2n}的,假设我们已经求出了F0F_0表示mod&ThinSpace;&ThinSpace;xn\mod x^n时的答案,

    G(F)G(F)F0F_0处展开:
    G(F)=G(F0)+G(F0)(FF0)+12G(F0)(FF0)2mod&ThinSpace;&ThinSpace;x2nG(F)=G(F_0)+G&#x27;(F_0)(F-F_0)+\frac{1}{2}G&#x27;&#x27;(F_0)(F-F_0)^2 \mod{x^{2n}}
    我们注意到是在mod&ThinSpace;&ThinSpace;x2n\mod{x^{2n}}意义下的,而从第3项开始最低次项的指数均大于2n,所以可以直接省去,于是:

    G(F)=G(F0)+G(F0)(FF0)mod&ThinSpace;&ThinSpace;x2nG(F)=G(F_0)+G&#x27;(F_0)(F-F_0)\mod{x^{2n}}
    又因为G(F)=0mod&ThinSpace;&ThinSpace;x2nG(F)=0\mod{x^{2n}}

    0=G(F0)+G(F0)FG(F0)F0mod&ThinSpace;&ThinSpace;x2n0=G(F_0)+G&#x27;(F_0)F-G&#x27;(F_0)F_0\mod{x^{2n}}

    F=F0G(F0)G(F0)F=F_0-\frac{G(F_0)}{G&#x27;(F_0)}


    多项式求对数

    给出多项式G(x)G(x),要求F(x)F(x)使得F(x)=ln(G(x))mod&ThinSpace;&ThinSpace;xnF(x)=\ln(G(x))\mod{x^n}

    对两边同时求导,最后再积分回来,
    有:
    (ln(G(x)))=G(x)G(x)(\ln(G(x)))&#x27;=\frac{G&#x27;(x)}{G(x)}
    所以
    F(x)=G(x)G(x)dxF(x)=\int \frac{G&#x27;(x)}{G(x)}dx

    复杂度:O(nlog(n))O(n\log(n))


    多项式求EXP

    给出多项式G(x)G(x),求F(x)F(x)满足F(x)=eG(x)F(x)=e^{G(x)}

    考虑使用牛顿迭代,
    设多项式g(x)=ln(x)G(x)g(x)=ln(x)-G(x),即g(F)=0g(F)=0

    F=F0g(F0)g(F0)F=F_0-\frac{g(F_0)}{g&#x27;(F_0)}
    又因为
    g(F0)=(ln(F0))(A)=1F0g&#x27;(F_0)=(\ln(F_0))&#x27;-(A)&#x27;=\frac{1}{F_0}
    所以:

    F=F0F0(ln(F0)A)F=F_0-F_0(\ln(F_0)-A)

    复杂度:O(nlog(n))O(n\log(n))


    多项式求幂

    给出多项式F(x)F(x),求F(x)kF(x)^k
    F(x)k=ekln(F(x))F(x)^k=e^{k\ln(F(x))}

    这样如果k不为整数也能求了

    复杂度:O(nlog(n))O(n\log(n))


    展开全文
  • 那么,我们需要的fn只需要对右边的式子求一个多项式逆元即可。具体见代码(偷了HNU emofunx的板子,实在是太全了) #include #define LL long long using namespace std; const int mod = 998244353;//(119 )...

     

     

    大致题意:一个数列,如果存在一个i∈[1,n-1],使得前i个数字是1-i的一个排列,那么这个数列和不合法的。现在问1-n的排列中,有多少个不合法的数列。

    首先,我们定义一个不合法的序列,它仅被最大的一个i给计算,也即前i个数字是排列,后i+1~n个数字不是排列的情况。这个时候,我们令fn表示长度为n的不合法数列个数,那么显然有:

                                                       \large f_n=\sum_{i=1}^{n-1}i!\left((n-i)!-f_{n-i}\right)

    表示,长度为n的不合法数列个数,首先是前i个要是一个排列,那么有i!种方式。然后后面一定不存在一个排列,那么后面的方案数就是总方案书减去有排列的个数。那么现在考虑如何计算这个数字。

                                                       \large \begin{aligned} f_n =&\sum_{i=1}^{n-1}i!\left((n-i)!-f_{n-i}\right) \\ =&\left(\sum_{i=1}^{n-1}i!(n-i)!\right)-\left(\sum_{i=1}^{n-1}i!f_{n-i}\right) \\ \end{aligned}

    变成下面以后,我么可以分为前后两个部分,前后两部分都是NTT的形式。我们令0!=0,gn为n!的函数。那么就变成了:                                                                 \large f=g^2-g \times f

    整理一下可以有:

                                                         \large f=\frac{g^2}{1+g}

    那么,我们需要的fn只需要对右边的式子求一个多项式逆元即可。具体见代码(偷了HNU emofunx的板子,实在是太全了)

    #include <bits/stdc++.h>
    #define LL long long
    using namespace std;
    
    const int mod = 998244353;//(119 << 23) + 1;
    const int modinv2 = (mod+1)/2; // 1/2 in F_p
    const int G = 3;
    const int N = 540010;
    const int maxn = 530000;
    
    int f[N],g[N],fac[N];
    
    //取模加减乘
    inline int add(int a,int b) {return a+b>=mod?a+b-mod:a+b;}
    inline void inc(int&a,int b) {if ((a+=b)>=mod) a-=mod;}
    inline int sub(int a,int b) {return a-b<0?a-b+mod:a-b;}
    inline void dec(int&a,int b) {if ((a-=b)<0) a+=mod;}
    inline int mul(int a,int b) {return (LL)a*b%mod;}
    inline int qpow(int x,int n) {int ans=1;for (;n;n>>=1,x=(LL)x*x%mod) if (n&1) ans=(LL)ans*x%mod; return ans;}//quick power
    //-------------------------------NTT--------------------------------
    int wn[30],iwn[30]; //wn[i] = G^((P-1)/(2^i)) (mod P), iwn[i] = wn[i]^(-1) (mod P)
    inline void init() //do this before NTT
    {
        wn[23] = qpow(G,(mod-1)/(1<<23));
        for (int i=22;i>=0;i--) wn[i] = mul(wn[i+1],wn[i+1]);
        iwn[23] = qpow(wn[23],(1<<23)-1);
        for (int i=22;i>=0;i--) iwn[i] = mul(iwn[i+1],iwn[i+1]);
    }
    inline void revbin_permute(int a[],int n) {
        int i=1, j=n>>1, k;
        for (;i<n-1;i++) {
            if (i < j) swap(a[i],a[j]);
            for (k=n>>1;j>=k;) {j -= k; k >>= 1;}
            if (j < k) j += k;
        }
    }
    void NTT(int f[],int ldn,int is) {
        int n = (1<<ldn);
        revbin_permute(f,n);
        for (int i=0;i<n;i+=2) {
            int tmp1 = f[i], tmp2 = f[i+1];
            f[i] = add(tmp1,tmp2), f[i+1] = sub(tmp1,tmp2);
        }
        for (int ldm=2;ldm<=ldn;ldm++) {
            int m = (1<<ldm), mh = (m>>1);
            int dw = is>0?wn[ldm]:iwn[ldm], w = 1;
            for (int j=0;j<mh;j++) {
                for (int r=0;r<n;r+=m) {
                    int u = f[r+j], v = mul(f[r+j+mh],w);
                    f[r+j] = add(u,v);
                    f[r+j+mh] = sub(u,v);
                }
                w = mul(w,dw);
            }
        }
    }
    //多项式乘法
    void convolution(int f[],int g[],int n) {
        int ldn; for (int i=20;i>=0;i--) if (n&(1<<i)) {ldn=i;break;}
        NTT(f,ldn,1); NTT(g,ldn,1); //会改变g
        for (int i=0;i<n;i++) f[i] = mul(f[i],g[i]);
        NTT(f,ldn,-1);
        int iv = qpow(n,mod-2);
        for (int i=0;i<n;i++) f[i] = mul(f[i],iv);
    }
    
    //多项式求sq
    void polysq(int f[],int n) {
        int ldn; for (int i=20;i>=0;i--) if (n&(1<<i)) {ldn=i;break;}
        NTT(f,ldn,1);
        for (int i=0;i<n;i++) f[i] = mul(f[i],f[i]);
        NTT(f,ldn,-1);
        int iv = qpow(n,mod-2);
        for (int i=0;i<n;i++) f[i] = mul(f[i],iv);
    }
    
    //多项式求inv
    //Q(2n) = Q(n) - P*Q^2(n)
    void polyinv(int f[],int n) {
        static int g[maxn],b[maxn],c[maxn];
        for (int i=0;i<n;i++) g[i]=0;
        g[0] = qpow(f[0],mod-2);
        for (int i=2;i<=n;i<<=1) {
            for (int j=0;j<i;j++) b[j] = g[j], c[j] = f[j];
            for (int j=i;j<2*i;j++) b[j] = c[j] = 0;
            polysq(b,2*i);
            for (int j=i;j<2*i;j++) b[j] = 0;
            convolution(b,c,2*i);
            for (int j=0;j<i;j++) g[j] = (2ll*g[j] - b[j] + mod)%mod;
        }
        for (int i=0;i<n;i++) f[i] = g[i];
    }
    
    int main()
    {
        init(); int T;
        scanf("%d",&T); g[1]=f[1]=1;
        for(int i=2;i<=100000;i++)
            g[i]=f[i]=(LL)f[i-1]*i%mod;
        int lg; for(lg=1;lg<=100000;lg<<=1);
        polysq(g,lg<<1); f[0]++;
        polyinv(f,lg<<1);
        convolution(f,g,lg<<2);
        while(T--)
        {
            int x;
            scanf("%d",&x);
            printf("%d\n",f[x]);
        }
        return 0;
    }
    

     

    展开全文
  • 题面 题意:求出满足两个性质的有根多叉树的数量(结点无标号,孩子有顺序) ①共有 n 个叶子结点(n ≤ 1e5) ②每个非叶结点的儿子数量∈ S(1∉S) 设答案为fi,f_i,生成函数为FF 它要么是叶子,f1=1f_1=1 ...
  • 我们要求的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...
  • 递归求解即可#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];...
  • 题目:/*@author tilltheendwjx@blog http://blog.csdn.net/wjh200821或者http://www.cnblogs.com/tilltheendwjx/*/#includeusing namespace std;int indexofmax1(int value){int tmp=1;int count=0;...
  • 多项式逆元

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

    千次阅读 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() {...
  • 多项式逆元是一个非常重要的知识点,许多多项式操作都需要用到该算法,包括多项式取模,除法,开跟,求ln,求exp,快速幂。用快速傅里叶变换和倍增法可以在$O(n log n)$的时间复杂度下求出一个$n$次多项式逆元。...
  • 给定一个多项式 \(F(x)\) ,请求出一个多项式 \(G(x)\), 满足 \(F(x) * G(x) \...考虑倍增多项式只有一项时就是乘法逆元假设我们现在得到了\[G^{'}(x) \equiv F(x) (mod\ x^{\frac{n}{2}})\]我们需要求\[G(x)\equiv...
  • 求域上多项式逆元

    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算法是一样的,这里感谢...
  • 1258序列求和V4 题意:求\(S_m(n) = \sum_{i=1}^n i^m ...多项式逆元\(O(mlogm)\)预处理伯努利数,然后可以\(O(m)\)回答 因为是任意模数,所以要用拆系数fft 拆系数fft+多项式逆元,写的爽死了 具体内容可能会写...
  • AES:有限域的多项式乘法逆元求解

    千次阅读 2017-11-07 17:23:00
    题目: 求解算法, 扩展的欧几里得算法 ...cout多项式(";...cout)的乘法逆元是(";polynomialtostring(x);cout)"; system("pause"); return 0; } 运行结果如下图
  • 一. 洛谷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
  • 2.多项式逆元每次长度都不确定,不能先预处理二进制反转   #include #include #include #include #include using namespace std; typedef long long ll; const int N=3e5+ 5 ; ...
  • 多项式有无逆元取决于其常数项有无逆元,显然这题正好保证了$1-C$的常数项为$1$ 再次提醒:次数界开两倍,复杂度:$$T(n)=O(n\log n)+T(n/2)=O(n\log n)$$不过基于常数问题还是不要把它看成一个$log$比较好。 1...

空空如也

空空如也

1 2 3 4 5 ... 12
收藏数 223
精华内容 89
关键字:

多项式逆元