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

多项式模板

时间：2023-08-15 09:36:25浏览次数：34  
标签：return int 多项式 complex resize inline 模板 const 

//#define FFT_
//#define FAST
//#define SECURE
#ifdef FFT_
#ifdef FAST
#define FAST_FAST_TLE_
#endif
#ifdef SECURE
#define HIGH_PRECISION
#endif
#endif
#ifdef FAST
#include<bits/extc++.h>
#endif
namespace Math{
	const int P=998244353,G=3,Gi=332748118;
	typedef vector<int> Vec;
	typedef unsigned long long ull;
	inline ll fpow(ll a,int b,int MOD=P,ll c=1)
	{
		for(;b;b>>=1,a=a*a%MOD)if(b&1)c=c*a%MOD;
		return c;
	}
	inline int inv(int x,int MOD=P){return fpow(x,MOD-2);}
	inline int extend(int x)
	{
		int n=1;
		while(n<x)n<<=1;
		return n;
	}
	inline int add(int x){return x>P?x-P:x;}
	inline int sub(int x){return x<0?x+P:x;}
	inline void add(int &x,int y){(x+=y)>=P&&(x-=P);}
	inline void sub(int &x,int y){(x-=y)<0&&(x+=P);}
	inline int BSGS(int a,int b,int p)
	{
#ifdef FAST
		__gnu_pbds::gp_hash_table<int,int>mp;
#else 
		unordered_map<int,int>mp;
#endif
		int m=ceil(sqrt(p));//ceil!!
		for(int i=0;i<=m;b=1ll*a*b%p,++i)mp[b]=i;
		a=fpow(a,m);
		for(int i=0,j=1;i<m;j=1ll*j*a%p)
			if(mp.find(j)!=mp.end()&&i*m>=mp[j])
				return i*m-mp[j];
		return -1;
	}
	inline int root(int p)
	{
		Vec fac;
		int phi=p-1,x=phi;
		for(int i=2;i*i<=x;++i)
			if(x%i==0){
				fac.push_back(i);
				while(x%i==0)x/=i;
			}
		if(x>1)fac.push_back(x);
		for(int i=2;i<=phi;++i)
		{
			bool flag=1;
			for(auto j:fac)if(fpow(i,phi/j,p)==1){flag=0;break;}
			if(flag)return i;
		}
		return -1;
	}
	int degree(int a,int k,int p)
	{
		int g=root(p);
		int x=BSGS(g,a,p);
		assert(x>=0&&x%k==0);
		int r=fpow(g,x/k,p);
		return min(r,p-r);
	}
}
using namespace Math;
namespace Poly{
#define lg2(x) (31-__builtin_clz(x))
	namespace FFT{
#ifdef HIGH_PRECISION
		typedef __float128 db;
#else
		typedef double db;
#endif
		const db PI=acos(-1);
		struct complex{
			db x,y;
			complex(){}
			explicit complex(db _x,db _y):x(_x),y(_y){}
		};
		typedef vector<complex> Vex;
		inline complex operator + (const complex &a,const complex &b){return complex(a.x+b.x,a.y+b.y);}
		inline complex operator - (const complex &a,const complex &b){return complex(a.x-b.x,a.y-b.y);}
		inline complex operator * (const complex &a,const complex &b){return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
		inline complex& operator += (complex &a,const complex &b){return a=a+b;}
		inline complex& operator -= (complex &a,const complex &b){return a=a-b;}
		inline complex& operator *= (complex &a,const complex &b){return a=a*b;}
		inline void FFT(Vex &a,int opt)
		{
			int n=a.size(),L=lg2(n);
			Vec R(n);
			for(int i=0;i<n;++i)
			{
				R[i]=R[i>>1]>>1|(i&1)<<(L-1);
				if(i<R[i])swap(a[i],a[R[i]]);
			}
			for(int len=1;len<n;len<<=1)
			{
				complex O=complex(cos(PI/len),opt*sin(PI/len));
				for(int i=0;i<n;i+=len<<1)
				{
					complex o=complex(1,0);
					for(int j=0;j<len;++j,o=o*O)
					{
						complex Nx=a[i+j],Ny=o*a[i+j+len];
						a[i+j]=Nx+Ny,a[i+j+len]=Nx-Ny;
					}
				}
			}
		}
		inline void DFT(Vex &a){FFT(a,1);}
		inline void IDFT(Vex &a){
			FFT(a,-1);
			int n=a.size();
			for(auto &i:a)
#ifdef FAST_FAST_TLE_
				i.y/=2*n;
#else
				i.x/=n;
#endif
		}
		Vec mul(Vec a,Vec b)
		{
			int n=a.size()+b.size()-1,N=extend(n);
			a.resize(N),b.resize(N);
#ifdef FAST_FAST_TLE_
			Vex A(N);
			for(int i=0;i<N;++i)A[i]=complex(a[i],b[i]);
			DFT(A);
			for(auto &i:A)i*=i;
			IDFT(A);
			for(int i=0;i<N;++i)a[i]=(int)(A[i].y+0.5);
#else
			Vex A(N),B(N);
			for(int i=0;i<N;++i)A[i].x=a[i],B[i].x=b[i];
			DFT(A),DFT(B);
			for(int i=0;i<N;++i)A[i]*=B[i];
			IDFT(A);
			for(int i=0;i<N;++i)a[i]=(int)(A[i].x+0.5);
#endif
			return a.resize(n),a;
		}
	}
	namespace NTT{
		inline void NTT(Vec &a,int opt)
		{
			int n=a.size(),L=lg2(n);
			Vec R(n);
			vector<ull>t(n);
			copy(a.begin(),a.end(),t.begin());
			for(int i=0;i<n;++i)
			{
				R[i]=R[i>>1]>>1|(i&1)<<(L-1);
				if(i<R[i])swap(t[i],t[R[i]]);
			}
			for(int len=1;len<n;len<<=1)
			{
				ll O=fpow(opt==1?G:Gi,(P-1)/(len<<1));
				for(int i=0;i<n;i+=(len<<1))
				{
					ll o=1;
					for(int j=0;j<len;++j,o=o*O%P)
					{
						int tmp=o*t[i+j+len]%P;
						t[i+j+len]=t[i+j]-tmp+P;
						t[i+j]+=tmp;
					}
				}
			}
			for(int i=0;i<n;++i)a[i]=t[i]%P;
		}
		inline void DFT(Vec &a){NTT(a,1);}
		inline void IDFT(Vec &a)
		{
			NTT(a,-1);
			int Inv=inv(a.size());
			for(auto &i:a)i=1ll*i*Inv%P;
		}
		Vec mul(Vec a,Vec b)
		{
			int n=a.size()+b.size()-1,N=extend(n);
			a.resize(N),b.resize(N);
			DFT(a),DFT(b);
			for(int i=0;i<N;++i)a[i]=1ll*a[i]*b[i]%P;
			IDFT(a);
			return a.resize(n),a;
		}
	}
#ifdef FFT_
	using FFT::mul;
	using FFT::DFT;
	using FFT::IDFT;
#else
	using NTT::mul;
	using NTT::DFT;
	using NTT::IDFT;
#endif
	Vec operator * (const Vec &a,const Vec &b){return mul(a,b);}
	Vec& operator *= (Vec &a,const Vec &b){return a=a*b;}
#ifndef FFT_
	Vec operator ~ (Vec);
	Vec fix(Vec,int);
	Vec operator - (Vec A,Vec B)
	{
		int n=max(A.size(),B.size());
		A.resize(n),B.resize(n);
		for(int i=0;i<n;++i)A[i]=sub(A[i]-B[i]);
		return A;
	}
	Vec operator - (Vec A){
		for(auto i:A)i=sub(-i);
		return A;
	}
	Vec operator - (int v,Vec A){
		sub(A[0],v);
		return A;
	}
	Vec operator - (Vec A,int v){
		sub(A[0],v);
		return A;
	}
	Vec operator + (int v,Vec A){
		add(A[0],v);
		return A;
	}
	Vec operator + (Vec A,int v){
		add(A[0],v);
		return A;
	}
	Vec operator + (Vec A,Vec B){
		int n=max(A.size(),B.size());
		A.resize(n),B.resize(n);
		for(int i=0;i<n;++i)A[i]=add(A[i]+B[i]);
		return A;
	}
	Vec operator / (Vec A,Vec B)
	{
		int n=A.size()-B.size()+1;
		if(n<=0)return Vec(1,0);
		reverse(A.begin(),A.end());
		reverse(B.begin(),B.end());
		A.resize(n),B.resize(n);
		A=fix(A*~B,n);
		return reverse(A.begin(),A.end()),A;
	}
	Vec operator % (Vec A,Vec B){int n=B.size()-1;return fix(A-A/B*B,n);}
	Vec operator ~ (Vec A)
	{
		int n=A.size(),N=extend(n);
		A.resize(N);
		Vec I(N);
		I[0]=inv(A[0]);
		for(int l=2;l<=N;l<<=1)
		{
			Vec X(l),Y(l);
			copy(A.begin(),A.begin()+l,X.begin());
			copy(I.begin(),I.begin()+l,Y.begin());
			int L=l<<1;
			X.resize(L),Y.resize(L);
			DFT(X),DFT(Y);
			for(int i=0;i<L;++i)X[i]=1ll*Y[i]*(P+2-1ll*X[i]*Y[i]%P)%P;
			IDFT(X),X.resize(l);
			copy(X.begin(),X.begin()+l,I.begin());
		}
		return I.resize(n),I;
	}
	Vec fix(Vec A,int n)
	{
		return A.resize(n),A;
	}
	Vec der(Vec A,bool mod=1)
	{
		int n=A.size();
		if(n==1)return Vec(1,0);
		Vec D(n-1);
		for(int i=1;i<n;++i)D[i-1]=1ll*i*A[i]%P;
		if(mod)D.resize(n);
		return D;
	}
	Vec inte(Vec A,bool mod=1)
	{
		int n=A.size();
		Vec I=Vec(n+1,0);
		for(int i=1;i<=n;++i)I[i]=1ll*inv(i)*A[i-1]%P;
		if(mod)I.resize(n);
		return I;
	}
	inline Vec ln(Vec A){
		assert(A[0]==1);
		int n=A.size();
		return inte(fix(der(A)*~A,n));
	}
	inline Vec sqrt(Vec A)
	{
		int n=A.size(),N=extend(n);
		A.resize(N);
		Vec R(N);
		R[0]=degree(A[0],2,P);
		int i2=inv(2,P);
		for(int l=2;l<=N;l<<=1)
		{
			Vec F(l),G(l);
			copy(A.begin(),A.begin()+l,F.begin());
			copy(R.begin(),R.begin()+l,G.begin());
			Vec I=~G;
			int L=l<<1;
			F.resize(L),G.resize(L),I.resize(L);
			DFT(F),DFT(G),DFT(I);
			for(int i=0;i<L;++i)G[i]=1ll*G[i]*G[i]%P,F[i]=1ll*(F[i]+G[i])*i2%P*I[i]%P;
			IDFT(F),F.resize(l);
			copy(F.begin(),F.begin()+l,R.begin());
		}
		return R.resize(n),R;
	}
	inline Vec exp(Vec A)
	{
		assert(!A[0]);
		int n=A.size(),N=extend(n);
		A.resize(N);
		Vec E(N,0);
		E[0]=1;
		for(int l=2;l<=N;l<<=1)
		{
			Vec P=(fix(A,l)-ln(fix(E,l))+1) * fix(E,l);
			copy(P.begin(),P.begin()+l,E.begin());
		}
		return E.resize(n),E;
	}
	Vec ls,rs,pos;
	vector<Vec>h,g;
	int id;
	#define mid ((l+r)>>1)
	inline void dfs(int &rt,int l,int r){
		rt=id++;
		if(l==r)return pos[l]=rt,void();
		dfs(ls[rt],l,mid),dfs(rs[rt],mid+1,r);
	}
	#undef mid
	inline void build(int n){
		ls.resize(2*n),rs.resize(2*n);
		h.resize(2*n),g.resize(2*n);
		pos.resize(n),id=0;
		dfs(*new int,0,n-1);
	}
	pair<Vec,Vec> calc(Vec H,Vec G1,Vec G2){
		int n=H.size(),N=extend(n),m1=G1.size(),m2=G2.size();
		reverse(G1.begin(),G1.end());
		reverse(G2.begin(),G2.end());
		H.resize(N),G1.resize(N),G2.resize(N);
		DFT(H),DFT(G1),DFT(G2);
		for(int i=0;i<N;++i)G1[i]=1ll*G1[i]*H[i]%P;
		for(int i=0;i<N;++i)G2[i]=1ll*G2[i]*H[i]%P;
		IDFT(G1),IDFT(G2);
		return make_pair(Vec(G2.begin()+m2-1,G2.begin()+n),Vec(G1.begin()+m1-1,G1.begin()+n));
	}
	Vec _eval(Vec A,Vec Q){
		int n=A.size(),N=extend(2*n-2);
		build(n);
		for(int i=0;i<n;++i)g[pos[i]]=(Vec){1,add(P-Q[i])};
		for(int i=n*2-2;~i;--i)if(ls[i])g[i]=g[ls[i]]*g[rs[i]];
		g[0]=~g[0];
		reverse(g[0].begin(),g[0].end());
		A.resize(N),g[0].resize(N);
		DFT(A),DFT(g[0]);
		for(int i=0;i<N;++i)A[i]=1ll*A[i]*g[0][i]%P;
		IDFT(A);
		h[0].resize(n);
		copy(A.begin()+n,A.begin()+2*n,h[0].data());
		for(int i=0;i<n*2-1;++i)if(ls[i])tie(h[ls[i]],h[rs[i]])=calc(h[i],g[ls[i]],g[rs[i]]);
		Vec ans(n);
		for(int i=0;i<n;++i)ans[i]=h[pos[i]][0];
		return ans;
	}
	Vec eval(Vec A,Vec Q)
	{
		ls.clear(),rs.clear(),pos.clear(),h.clear(),g.clear();
		int n=A.size(),m=Q.size();
		A.resize(max(n,m)),Q.resize(max(n,m));
		return fix(_eval(A,Q),m);
	}
#endif
}
using namespace Poly;

标签：return,int,多项式,complex,resize,inline,模板,const
From： https://www.cnblogs.com/LLCSBlog/p/17630466.html

相关文章

