提交记录 16934

用户 题目 状态 得分 用时 内存 语言 代码长度
myee 1002i. 【模板题】多项式乘法 Accepted 100 63.171 ms 18124 KB C++11 11.91 KB
提交时间 评测时间
2021-11-07 14:38:33 2021-11-07 14:38:37 
#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T power(T base,T index,T mod){return((index<=1)?(index?base:1):(power(base*base%mod,index>>1,mod)*power(base,index&1,mod)))%mod;}
template<typename T>T lowbit(T num){return num&-num;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<const ullt p=998244353>
class mod_ullt//会自然溢出,模数不可过大
{
	private:
		ullt v;
		voi _print(ullt v){if(v>=10)_print(v/10);putchar('0'+v%10);}
	public:
		mod_ullt():v(0){}
		mod_ullt(ullt v):v(v%p){}
		bol empty(){return!v;}
		ullt val(){return v;}
		bol operator<(mod_ullt b){return v<b.v;}
		bol operator>(mod_ullt b){return v>b.v;}
		bol operator<=(mod_ullt b){return v<=b.v;}
		bol operator>=(mod_ullt b){return v>=b.v;}
		bol operator==(mod_ullt b){return v==b.v;}
		bol operator!=(mod_ullt b){return v!=b.v;}
		bol operator<(ullt v){return*this<mod_ullt(v);}
		bol operator>(ullt v){return*this>mod_ullt(v);}
		bol operator<=(ullt v){return*this<=mod_ullt(v);}
		bol operator>=(ullt v){return*this>=mod_ullt(v);}
		bol operator==(ullt v){return*this==mod_ullt(v);}
		bol operator!=(ullt v){return*this!=mod_ullt(v);}
		mod_ullt operator+(mod_ullt b){return mod_ullt(v+b.v);}
		mod_ullt operator+(ullt b){return mod_ullt(v+b%p);}
		mod_ullt operator-(mod_ullt b){return mod_ullt(v+p-b.v);}
		mod_ullt operator-(ullt b){return mod_ullt(v+p-b%p);}
		mod_ullt operator*(mod_ullt b){return mod_ullt(v*b.v);}
		mod_ullt operator*(ullt b){return mod_ullt(b%p*v);}
		mod_ullt operator/(mod_ullt b){return mod_ullt(v*power(b.v,p-2,p));}
		mod_ullt operator/(ullt b){return mod_ullt(v*power(b%p,p-2,p));}
		mod_ullt operator-(){return mod_ullt(p-v);}
		mod_ullt sqrt()
		{
            if(power(v,(p-1)>>1,p)!=1)return 0;mod_ullt b=1;do b++;while(b._power((p-1)>>1)==1);ullt t=p-1,s=0,k=1;while(!(t&1))s++,t>>=1;
            mod_ullt x=_power((t+1)>>1),e=_power(t);while(k<s){if(e._power(1llu<<(s-k-1))!=1)x*=b._power((1llu<<(k-1))*t);e=_power(p-2)*x*x,k++;}return _min(x,-x),x;
        }
		mod_ullt inv(){return mod_ullt(power(v,p-2,p));}
		mod_ullt _power(ullt index){mod_ullt ans(1),w(v);while(index){if(index&1)ans*=w;w*=w,index>>=1;}return ans;}
		voi read(){v=0;chr c;do c=getchar();while(c>'9'||c<'0');do v=c-'0'+v*10,c=getchar();while(c>='0'&&c<='9');v%=p;}
		voi print(){_print(v);}
		voi println(){_print(v),putchar('\n');}
		mod_ullt operator++(int){mod_ullt ans=*this;return*this=*this+1,ans;}
	public:
		mod_ullt&operator=(ullt v){return this->v=v%p,*this;}
		mod_ullt&operator+=(mod_ullt b){return*this=mod_ullt(v+b.v);}
		mod_ullt&operator+=(ullt b){return*this=mod_ullt(v+b%p);}
		mod_ullt&operator-=(mod_ullt b){return*this=mod_ullt(v+p-b.v);}
		mod_ullt&operator-=(ullt b){return*this=mod_ullt(v+p-b%p);}
		mod_ullt&operator*=(mod_ullt b){return*this=mod_ullt(v*b.v);}
		mod_ullt&operator*=(ullt b){return*this=mod_ullt(b%p*v);}
		mod_ullt&operator/=(mod_ullt b){return*this=mod_ullt(v*power(b.v,p-2,p));}
		mod_ullt&operator/=(ullt b){return*this=mod_ullt(v*power(b%p,p-2,p));}
		mod_ullt&operator++(){return*this=*this+1;}
};
template<const ullt p=998244353>
class Inv_ullt
{
    public:
        voi bzr(ullt n){V.clear();V.push_back(0);if(n){V.push_back(1);for(ullt i=2;i<=n;++i)V.push_back(-V[p%i]*(p/i));}}
		mod_ullt<p>inv(ullt n){return V[n];}mod_ullt<p>operator[](ullt n){return V[n];}std::vector<mod_ullt<p> >I(){return V;}
    private:std::vector<mod_ullt<p> >V;
};
template<const ullt p=998244353,const ullt g=3>
class poly_NTT
{
	private:
        std::vector<mod_ullt<p> >V;
	public:
		class NTT_ullt
		{
		    public:
		        uint length(){return len;}
		        voi bzr(uint length)
		        {
		            uint k=0;len=1,V.clear();while(length){++k,len<<=1,length>>=1;}
		            for(uint i=0;i<len;++i)V.push_back(0);for(uint i=0;i<k;++i)V[1<<i]=1<<(k-i-1);for(uint i=3;i<len;++i)V[i]=V[i^lowbit(i)]|V[lowbit(i)];
		        }
		        voi ntt(std::vector<mod_ullt<p> >&x,bol opt)
		        {
		        	mod_ullt<p>gn,c,tmp;uint m,k;
		            for(uint i=0;i<len;++i)if(V[i]<i)std::swap(x[i],x[V[i]]);
		            for(m=2,k=1;m<=len;m<<=1,k<<=1)
		            {
		                gn=power(g,(p-1)/m,p);for(uint i=0;i<len;i+=m){c=1;for(uint j=0;j<k;++j,c=c*gn)tmp=x[i+j+k]*c,x[i+j+k]=x[i+j]-tmp,x[i+j]+=tmp;}
		            }
		            if(opt){uint l=1,r=len-1;while(l<r)std::swap(x[l++],x[r--]);mod_ullt<p>inv=mod_ullt<p>(len).inv();for(uint i=0;i<len;++i)x[i]*=inv;}
		        }
		    private:
		        std::vector<uint>V;uint len;
		};
	public:
		poly_NTT(){V.clear();}
		poly_NTT(std::vector<ullt>V){this->V.clear();for(uint i=0;i<V.size();++i)this->V.push_back(mod_ullt<p>(V[i]));}
		poly_NTT(std::vector<mod_ullt<p> >V):V(V){}
		bol empty(){return cut_zero(),!size();}
		voi bzr(){V.clear();}
		voi push(mod_ullt<p>v){V.push_back(v);}
		voi push(ullt v){V.push_back(mod_ullt<p>(v));}
		voi pop(){V.pop_back();}
		mod_ullt<p>val(uint n){return(n<V.size())?V[n]:mod_ullt<p>();}
		uint deg(){return V.size()-1;}
		uint size(){return V.size();}
        poly_NTT operator+(poly_NTT b){uint n=size();if(b.size()<n)b.chg_siz(n);for(uint i=0;i<n;++i)b[i]+=V[i];b.cut_zero();return b;}
        poly_NTT operator-(poly_NTT b){uint n=size();if(b.size()<n)b.chg_siz(n);for(uint i=0;i<b.size();++i)b[i]=val(i)-b[i];b.cut_zero();return b;}
        poly_NTT operator*(poly_NTT b)
        {
            if(size()==0)return*this;if(b.size()==0)return b;
            std::vector<mod_ullt<p> >v1,v2,v3;NTT_ullt s;uint len;s.bzr(deg()+b.deg()+1),len=s.length();
        	for(uint i=0;i<len;++i)v1.push_back(val(i)),v2.push_back(b.val(i));s.ntt(v1,0),s.ntt(v2,0);
			for(uint i=0;i<len;++i)v3.push_back(v1[i]*v2[i]);s.ntt(v3,1);b=poly_NTT(v3),b.cut_zero();return b;
        }
        poly_NTT operator*(mod_ullt<p>v){if(empty()||v.empty())return poly_NTT();uint n=size();poly_NTT w=*this;for(uint i=0;i<n;++i)w[i]*=v;return w;}
        poly_NTT operator*(const ullt v){return*this*mod_ullt<p>(v);}
        poly_NTT operator-(){return*this*(p-1);}
        poly_NTT inv(){return inv(size());}
        poly_NTT inv(const uint prec)//论文哥常数优化2版本 默认版本
        {
            std::vector<mod_ullt<p> >ans(prec<<1),f;NTT_ullt s;
            ans[0]=V[0].inv();uint tp=1;
            while(tp<prec)
            {
                f.clear(),tp<<=1;for(uint i=0;i<tp;++i)f.push_back(val(i));s.bzr(tp-1),s.ntt(f,0),s.ntt(ans,0);
                for(uint i=0;i<tp;++i)f[i]=-f[i]*ans[i]+1;s.ntt(f,1),tp>>=1;for(uint i=0;i<tp;++i)f[i]=f[i+tp],f[i+tp]=0;
                s.ntt(f,0);for(uint i=(tp<<1)-1;~i;--i)f[i]*=ans[i];s.ntt(f,1),s.ntt(ans,1);for(uint i=0;i<tp;++i)ans[tp+i]=f[i];tp<<=1;
            }
            while(ans.size()>prec)ans.pop_back();return ans;
        }
        poly_NTT diff(){uint n=size();poly_NTT ans;for(uint i=1;i<n;++i)ans.push(V[i]*i);return ans;}
        poly_NTT inte(){uint n=size();poly_NTT ans;ans.push(0);Inv_ullt<p>I;I.bzr(n);for(uint i=0;i<n;++i)ans.push(V[i]*I[i+1]);return ans;}
        poly_NTT inte(Inv_ullt<p>&I){uint n=size();poly_NTT ans;ans.push(0);for(uint i=0;i<n;++i)ans.push(V[i]*I[i+1]);return ans;}
        poly_NTT ln(){return(this->diff()*this->inv()).inte().chg_deg_ed(deg());}
        poly_NTT ln(Inv_ullt<p>&I){return(this->diff()*this->inv()).inte(I).chg_deg_ed(deg());}
        poly_NTT ln(const uint prec){return(this->diff()*this->inv(prec)).inte().chg_deg_ed(prec-1);}
        poly_NTT ln(Inv_ullt<p>&I,const uint prec){return(this->diff()*this->inv(prec)).inte(I).chg_deg_ed(prec-1);}
        poly_NTT exp(){return exp(size());}
        poly_NTT exp(const uint prec)
        {
            poly_NTT m,q;m.push(1),q.push(1);if(empty())return m;uint tp=1;Inv_ullt<p>I;I.bzr(prec*2);
            while(tp<prec)m*=q+*this-(m.diff()*m.inv(tp<<=1)).inte(I),m.chg_siz(tp);m.chg_siz(prec);return m;
        }
        poly_NTT exp(Inv_ullt<p>&I){return exp(I,size());}
        poly_NTT exp(Inv_ullt<p>&I,const uint prec)
        {
            poly_NTT m,q;m.push(1),q.push(1);if(empty())return m;uint tp=1;
            while(tp<prec)m*=q+*this-(m.diff()*m.inv(tp<<=1)).inte(I),m.chg_siz(tp);m.chg_siz(prec);return m;
        }
        poly_NTT _power(const ullt index)
        {
			poly_NTT f,w;if(!index)return f.push(1),f;uint t=0,n=size();while(t<n&&V[t].empty())++t;if(t==n)return*this;
			mod_ullt<p>v=V[t].inv();t*=index;if(t>=n)return poly_NTT();
			for(uint i=t/index;i<t/index+n-t;++i)w.push(v*V[i]);w=(w.ln()*index).exp(),v=V[t/index]._power(index);
			f=std::vector<mod_ullt<p> >(t);for(uint i=t;i<n;i++)f.push(w[i-t]*v);return f;
		}
        poly_NTT _power(Inv_ullt<p>&I,const ullt index)
        {
			poly_NTT f,w;if(!index)return f.push(1),f;uint t=0,n=size();while(t<n&&V[t].empty())++t;if(t==n)return*this;
			mod_ullt<p>v=V[t].inv();t*=index;if(t>=n)return poly_NTT();
			for(uint i=t/index;i<t/index+n-t;++i)w.push(v*V[i]);w=(w.ln(I)*index).exp(I),v=V[t/index]._power(index);
			f=std::vector<mod_ullt<p> >(t);for(uint i=t;i<n;i++)f.push(w[i-t]*v);return f;
		}
        poly_NTT _power(const ullt index1,const ullt index2)//index mod p, index mod (p-1)
        {
			poly_NTT f,w;uint t=0,n=size();while(t<n&&V[t].empty())++t;if(t==n)return index1?*this:(f.push(1),f);
			mod_ullt<p>v=V[t].inv();if(index1==0){f.push(V[t]._power(index2));return f;}t*=index1;if(t>=n)return poly_NTT();
			for(uint i=t/index1;i<t/index1+n-t;++i)w.push(v*V[i]);w=(w.ln()*index1).exp(),v=V[t/index1]._power(index2);
			f=std::vector<mod_ullt<p> >(t);for(uint i=t;i<n;i++)f.push(w[i-t]*v);return f;
		}
		poly_NTT sqrt(){return sqrt(size());}
		poly_NTT sqrt(const uint prec)
		{
		    if(empty())return poly_NTT();
            poly_NTT ans;ans.push(V[0].sqrt());
            mod_ullt<p>f=(p+1)>>1;uint tp=1;
            while(tp<prec)ans=(ans+ans.inv(tp<<=1)**this)*f,ans.chg_deg(tp);
            return ans.chg_siz(prec),ans;
        }
        poly_NTT reverse(){poly_NTT ans;for(uint i=deg();~i;--i)ans.push(V[i]);return ans;}
        poly_NTT operator/(poly_NTT b)
        {
            cut_zero(),b.cut_zero();uint m=size(),n=b.deg();if(m<=n)return poly_NTT();
            poly_NTT f=this->reverse()*b.reverse().inv(m-n);f.chg_siz((m>n)?m-n:0);return f.reverse();
        }
        poly_NTT operator%(poly_NTT b){poly_NTT f=*this-*this/b*b;f.cut_zero();return f;}
        poly_NTT sin(){mod_ullt<>i=mod_ullt<p>(p-1).sqrt();return((*this*-i).exp()-(*this*i).exp())*i*((p+1)>>1);}
        poly_NTT cos(){mod_ullt<>i=mod_ullt<p>(p-1).sqrt();return((*this*-i).exp()+(*this*i).exp())*((p+1)>>1);}
	    voi cut_zero(){while(!V.empty()&&V.back().empty())V.pop_back();}
	    voi chg_siz(const uint siz){while(V.size()<siz)V.push_back(0);while(V.size()>siz)V.pop_back();}
	    voi chg_deg(const uint d){chg_siz(d+1);}
	    poly_NTT chg_deg_ed(const uint d){poly_NTT ans=*this;return ans.chg_deg(d),ans;}
	public:
		mod_ullt<p>&operator[](const uint n){return V[n];}
		poly_NTT&operator=(std::vector<ullt>V){this->V.clear();for(uint i=0;i<V.size();++i)this->V.push_back(mod_ullt<p>(V[i]));return*this;}
		poly_NTT&operator=(const std::vector<mod_ullt<p> >V){this->V=V;return*this;}
        poly_NTT&operator+=(const poly_NTT b){return*this=*this+b;}
        poly_NTT&operator-=(const poly_NTT b){return*this=*this-b;}
        poly_NTT&operator*=(const poly_NTT b){return*this=*this*b;}
        poly_NTT&operator*=(const mod_ullt<p>b){return*this=*this*b;}
        poly_NTT&operator*=(const ullt b){return*this=*this*b;}
        poly_NTT&operator/=(const poly_NTT b){return*this=*this/b;}
        poly_NTT&operator%=(const poly_NTT b){return*this=*this%b;}
};
poly_NTT<104857601>P,Q;
int main()//以 Luogu P3803 【模板】多项式乘法（FFT） 为例
{
	uint n,m;ullt v;scanf("%u%u",&n,&m);
	for(uint i=0;i<=n;i++)scanf("%llu",&v),P.push(v);
	for(uint i=0;i<=m;i++)scanf("%llu",&v),Q.push(v);
	P*=Q;
	for(uint i=0;i<=n+m;i++)P[i].print(),putchar((i^(n+m))?' ':'\n');
    return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Subtask #1 Testcase #120.41 us24 KBAcceptedScore: 0

Subtask #1 Testcase #261.861 ms17 MB + 636 KBAcceptedScore: 100

Subtask #1 Testcase #323.624 ms8 MB + 980 KBAcceptedScore: 0

Subtask #1 Testcase #423.433 ms7 MB + 56 KBAcceptedScore: 0

Subtask #1 Testcase #523.6 us24 KBAcceptedScore: 0

Subtask #1 Testcase #621.62 us24 KBAcceptedScore: 0

Subtask #1 Testcase #723.16 us24 KBAcceptedScore: 0

Subtask #1 Testcase #858.596 ms17 MB + 96 KBAcceptedScore: 0

Subtask #1 Testcase #957.872 ms15 MB + 976 KBAcceptedScore: 0

Subtask #1 Testcase #1054.583 ms15 MB + 436 KBAcceptedScore: 0

Subtask #1 Testcase #1163.171 ms17 MB + 716 KBAcceptedScore: 0

Subtask #1 Testcase #1250.651 ms16 MB + 596 KBAcceptedScore: 0

Subtask #1 Testcase #1317.95 us24 KBAcceptedScore: 0

Judge Duck Online | 评测鸭在线
Server Time: 2026-03-18 09:50:53 | Loaded in 1 ms | Server Status
个人娱乐项目，仅供学习交流使用 | 捐赠