首页 > 其他分享 >poly 全家福

poly 全家福

时间：2024-02-16 12:22:24浏览次数：26  
标签：return 全家福 int poly inline size const 

const int P=998244353,Pi=499122177;

inline int inc(int a,int b){return(a+=b)>=P?a-P:a;}
inline int dec(int a,int b){return(a-=b)<0?a+P:a;}
inline int mul(int a,int b){int s=1ll*a*b%P;return s<0?s+P:s;}
inline void add(int &a,int b){(a+=b)>=P?a-=P:1;}
inline void sub(int &a,int b){(a-=b)<0?a+=P:1;}
inline int sgn(int x){return x&1?P-1:1;}
inline int qpow(int a,int b){int res=1;while(b){if(b&1)res=mul(res,a);a=mul(a,a);b>>=1;}return res;}

namespace Poly{

    const int ng=3;
    const int ngi=(P+1)/3;

    const int L=20;
    const int N=1<<L;

    int w[N],pinv[N];

    inline void init_w(){
        w[0]=pinv[1]=1;
        for(int i=0;i<L;i++)
            w[1<<i]=qpow(ng,(P-1)>>(i+2));
        for(int i=2;i<N;i++){
            w[i]=mul(w[i&-i],w[i&i-1]);
            pinv[i]=P-mul(P/i,pinv[P%i]);
        }
    }

    inline void dif(int *f,int n){
        int t,k,*tw,*tf,*pf;
        for(k=n>>1;k;k>>=1){
            for(tw=w,tf=f;tf!=f+n;tw++,tf+=k<<1){
                for(pf=tf;pf!=tf+k;pf++){
                    t=mul(pf[k],*tw);
                    pf[k]=dec(*pf,t);
                    add(*pf,t);
                }
            }
        }
    }

    inline void dit(int *f,int n){
        int t,k,*tw,*tf,*pf;
        for(k=1;k<n;k<<=1){
            for(tw=w,tf=f;tf!=f+n;tw++,tf+=k<<1){
                for(pf=tf;pf!=tf+k;pf++){
                    t=pf[k];
                    pf[k]=mul(dec(*pf,t),*tw);
                    add(*pf,t);
                }
            }
        }
        int iv=P-(P-1)/n;
        for(int i=0;i<n;i++)
            f[i]=mul(f[i],iv);
        reverse(f+1,f+n);
    }

    int f0[N];

    struct poly{

        vector<int>a;
        inline int size(){return(int)a.size();}
        inline int& operator[](int i){return a[i];}
        inline void clear(){a.clear();}
        inline void resize(int n){a.resize(n);}

        inline poly(int n=0,int x=0){a.resize(n,x);}
        inline poly(const vector<int>&o){a=o;}
        inline poly(const poly &o){a=o.a;}

		inline void print(){
            int n=size();poly a=*this;
            for(int i=0;i<n;i++)write(a[i]),putchar(' ');puts("");
        }

        inline void operator+=(poly b){
            int n=size(),m=b.size();
            resize(max(n,m));
            for(int i=0;i<m;i++)
                add(a[i],b[i]);
        }

        inline friend poly operator+(poly a,poly b){
            a+=b;
            return a;
        }

        inline void operator-=(poly b){
            int n=size(),m=b.size();
            resize(max(n,m));
            for(int i=0;i<m;i++)
                sub(a[i],b[i]);
        }

        inline friend poly operator-(poly a,poly b){
            a-=b;
            return a;
        }

        inline void operator<<=(int k){
            int n=size();
            resize(n+k);
            for(int i=0;i<n;i++)
                a[i+k]=a[i];
            for(int i=0;i<k;i++)
                a[i]=0;
        }

        inline friend poly operator<<(poly a,int k){
            a<<=k;
            return a;
        }

        inline void operator*=(int b){
            int n=size();
            for(int i=0;i<n;i++)
                a[i]=mul(a[i],b);
        }

        inline friend poly operator*(poly a,int b){
            a*=b;
            return a;
        }

