多项式模板求调
  • 板块学术版
  • 楼主__Tonycyt__
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/5/12 13:55
  • 上次更新2024/5/12 16:30:49
查看原帖
多项式模板求调
667037
__Tonycyt__楼主2024/5/12 13:55

无法读入多项式。。。

调试发现问题在构造函数

#include<iostream>
#include<cstdio>
#include<cmath>
#include<complex>
#include<windows.h>
using namespace std;
namespace _Poly{
	#define sd signed
	#define ll long long
	#define cp complex<long double>
	const sd N=(1<<20)+10;
	const long double pi=acos(-1.0);
	cp eps[N],inv[N];
	template<class T=sd>
	inline T read(){
		T f=1,x=0;
		char ch=getchar();
		while(ch<48||ch>57){
			if(ch=='-') f=-1;
			ch=getchar();
		}
		while(ch>47&&ch<58) x=(x<<3)+(x<<1)+ch-48,ch=getchar();
		return f*x;
	}
	template<class T>
	inline void write(T x){
		if(x<0){
			putchar('-');
			x=-x;
		}
		if(x>9) write((T)(x/10));
	    putchar(x%10+48);
	}
	void init(sd n){
		for(sd i=0;i<n;i++){
			eps[i]=cp(cos(2*i*pi/n),sin(2*i*pi/n));
			inv[i]=conj(eps[i]);
		}
	}
	void fft(cp*a,cp*omg,sd n){
		sd lim=0;
		while((1<<lim)<n) lim++;
		for(sd i=0;i<n;i++){
			sd t=0;
			for(sd j=0;j<lim;j++)
				if((i>>j)&1) t|=(1<<(lim-j-1));
			if(i<t) swap(a[i],a[t]);
		}
		for(sd i=2;i<=n;i<<=1){
			sd m=i>>1;
			for(cp*j=a;j!=a+n;j++)
				for(sd k=0;k<m;k++){
					cp t=omg[n/i*k]*j[k+m];
					j[k+m]=j[k]-t;
					j[k]+=t;
				}
		}
	}
	struct Poly{
		sd siz;
		ll a[100010];
		Poly(const sd NewSiz=0,const ll NewVal=0ll){siz=NewSiz;for(sd i=0;i<=siz;i++) a[i]=NewVal;}
		Poly(const Poly&poly):siz(poly.siz){for(sd i=0;i<=siz;i++) a[i]=poly[i];}
		ll&operator[](const sd&pos){return (*this).a[pos];}
		const ll operator[](const sd&pos)const{return (*this).a[pos];}
		const Poly operator+()const{return (*this);}
		const Poly operator-()const{
			Poly newpoly(siz);
			for(unsigned i=0;i<=newpoly.siz;i++) newpoly[i]=-a[i];
			return newpoly;
		}
		const Poly operator+(const Poly&poly)const{
			Poly sum(max(siz,poly.siz));
			for(unsigned i=0;i<=sum.siz;i++) sum[i]=a[i]+poly[i];
			return sum;
		}
		const Poly operator*(const Poly&poly)const;
	};
	const Poly Poly::operator*(const Poly&poly)const{
		sd n=1;
		while(n<(siz+poly.siz)) n<<=1;
		cp ca[n],cb[n];
		init(n);
		fft(ca,eps,n);
		fft(cb,eps,n);
		for(sd i=0;i<n;i++) ca[i]*=cb[i];
		fft(ca,inv,n);
		Poly res(n);
		for(sd i=1;i<n;i++) res.a[i]=floor(ca[i].real()/n+0.5);
	}
	istream&operator>>(istream&instream,Poly&poly){
		instream>>poly.siz;
		bool flg=1;
		for(unsigned i=poly.siz;flg;flg=i--) instream>>poly.a[i];
		return instream;
	}
	ostream&operator<<(ostream&outstream,const Poly&poly){
		bool flg=1;
		for(unsigned i=poly.siz;flg;flg=i--) outstream<<poly.a[i]<<' ';
		return outstream;
	}
	Poly getPoly(){
		Poly poly(read());
		for(sd i=poly.siz;i>-1;i--) poly.a[i]=read<ll>();
		return poly;
	}
	Poly getPoly(sd siz){
		Poly poly(siz);
		for(sd i=poly.siz;i>-1;i--) poly.a[i]=read<ll>();
		return poly;
	}
	void putPoly(Poly poly){for(sd i=poly.siz;i>-1;i--) write(poly.a[i]),putchar(' ');}
	#undef ll
	#undef cp
	#undef sd
}using namespace _Poly;
signed main(){
	Poly a=getPoly(),b=getPoly();
	putPoly(a*b);
	return 0;
}

2024/5/12 13:55
加载中...