30pts TLE 求助
查看原帖
30pts TLE 求助
158878
B1ade_楼主2022/6/17 18:11
#include<bits/stdc++.h>
using namespace std;
namespace modint {
	struct mdu {
		int mod;
		unsigned long long help;
		mdu(int x=1) {
			mod=x,help=(__int128(1)<<64)/x;
		}
	} mod=998244353;//g=3
	inline int operator % (const long long &a,const mdu &b) {
		int r=a-(__int128(b.help)*a>>64)*b.mod;
		return {r>=b.mod?r-b.mod:r};
	}
	struct mint {
		//It is suggest that don't use it in the Speed-needed place
		//建议不要在需要追求时间效率的地方使用这个模板
		int w;
		mint(long long x=0) {
			x=x%mod;
			if(x<0)x+=mod.mod;
			w=x;
		}
		bool operator == (const mint &b) const {
			return w==b.w;
		}
	};
	mint operator + (const mint &a,const mint &b) {
		int x=a.w+b.w;
		return {x>=mod.mod?x-mod.mod:x};
	}
	mint operator += (mint &a,const mint &b) {
		return a=a+b;
	}
	mint operator - (const mint &a,const mint &b) {
		int x=a.w-b.w;
		return {x>=0?x:x+mod.mod};
	}
	mint operator -= (mint &a,const mint &b) {
		return a=a-b;
	}
	mint operator * (const mint &a,const mint &b) {
		return {1ll*a.w*b.w%mod};
	}
	mint operator *= (mint &a,const mint &b) {
		return a=a*b;
	}
	mint pw(mint a,int b) {
		mint res=1;
		for(; b; a*=a,b>>=1)
			if(b&1)res*=a;
		return res;
	}
	int exgcd(int a,int b,int &x,int &y) {
		if(!b) {
			x=1,y=0;
			return a;
		}
		int g=exgcd(b,a%b,y,x);
		y-=a/b*x;
		return g;
	}
	mint inv(mint x) {
		//assert that a and mod are relatively prime
		//假定 a 与模数互质
		int ni,nt;
		assert(exgcd(x.w,mod.mod,ni,nt)==1);
		return ni;
	}
	mint operator / (const mint &a,const mint &b) {
		return a*inv(b);
	}
	mint operator /= (mint &a,const mint &b) {
		return a=a/b;
	}
};
namespace biginteger {
	using namespace modint;
	struct bint {
		short tp;
		vector<int>s;
		bint(long long x=0) {
			s.clear();
			if(x>0)tp=1;
			if(!x)tp=0;
			if(x<0)tp=-1,x=-x;
			while(x) {
				s.push_back(int(x%10));
				x/=10;
			}
			reverse(s.begin(),s.end());
		}
		void read() {
			s.clear();
			int c=getchar();
			tp=1;
			while(!isdigit(c)) {
				if(c=='-')tp=-1;
				c=getchar();
			}
			while(isdigit(c)) {
				if(!s.empty()||c!='0')s.push_back({c^'0'});
				c=getchar();
			}
			if(s.empty())tp=0;
		}
		void write() {
			if(!tp)putchar('0');
			else {
				if(tp==-1)putchar('-');
				for(auto z:s)putchar(z^'0');
			}
		}
		bool operator < (const bint &b) const {
			return tp==b.tp?s.size()==b.s.size()?s<b.s:s.size()<b.s.size():tp<b.tp;
		}
		bool operator > (const bint &b) const {
			return b<*this;
		}
		bool operator <= (const bint &b) const {
			return !(b<*this);
		}
		bool operator >= (const bint &b) const {
			return !(*this<b);
		}
		bool operator == (const bint &b) const {
			return tp==b.tp&&s==b.s;
		}
		bool operator != (const bint &b) const {
			return !(*this==b);
		}
	};
	bint operator - (bint a) {
		a.tp=-a.tp;
		return a;
	}
	bint operator + (bint a,bint b) {
		if(!a.tp)return b;
		if(!b.tp)return a;
		bint c;
		reverse(a.s.begin(),a.s.end());
		reverse(b.s.begin(),b.s.end());
		if(a.tp==b.tp) {
			c.tp=b.tp,c.s.resize(max(a.s.size(),b.s.size()));
			int ad=0;
			for(unsigned i=0; i<c.s.size(); ++i) {
				if(i<a.s.size())c.s[i]+=a.s[i];
				if(i<b.s.size())c.s[i]+=b.s[i];
				c.s[i]+=ad;
				if(c.s[i]>=10)c.s[i]-=10,ad=1;
				else ad=0;
			}
			while(ad>0)c.s.push_back(ad%10),ad/=10;
		} else {
			c.tp=a.tp,c.s.resize(max(a.s.size(),b.s.size()));
			for(unsigned i=0; i<c.s.size(); ++i) {
				if(i<a.s.size())c.s[i]+=a.s[i];
				if(i<b.s.size())c.s[i]-=b.s[i];
			}
			while(!c.s.empty()&&c.s.back()==0)c.s.pop_back();
			if(!c.s.empty()) {
				if(c.s.back()<0) {
					c.tp=-c.tp;
					for(auto &z:c.s)z=-z;
				}
				int ad=0;
				for(auto &z:c.s) {
					z+=ad;
					if(z<0)ad=-1,z+=10;
					else ad=0;
				}
				while(!c.s.empty()&&c.s.back()==0)c.s.pop_back();
			}
			if(c.s.empty())c.tp=0;
		}
		reverse(c.s.begin(),c.s.end());
		return c;
	}
	bint operator += (bint &a,const bint &b) {
		return a=a+b;
	}
	bint operator - (const bint &a,const bint &b) {
		return a+-b;
	}
	bint operator -= (bint &a,const bint &b) {
		return a=a-b;
	}
	static void dft(vector<mint>&a,vector<int>&sw,int L,int tp) {
		//In the speed-needed place we expand the mint type
		//这里在瓶颈处我们展开了 mint 类
		for(int i=0; i<L; ++i)
			if(i<sw[i])swap(a[i],a[sw[i]]);
		for(int i=1; i<L; i<<=1) {
			int g=modint::pw(3,tp==1?(mod.mod-1)/i/2:mod.mod-1-(mod.mod-1)/i/2).w;
			for(int j=0; j<L; j+=i) {
				int bf=1;
				for(int k=0; k<i; ++j,++k,bf=1ll*bf*g%mod) {
					int x=a[j].w,y=1ll*a[j+i].w*bf%mod;
					a[j]=x+y,a[j+i]=x-y;
				}
			}
		}
		if(tp==-1) {
			mint ivn=inv(L);
			for(int i=0; i<L; ++i)a[i]*=ivn;
		}
	}
	bint operator * (bint a,bint b) {
		if(a==0||b==0)return 0;
		int L=1<<int(log(a.s.size()+b.s.size()-2)/log(2)+1);
		bint c;
		c.tp=a.tp*b.tp;
		reverse(a.s.begin(),a.s.end());
		reverse(b.s.begin(),b.s.end());
		c.s.resize(a.s.size()+b.s.size()-1);
		if(min(a.s.size(),b.s.size())<4*log(L))
			for(unsigned i=0; i<a.s.size(); ++i)
				for(unsigned j=0; j<b.s.size(); ++j)
					c.s[i+j]+=a.s[i]*b.s[j];
		else {
			assert(L<=8388608);
			//assert that L is no longer than 8388608
			//假定 L 不大于 8388608
			vector<mint>x(L),y(L);
			vector<int>sw(L);
			for(unsigned i=0; i<a.s.size(); ++i)x[i]=a.s[i];
			for(unsigned i=0; i<b.s.size(); ++i)y[i]=b.s[i];
			for(int i=1; i<L; ++i)sw[i]=(i&1?sw[i>>1]|L:sw[i>>1])>>1;
			dft(x,sw,L,1),dft(y,sw,L,1);
			for(int i=0; i<L; ++i)x[i]*=y[i];
			dft(x,sw,L,-1);
			for(unsigned i=0; i<c.s.size(); ++i)c.s[i]=x[i].w;
		}
		int ad=0;
		for(auto &z:c.s)z+=ad,ad=z/10,z%=10;
		while(ad>0)c.s.push_back(ad%10),ad/=10;
		reverse(c.s.begin(),c.s.end());
		return c;
	}
	bint operator *= (bint &a,const bint &b) {
		return a=a*b;
	}
	static bint pw(bint a,int b) {
		bint res=1;
		for(; b; a*=a,b>>=1)
			if(b&1)res*=a;
		return res;
	}
	bint operator << (bint a,int b) {
		for(int i=0; i<b; ++i)a.s.push_back(0);
		return a;
	}
	bint operator <<= (bint &a,const int &b) {
		return a=a<<b;
	}
	bint operator >> (bint a,int b) {
		for(int i=0; i<b; ++i)
			if(!a.s.empty())a.s.pop_back();
			else {
				a.tp=0;
				break;
			}
		return a;
	}
	bint operator >>= (bint &a,const int &b) {
		return a=a>>b;
	}
	bint barret(bint a) {
		int n=a.s.size();
		if(n==1)return 100/a.s[0];
		if(n==2)return 10000/(10*a.s[0]+a.s[1]);
		int m=n/2+1;
		bint b=barret(a>>(n-m))<<(n-m);
		b=(b*((bint(2)<<(n<<1))-a*b))>>(n<<1);
		return b;
	}
	bint operator / (bint a,bint b) {
		assert(b.tp);
		if(!a.tp)return 0;
		int m=a.s.size()-2*b.s.size();
		if(m>0)a<<=m,b<<=m;
		int x=a.tp*b.tp;
		a.tp=b.tp=1;
		bint n=bint(1)<<(b.s.size()<<1),k=barret(b);
		k=(k*a)>>(b.s.size()<<1);
		bint g=k*b;
		while(g<a)k+=1,g+=b;
		while(g>a)k-=1,g-=b;
		k.tp=x;
		if(k.s.empty())k.tp=0;
		return k;
	}
	bint operator /= (bint &a,const bint &b) {
		return a=a/b;
	}
	bint operator % (const bint &a,const bint &b) {
		return a-a/b*b;
	}
	bint operator %= (bint &a,const bint &b) {
		return a=a%b;
	}
	bint pw(bint a,bint b,bint c) {
		bint res=1;
		for(; b!=0; a=a*a%c,b=b/2)
			if(b.s.back()&1)res=res*a%c;
		return res;
	}
	bool miller_rabin(bint n) {
		assert(n.tp==1);
		if(n==1)return 0;
		if(n<=3)return 1;
		if(!(n.s.back()&1))return 0;
		for(int i=20; i>=0; --i) {
			bint v=n-1;
			while((v.s.back()&1)==0)v/=2;
			bint p=rand()%(n-2)+2;
			bint y=pw(p,v,n);
			bool ok=0;
			if(y==1)ok=1;
			else
				while(v<n-1) {
					if(y==n-1) {
						ok=1;
						break;
					}
					v*=2,y=y*y%n;
				}
			if(!ok)return 0;
		}
		return 1;
	}
};
namespace bigdecimal {
	using namespace biginteger;
	const int prc=114;
	struct bfloat {
		bint w;
		int pc;
		long long sc;
		bfloat(bint x=0) {
			w=x;
			pc=prc;
		}
		bfloat(double x) {
			w.s.clear();
			if(x==0)
			{
				w.tp=0;return;
			}
			if(x<0)x=-x,w.tp=-1;
			w=int(floor(x));x-=floor(x);
			for(int i=0;i<15;++i)
				w=int(floor(x*=10)),x-=floor(x);
		}
		void shrink_to_fit(int n) {
			int t=w.s.size()-n;
			pc=n;
			int la=0;
			for(int i=0; i<t; ++i)
				la=w.s.back(),w.s.pop_back(),++sc;
			if(la==5&&t==1&&(!w.s.empty()&&(w.s.back()&1)))w+=w.tp;
			if(la>5||(la==5&&t>1))w+=w.tp;
			if(w.s.empty())w.tp=0;
		}
	};
	bfloat operator + (const bfloat &a,const bfloat &b)
	{
	//	bfloat c;c.tp=max(a.tp,b.tp);
		return 0;
	//	return c;
	} 
};
int main() {
	using namespace bigdecimal;
	using namespace biginteger;
	bint n,m,ans1=1,ans2=2;
	n.read();m.read();
	for (bint i=1;i<=n+2;i+=1) ans1*=i;
	for (bint i=1;i<=n+3;i+=1) ans1*=i;
	for (bint i=1;i<=n+3-m;i+=1) ans1/=i;
	for (bint i=1;i<=n+1;i+=1) ans2*=i;
	for (bint i=1;i<=n+2;i+=1) ans2*=i;
	for (bint i=1;i<=n-m+2;i+=1) ans2/=i;
	bint finans=ans1-ans2;
	finans.write();
	return 0;
}
2022/6/17 18:11
加载中...