        inline void operator /=(int b){
            int n=size(),iv=qpow(b,P-2);
            for(int i=0;i<n;i++)
                a[i]=mul(a[i],iv);
        }

        inline friend poly operator/(poly a,int b){
            a/=b;
            return a;
        }

        inline void operator>>=(int k){
            int n=size();
            if(n<=k){
                *this=poly();
                return;
            }
            for(int i=k;i<n;i++)
                a[i-k]=a[i];
            resize(n-k);
        }

        inline friend poly operator>>(poly a,int k){
            a>>=k;
            return a;
        }

        inline poly diff(){
            int n=size();
            if(!n)
                return poly();
            poly res(n-1);
            for(int i=1;i<n;i++)
                res[i-1]=mul(a[i],i);
            return res;
        }

        inline poly intg(){
            int n=size();
            poly res(n+1);
            for(int i=0;i<n;i++)
                res[i+1]=mul(a[i],pinv[i+1]);
            return res;
        }

        inline void dft(){
            int n=size();
            assert(n==(n&-n));
            for(int i=0;i<n;i++)
                f0[i]=a[i];
            dif(f0,n);
            for(int i=0;i<n;i++)
                a[i]=f0[i];
        }

        inline void idft(){
            int n=size();
            assert(n==(n&-n));
            for(int i=0;i<n;i++)
                f0[i]=a[i];
            dit(f0,n);
            for(int i=0;i<n;i++)
                a[i]=f0[i];
        }

        inline void operator*=(poly b){
            int n=size(),m=b.size();
            int lim=1;
            while(lim<n+m-1)
                lim<<=1;
            resize(lim),dft();
            b.resize(lim),b.dft();
            for(int i=0;i<lim;i++)
                a[i]=mul(a[i],b[i]);
            idft(),resize(n+m-1);
        }

        inline friend poly operator*(poly a,poly b){
            a*=b;
            return a;
        }

        inline void operator/=(poly b){
            int n=size(),m=b.size();
            assert(n>=m);
            reverse(a.begin(),a.end());
            reverse(b.a.begin(),b.a.end());
            resize(n-m+1),b.resize(n-m+1);
            *this*=b.inv(),resize(n-m+1);
            reverse(a.begin(),a.end());
        }

        inline friend poly operator/(poly a,poly b){
            a/=b;
            return a;
        }
        
        inline void operator%=(poly b){
            int m=b.size();
            poly q=*this/b;
            *this-=q*b,resize(m-1);
        }

        inline friend poly operator%(poly a,poly b){
            a%=b;
            return a;
        }

        inline poly inv(){
            int n=size();
            assert(n);
            assert(a[0]);
            poly res(1),cp;
            res[0]=qpow(a[0],P-2);
            for(int o=2;o<(n<<1);o<<=1){
                cp=a;cp.resize(o);cp.resize(o<<1);
                res.resize(o<<1);
                res.dft(),cp.dft();
                for(int i=0;i<o<<1;i++)
                    res[i]=mul(res[i],dec(2,mul(res[i],cp[i])));
                res.idft(),res.resize(o);
            }
            res.resize(n);
            return res;
        }

        inline poly ln(){
            int n=size();
            assert(n);
            assert(a[0]==1);
            poly res=(diff()*inv()).intg();
            res.resize(n);
            return res;
        }

        inline poly exp(){
            int n=size();
            assert(n);
            assert(!a[0]);
            poly res(1),fln,cp;
            res[0]=1;
            for(int o=2;o<(n<<1);o<<=1){
                cp=a;cp.resize(o);cp.resize(o<<1);
                res.resize(o);fln=res.ln();fln.resize(o<<1);
                res.resize(o<<1);
                res.dft(),fln.dft(),cp.dft();
                for(int i=0;i<o<<1;i++)
                    res[i]=mul(res[i],dec(1,dec(fln[i],cp[i])));
                res.idft(),res.resize(o);
            }
            res.resize(n);
            return res;
        }

        inline poly pow(int k){
            poly cp=*this;
            assert(cp.size());
            assert(cp.a[0]);
            int c=cp.a[0];
            cp/=c;
            cp=(cp.ln()*k).exp();
            cp*=qpow(c,k);
            return cp;
        }