  • Mybatis配置文件的空白模板和联系demo所用到的依赖
    核心配置文件模板<?xmlversion="1.0"encoding="UTF-8"?><!DOCTYPEconfigurationPUBLIC"-//mybatis.org//DTDConfig3.0//EN""https://mybatis.org/dtd/mybatis-3-config.dtd"><configuration><envir......
  • C2025暑假集训模板
    快速幂#include<bits/stdc++.h>usingnamespacestd;unsignedlonglonga,b,k,ans=1;intmain(){ cin>>a>>b>>k; if(b==0){ ans=1%k; cout<<ans<<endl; return0; }while(b!=0){ if(b&1) ans=ans*a%k; a=a*a%k; ......
  • Vuejs装饰器风格开发教程（前言、模板项目、类属性、类方法）
    教程前言AOP切面编程是面向对象开发中的一种经典的编程范式，旨在将横切关注点与核心业务逻辑分离来提高代码的模块性和可维护性。如：日志记录、事务管理等就属于横切关注点。在为H5提供Android原生支持时，曾将插件模块改造为AOP模式，实现插件的自动注册。Java领域的SpringBoo......
  • 优维低代码实践：自定义模板
    优维低代码技术专栏，是一个全新的、技术为主的专栏，由优维技术委员会成员执笔，基于优维7年低代码技术研发及运维成果，主要介绍低代码相关的技术原理及架构逻辑，目的是给广大运维人提供一个技术交流与学习的平台。优维低代码实践连载第14期《自定义模板》▽一、概述构件是我们的页面最基......
  • P3374 【模板】树状数组
    \(P3374\)【模板】树状数组1#include<bits/stdc++.h>usingnamespacestd;constintN=5*1e5+10;intn,m;inta[N];//树状数组模板inttr[N];intlowbit(intx){returnx&-x;}voidadd(intx,intc){for(inti=x;i<N;i+=lo......
  • 模板设计模式
    一.意图模板方法模式 (TemplateMethod)是一种行为设计模式，它在超类中定义了一个算法的框架，允许子类在不修改结构的情况下重写算法的特定步骤。模板方法模式是所有模式中最为常见的几个模式之一，是基于继承的代码复用的基本技术。，没有关联关系。因此，在模板方法模式的类结构......
  • SAP Fiori Elements 应用里标准模板 XML Fragment 加载的逻辑和 XMLPreprocessor 的作
    触发时间点是XMLPreprocessor的insertFragment方法:上图的调试器上下文里，我们看到了XMLPreprocessor.js的实现，它是SAPUI5框架中一个重要的文件，它主要负责处理XML视图的预处理工作。对于SAPUI5中的视图创建，可以使用JavaScript、JSON、XML等多种方式。其中，XML......
  • 单调队列模板
    好的，这是一个晴朗的夜晚。-苯荏水平不高甚至菜亖，博客仅仅写给自己避免自己忘记学了什么，也仅据我理解写出，不严谨，非常不严谨。单调队列。在原序列基础上，维护一个单调的序列。单调队列中的元素在原序列中的相对位置不变，且在单调队列中的元素是单调的。基本模板题：https://www.lu......
  • java8 时间模板中 year 和 year-of-era 的不同
    Java8在表示时间的时候引入了一个u激发了我的好奇心,下面给大家讲解下两个的不同:year字段表示公历年份,其值可以是正数或负数,从-999,999,999到999,999,999。year-of-era字段表示日历纪元内的年份,其值范围从1到正无穷大。两者的区别在于:year字段直接表示公历年份,不受纪元......
  • tarjan模板
    ilvoidtarjan(intu){ dfn[u]=low[u]=++num,st[++top]=u,ins[u]=1; G(i,u) { intv=ver[i]; if(!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); } elseif(ins[v])low[u]=min(low[u],dfn[v]); } if(dfn[u]==low[u]) { intt=0; cnt++; do......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99