首页 > 其他分享 >pp_orange的多项式模板

pp_orange的多项式模板

时间：2023-11-21 10:55:44浏览次数：36  
标签：f0 pp int ll long orange mod 模板 define 

/* Code by pp_orange */
#include<bits/stdc++.h>
#define m_p(a,b) make_pair(a,b)
#define pb push_back
#define ll long long
#define ull unsigned long long
#define lld long double
#define inf 0x7FFFFFFF
#define inff 9223372036854775807
#define rep(i,l,r) for(int i=l;i<r;++i)
#define repp(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r-1;i>=l;--i)
#define pper(i,r,l) for(int i=r;i>=l;--i)
#define pii pair<int,int>
#define fi first
#define se second
#define p_q priority_queue
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
#define lb(x) ((x)&-(x))
const int mod = 998244353;
//#define int ll
using namespace std;
inline int rd(){
    int x(0),f(1);char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
inline void out(int X){
    if(X<0) {X=~(X-1); putchar('-');}
    if(X>9) out(X/10);
    putchar(X%10+'0');
}
ll pw(ll x,int d){
    ll t = 1;
    for(;d;d>>=1,x=x*x%mod)if(d&1)t = t*x%mod;
    return t;
}
#define MAX (1<<21)
namespace poly{
    const int de = 1;
    const int intsz = sizeof(int);
    
    int getN(int n){
        int N = 1;
        while(N<=n)N<<=1;
        return N;
    }

    namespace polyNTT{
        int r[MAX];
        int nwsz = -1;
        
        void initR(int N,int lim){
            if(nwsz==lim)return ;
            nwsz = lim;
            rep(i,1,N)r[i] = (r[i>>1]>>1)|((i&1)<<(lim-1));
            return ;
        }
        
        const int G = 3;
        const int Gi = pw(G,mod-2);
        int x,y;
        void NTT(int *a,int N,int tp){
        //1:G, -1:Gi
        //need init R
            if(de)assert(__builtin_ctz(N)==nwsz);
            const int g = tp==1?G:Gi;
            int omg;
            ll w;
            rep(i,0,N)if(r[i]<i)swap(a[i],a[r[i]]);
            for(int mid=1;mid<N;(mid<<=1)){
                omg = pw(g,(mod-1)/(mid<<1));
                for(int i=0,len=(mid<<1);i<N;i+=len){
                    w = 1;
                    for(int j=i;j<i+mid;++j,w=w*omg%mod){
                        x = a[j];
                        y = a[j+mid]*w%mod;
                        a[j] = (x+y)%mod;
                        a[j+mid] = (x-y+mod)%mod;
                    }
                }
            }
            return ;
        }
    }using polyNTT::NTT,polyNTT::initR;
    
    namespace polyMul{
        int tmp[MAX];
        void Mul(int *a,int n,int *b,int m){
        //Mul(rlt,n,b,m) , won't destroy b
        //a^n and b^m
            memcpy(tmp,b,intsz*(m+1));
            int lim = 0;
            int N = 1;
            while(N<=n+m){
                N <<= 1;
                lim++;
            }
            initR(N,lim);
            NTT(a,N,1);
            NTT(b,N,1);
            ll Ni = pw(N,mod-2);
            rep(i,0,N)a[i] = (ll)a[i]*b[i]%mod*Ni%mod;
            NTT(a,N,-1);
            memcpy(b,tmp,intsz*(m+1));
            memset(b+m+1,0,intsz*(N-(m+1)));
            return ;
        }
    }using polyMul::Mul;

    namespace polyInv{
        int f[MAX];
        void Inv(int *b,int *a,int n){
        //Inv(output,input,n) mod x^n , won't destroy a
            int N = 1;
            int lim = 0;
            b[0] = pw(a[0],mod-2);b[1] = 0;
            while(N<n){
                lim++;
                N <<= 1;
                initR(N,lim);
                memset(b+N,0,intsz*N);
                memcpy(f,a,intsz*N);
                memset(f+N,0,intsz*N);
                initR(N<<1,lim+1);
                NTT(b,N*2,1);
                NTT(f,N*2,1);
                rep(i,0,N*2)f[i] = b[i]*(2-(ll)b[i]*f[i]%mod+mod)%mod;
                NTT(f,N*2,-1);
                ll Ni = pw(N*2,mod-2);
                rep(i,0,N)b[i] = f[i]*Ni%mod;
                memset(b+N,0,intsz*N);
            }
            memset(b+n,0,intsz*(N-n));
        }
    }using polyInv::Inv;

    namespace polySqrt{
        int gi[MAX];
        int f[MAX];
        const int inv2 = pw(2,mod-2);
        void Sqrt(int *b,int *a,int n){
        //Sqrt(output,input,n) , mod x^n
            int N = 1;
            int lim = 0;
            if(de)assert(a[0]==1);
            b[0] = 1;b[1] = 0;
            while(N<n){
                lim++;
                N <<= 1;
                memset(b+N,0,intsz*N);
                Inv(gi,b,N);
                memset(gi+N,0,intsz*N);
                memcpy(f,a,intsz*N);
                memset(f+N,0,intsz*N);
                initR(N*2,lim+1);
                NTT(gi,N*2,1);
                NTT(f,N*2,1);
                NTT(b,N*2,1);
                ll Ni = pw(N*2,mod-2);
                rep(i,0,N*2)b[i] = ((ll)f[i]*gi[i]%mod+b[i])*inv2%mod*Ni%mod;
                NTT(b,N*2,-1);
                memset(b+N,0,intsz*N);
            }
            memset(b+n,0,intsz*(N-n));
            return ;
        }
    }using polySqrt::Sqrt;
    
    void Dev(int *a,int n){
        //get Dev [ 0 , n )
        rep(i,0,n-1)a[i] = ((ll)a[i+1]*(i+1))%mod;
        a[n-1] = 0;
        return ;
    }
    
    namespace polyInter{
        int inv[MAX] = {0,1};
        int invsz = 1;
        void initInv(int sz){
            if(sz<=invsz)return ;
            repp(i,2,sz)inv[i] = (mod-(ll)inv[mod%i]*(mod/i)%mod);
            invsz = sz;
        }
        void Inter(int *a,int n){
        //get Inter [ 0 , n )
            initInv(n);
            per(i,n,1)a[i] = ((ll)a[i-1]*inv[i])%mod;
            a[0] = 0;
            return ;
        }
    }using polyInter::Inter;
    
    namespace polyLn{
        int tmp[MAX];
        void Ln(int *b,int *a,int n){
        //Ln(out,in,n) , won't destroy a , mod x^n
            memcpy(tmp,a,intsz*n);

            int N = getN(n-1)*2;
            if(de)assert(a[0]==1);
            memcpy(b,a,intsz*N);
            Inv(a,b,n);
            Dev(b,n);
            
            initR(N,__builtin_ctz(N));
            NTT(a,N,1);
            NTT(b,N,1);
            ll Ni = pw(N,mod-2);
            rep(i,0,N)b[i] = ((ll)a[i]*b[i]%mod*Ni)%mod;
            NTT(b,N,-1);
            memset(b+n,0,intsz*(N-n));
            Inter(b,n);

            memcpy(a,tmp,intsz*n);
            memset(a+n,0,intsz*(N-n));
            return ;
        }
    }using polyLn::Ln;

    namespace polyExp{
        int c[MAX];
        int d[MAX];
        void Exp(int *b,int *a,int n){
        //Exp(out,in,n) , won't destroy a
        // mod x^n
            if(de)assert(a[0]==0);
            int N = 1,lim = 0;
            b[0] = 1,b[1] = 0;
            while(N<n){
                N <<= 1;
                lim++;
                memset(b+N,0,intsz*N);
                Ln(c,b,N);
                memcpy(d,a,intsz*N);
                memset(d+N,0,intsz*N);
                initR(N*2,lim+1);
                NTT(b,N*2,1);
                NTT(c,N*2,1);
                NTT(d,N*2,1);
                ll Ni = pw(N*2,mod-2);
                rep(i,0,N*2)b[i] = (1ll-c[i]+d[i]+mod)%mod*b[i]%mod*Ni%mod;
                NTT(b,N*2,-1);
                memset(b+N,0,intsz*N);
            }
            memset(b+n,0,intsz*(N-n));
            return ;
        }
    }using polyExp::Exp;

    namespace polyPow{
    //暂不支持多测
        int tmp[MAX];
        int c[MAX];
        void Pow(int *b,int *a,int n,ll d){
            if(d==0){
                memset(b,0,intsz*n);
                b[0] = 1;
                return ;
            }
        //Pow(rlt&input,len,times);  mod x^len
            if(de)assert(a[0]==1);
            Ln(tmp,a,n);
            rep(i,0,n)tmp[i] = (tmp[i]*d)%mod;
            Exp(b,tmp,n);
            return ;
        }

        void exPow(int *b,int *a,int n,ll d,ll d2 = -1){
        //exPow(rlt&input,len,times%mod,times%(mod-1));  mod x^len
            if(d2==-1)d2=d;
            if(d==0){
                memset(b,0,intsz*n);
                b[0] = pw(a[0],d2);
                return ;
            }
            int cnt = 0;
            rep(i,0,n){
                if(a[i]==0)cnt++;
                else break;
            }
            ll m = cnt*d;
            if(m>=n){
                memset(b,0,intsz*n);
                return ;
            }
            ll f0 = a[cnt];
            ll if0 = pw(f0,mod-2);
            memcpy(c,a+cnt,intsz*(n-m));
            rep(i,0,n-m)c[i] = (c[i]*if0)%mod;
            Pow(b+m,c,n-m,d);
            memset(b,0,intsz*m);
            f0 = pw(f0,d2);
            rep(i,m,n)b[i] = (b[i]*f0)%mod;
            return ;
        }
    }using polyPow::Pow,polyPow::exPow;

    void Rev(int *a,int n){
        reverse(a,a+n+1);
        return ;
    }

    namespace polyDiv{
    //暂不支持多测
        int gi[MAX];
        int tmpg[MAX];
        void Div(int *q,int *r,int *f,int n,int *g,int m){
        //f = q*g+r , f^n , g^m
            assert(m<=n);
            Rev(f,n);Rev(g,m);

            int sz = n-m+1;
            memcpy(tmpg,g,intsz*sz);
            Inv(gi,tmpg,sz);
            Mul(gi,sz-1,f,n);
            memcpy(q,gi,intsz*sz);

            Rev(f,n);Rev(g,m);Rev(q,n-m);
            //memset(q)...
            memcpy(tmpg,q,intsz*sz);

            Mul(tmpg,n-m,g,m);
            rep(i,0,m)r[i] = (f[i]-tmpg[i]+mod)%mod;
            return ;
        }
    }using polyDiv::Div;

}
int f[MAX],g[MAX],q[MAX],r[MAX];
signed main(){
    //freopen("in.in","r",stdin);
    //freopen("out.out","w",stdout);
    int n = rd();
    int m = rd();
    repp(i,0,n)f[i] = rd();
    repp(i,0,m)g[i] = rd();
    poly::Div(q,r,f,n,g,m);
    repp(i,0,n-m)cout<<q[i]<<' ';cout<<endl;
    rep(i,0,m)cout<<r[i]<<' ';cout<<endl;
    return 0;
}

 

标签：f0,pp,int,ll,long,orange,mod,模板,define
From： https://www.cnblogs.com/pp-orange/p/17845748.html

相关文章

  • 2023-11-21 {“errcode”:40029,“errmsg”:“invalid code, rid: xxx”} ==》后端保
    今天上午登一下小程序，登录失败，后端调查发现是微信登录的时候报了这个错误：{“errcode”:40029,“errmsg”:“invalidcode,rid:xxx”}原因：后端保存的appsecret和appid与前端的appid不匹配导致。解决方案：更新后端保存的appsecret和appid即可。......
  • 获取App Store线上应用版本信息
    热烈欢迎，请直接点击！！！进入博主AppStore主页，下载使用各个作品！！！注：博主将坚持每月上线一个新app！！【 注意：中国大陆区用/cn/，如果是其他地区，请把链接改成对应的地区代码。】1、通过AppID：AppStore搜索对应的应用，点击右上角分享按钮，点击拷贝链接，复制到浏览器中，最后的显示的就是十位idh......
  • Init ubuntu for cpp dev
    sudoaptupdate;sudoaptupgrade-y;wgethttps://dl.google.com/linux/direct/google-chrome-stable_current_amd64.deb;sudodpkg-igoogle-chrome-stable_current_amd64.deb;sudosnapinstall--classiccode;sudoaptinstallgcc-13g++-13-y;sudoaptinstall......
  • Spring5学习随笔-整合MyBatis（持久层）、连接池、Mapper文件
    学习视频：【孙哥说Spring5：从设计模式到基本应用到应用级底层分析，一次深入浅出的Spring全探索。学不会Spring？只因你未遇见孙哥】Spring持久层整合第一章、持久层整合1.Spring框架为什么要与持久层技术进行整合JavaEE开发需要持久层进行数据库的访问操作。JDBCMyBatis、Hibe......
  • Applying sewage charging system to deal with water pollution problem in Russia.
    Whatisthe sewage charging system? Although manufacturing has always been a key driving force for China's economic growth, it is also the root cause of water pollution. In the face of rapid industrialization, China has take......
  • Ubuntu更新源文件报错：E: 仓库 “http://ppa.launchpad.net/chris-lea/node.js/ubuntu
    E:仓库“http://ppa.launchpad.net/chris-lea/node.js/ubuntubionicRelease”没有Release文件。一条命令解决sudoadd-apt-repository--removeppa:chris-lea/node.jssudoadd-apt-repository--removeppa:xxxxx/xxxxx再去执行sudoapt-getupdate就可以顺利的解决了......
  • Linux操作系统的优势官方开发App应用程序有哪些优缺点？
    随着技术的不断进步，Linux操作系统在应用程序开发中扮演着越来越重要的角色。其开放性、稳定性和定制性成为开发者的首选。图片来源：http://news.gulufenfa.com/post/211Linux系统简介Linux作为一个广泛使用的开源操作系统，它的核心是Linux内核，由LinusTorvalds在1991年首次发布。Linu......
  • The Application of River Chief System on Water Pollution in Britain
    Waterpollutionisaglobalconcernthataffectsthehealthandwell-beingofbothhumansandecosystems.InBritain,despiteeffortstoaddressthisissue,waterpollutionremainsasignificantchallenge.However,apromisingsolutiontothisproblemis......
  • wpf 自定义按钮模板
    <ButtonWidth="300"Height="100"Content="自定义按钮"Background="Bisque"FontSize="23"Foreground="Orchid"><Button.Template><ControlTemplateTargetType=&qu......
  • 去掉uniapp程序中顶部返回按钮
    去掉uniapp程序中顶部返回按钮1.javascript"autoBackButton":false在小程序下生效，H5不生效{"path":"pages/donation/list","style":{"navigationBarTitleText":"公益捐款"......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99