        inline poly sqrt(){
            int n=size();
            assert(n);
            assert(a[0]==1);
            poly res(1),fiv,cp;
            res[0]=a[0];
            for(int o=2;o<(n<<1);o<<=1){
                cp=a;cp.resize(o);cp.resize(o<<1);
                res.resize(o);fiv=res.inv();fiv.resize(o<<1);
                res.resize(o<<1);
                res.dft(),fiv.dft(),cp.dft();
                for(int i=0;i<o<<1;i++)
                    res[i]=mul(inc(mul(res[i],res[i]),cp[i]),mul((P+1)/2,fiv[i]));
                res.idft(),res.resize(o);
            }
            res.resize(n);
            return res;
        }
        
        inline poly fwt_or(poly a,int op){
            int m=a.size();
            for(int o=2,k=1;k<m;k<<=1,o<<=1)
                for(int i=0;i<m;i+=o)
                    for(int j=0;j<k;j++)
                        op?add(a[i|j|k],a[i|j]):sub(a[i|j|k],a[i|j]);
            return a;
        }
        
        inline poly OR(poly a,poly b){
            int m=a.size();
            a=fwt_or(a,1);b=fwt_or(b,1);
            for(int i=0;i<m;i++)
                a[i]=mul(a[i],b[i]);
            a=fwt_or(a,0);
            return a;
        }
        
        inline void operator|=(poly b){
            poly q=*this;
            *this=OR(*this,b);
        }
        
        inline friend poly operator|(poly a,poly b){
            a|=b;
            return a;
        }
        
        inline poly fwt_and(poly a,int op){
            int m=a.size();
            for(int o=2,k=1;k<m;k<<=1,o<<=1)
                for(int i=0;i<m;i+=o)
                    for(int j=0;j<k;j++)
                        op?add(a[i|j],a[i|j|k]):sub(a[i|j],a[i|j|k]);
            return a;
        }
        
        inline poly AND(poly a,poly b){
            int m=a.size();
            a=fwt_and(a,1);b=fwt_and(b,1);
            for(int i=0;i<m;i++)
                a[i]=mul(a[i],b[i]);
            a=fwt_and(a,0);
            return a;
        }
        
        inline void operator&=(poly b){
            poly q=*this;
            *this=AND(*this,b);
        }
        
        inline friend poly operator&(poly a,poly b){
            a&=b;
            return a;
        }
        
        inline poly fwt_xor(poly a,int op){
            int m=a.size();
            for(int o=2,k=1;k<m;k<<=1,o<<=1)
                for(int i=0;i<m;i+=o)
                    for(int j=0;j<k;j++)
                        if(op){
                            a[i|j]=inc(a[i|j],a[i|j|k]);
                            a[i|j|k]=inc(a[i|j],mul(dec(P,a[i|j|k]),2));
                        }else{
                            a[i|j]=mul(inc(a[i|j],a[i|j|k]),Pi);
                            a[i|j|k]=dec(a[i|j],a[i|j|k]);
                        }
            return a;
        }
        
        inline poly XOR(poly a,poly b){
            int m=a.size();
            a=fwt_xor(a,1);b=fwt_xor(b,1);
            for(int i=0;i<m;i++)
                a[i]=mul(a[i],b[i]);
            a=fwt_xor(a,0);
            return a;
        }
        
        inline void operator^=(poly b){
            poly q=*this;
            *this=XOR(*this,b);
        }
        
        inline friend poly operator^(poly a,poly b){
            a^=b;
            return a;
        }
    };
}

using Poly::init_w;
using Poly::poly;

标签：return,全家福,int,poly,inline,size,const
From： https://www.cnblogs.com/QcpyWcpyQ/p/18017037

相关文章

  • POJ--1179 Polygon(区间DP)
    记录22:012024-2-10http://poj.org/problem?id=1179区间DP问题。区间DP问题可能需要注意的点就是是根据区间长度来计算的，随着迭代区间长度不断增加，结果也就计算出来了这种“任意选择一个位置断开，复制形成2倍长度的链”的方法，是解决DP中环形结构的常用手段之一因此读入数......
  • 通义千问上线春节新应用，AI帮你免费拍全家福
    2月5日，春节将至年味渐浓，阿里云通义千问APP上线多项免费新应用，涵盖全家福、拜新年、万物成龙等图像生成的新玩法，共提供超300套照片模板，用户上传照片即可生成全家福、团圆照、拜年照、千里江山主题照；此外，一个月前火爆全网的全民舞王应用也迎来上新，用户可通过一张照片生成拜年视频，用更......
  • P4342 [IOI1998] Polygon
    原题链接题解最近做的题目有点多，感觉没什么好讲的,某个最大值一定是由连续区间上的节点操作后得来的\(Code\)#include<bits/stdc++.h>usingnamespacestd;intf[105][105][2];intmain(){memset(f,-0x3f3f3f,sizeoff);intn;cin>>n;charop[105];......
  • arcengine GP调用PolygonToLine 报错 -2147467259
    这个原因是传参数问题；GP调用面转线工具时，不能利用该方式传入参数IGpValueTableObjectgpValueTableObject=newGpValueTableObject();//对一个及以上要素类进行相交运算gpValueTableObject.SetColumns(2);objecto1=pFeatureClass2;//输入IFeatureC......
  • 无涯教程-MATLAB - 多项式(Polynomials)
    MATLAB将多项式表示为行向量，其中包含按降序排序的系数。例如，方程P(x)=x4+7x3-5x+9可以表示为-p＝[170-59]；判断多项式polyval函数用于以指定值判断多项式。例如，要判断我们先前的多项式p，在x=4处，键入-p＝[170-59]；polyval(p,4)MATLAB执行上述语句并返......
  • 操作序列计数加强加强加强加强版（polylog）
    哎跟风发一下。前边的工作类似，设\(F_i(x)\)表示从高到低考虑到了第\(i\)位，且第\(i\)位向下退\(x\)的方案数，其中初值为\(F_0(x)=1\)，根据转移可以归纳出这是一个\(i\)次多项式。然后就有经典的插值做法，可以做到\(O(n^3)\)，但是不够strong，考虑不去维护点值，而是维护系数......
  • 多项式求值软件下载Polynomial evaluation software mus 2025 download
    本软件是Windows下64位软件。本软件能计算如a0+a1*x+a2*x^2+......+an*x^n的式子的对b1的求值结果。具体的方法就是在多多项式系数区输入a0到an的值，然后点击计算多项式的结果即可在结果栏算出结果。最大项数为1000项。多项式系数输入时1项1行，从上到下是a0到an，中间不能空行。T......
  • 多项式定积分计算软件2025 64位WIN版下载Polynomial definite integral calculation s
    本软件功能强大，价格实惠，欢迎试用本软件的WIN64位版本。本软件能计算如a0+a1*x+a2*x^2+......+an*a^n的式子的对b1和b2的积分的结果。具体的方法就是在多多项式系数区输入a0到an的值，然后点击计算积分结果即可在结果栏算出结果。最大项数为1000项。多项式系数输入时1项1行，从上......
  • 郑州 河南职业技术学院Henan Polytechnic Henan Vocational & Technical College
    河南职业技术学院始建于1954年12月，先后历经河南省机器制造技工学校、河南省工人技术学校、河南省工业技术师范学校、河南省技工教育师范学校、河南省第一技工学校、河南省劳动厅第一半工半读技术学校(郑州机床厂)、河南省技工学校、河南职业技术教育学院等历史沿革，1999年3月，经教......
  • 多项式（Poly）笔记
    开头先扔板子：多项式板子们定义多项式（polynomial）是形如\(P(x)=\sum\limits_{i=0}^{n}a_ix^i\)的代数表达式。其中\(x\)是一个不定元。\(\partial(P(x))\)称为这个多项式的次数。多项式的基本运算多项式的加减法\[A(x)=\sum_{i=0}^{n}a_ix^i,B(x)=......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99