QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#288670#6325. Peaceful ResultsqLWA 0ms3364kbC++1413.0kb2023-12-23 11:14:322023-12-23 11:14:32

Judging History

你现在查看的是最新测评结果

  • [2023-12-23 11:14:32]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3364kb
  • [2023-12-23 11:14:32]
  • 提交

answer

#include<cstdio>
#include<type_traits>
#include<initializer_list>
#include<memory>
/**
 * Author: Cracker
 * Version: 0x04
 * Warning:
 * 	Vector is slower than in STL.
 * 	Static Allocator may lead to RE.
 * 	Turn to C++17.
*/
namespace Default_Source{
	namespace Memory{
		struct Memory_Pool_Base{
			template<typename _Tp>
			_Tp*allocate(){return new _Tp[1]{};}
			template<typename _Tp>
			_Tp*allocate(std::size_t n){return new _Tp[n]{};}
			template<typename _Tp>
			void deallocate(_Tp*v){delete[] v;}
		};
		Memory_Pool_Base Runtime_Memory_Pool;
		template<typename _Tp>
		struct Allocator_Base{
			using value_type=_Tp;
			template<typename T>
			struct rebind{using other=Allocator_Base<T>;};
			_Tp*allocate(){return Runtime_Memory_Pool.allocate<_Tp>();}
			_Tp*allocate(std::size_t n){return Runtime_Memory_Pool.allocate<_Tp>(n);}
			void deallocate(_Tp*v,std::size_t n){Runtime_Memory_Pool.deallocate<_Tp>(v);}
		    template<typename T,typename ...Args>
			void construct(T*p,Args&&... args){new(p)T(std::forward<Args>(args)...);}
			template<typename T>
			void destroy(T*p){p->~T();}
		};
		template<typename _Tp,std::size_t MAX_SIZE>
		class Static_Allocator_Base{
		private:
			_Tp pool[MAX_SIZE],*cur=pool;
		public:
			using value_type=_Tp;
			template<typename T>
			struct rebind{using other=Static_Allocator_Base<T,MAX_SIZE>;};
			_Tp*allocate(){return cur++;}
			_Tp*allocate(std::size_t n){
				static _Tp*tmp;
				tmp=cur,cur+=sizeof(_Tp)*n;
				return tmp;
			}
			void deallocate(_Tp*v,std::size_t n){}
		    template<typename T,typename ...Args>
			void construct(T*p,Args&&...args){new(p)T(std::forward<Args>(args)...);}
			template<typename T>
			void destroy(T*p){p->~T();}
		};
	}
	namespace Container{
		template<typename _Tp,typename _Allocator=std::allocator<int>>
		class vector{
		private:
			_Tp*arr;
			int cur;
			static _Allocator Allocator;
			void extend(std::size_t before,std::size_t after){
				_Tp*_arr=Allocator.allocate(after);
				__builtin_memcpy(_arr,arr,sizeof(_Tp)*before);
				Allocator.deallocate(arr,before),arr=_arr;
			}
			void shrink(std::size_t before,std::size_t after){
				_Tp*_arr=Allocator.allocate(after);
				__builtin_memcpy(_arr,arr,sizeof(_Tp)*after);
				Allocator.deallocate(arr,before),arr=_arr;
			}
		public:
			vector():arr{Allocator.allocate(0)},cur{0}{}
			auto begin(){return arr;}
			auto end(){return arr+cur;}
			_Tp&operator[](int x){return arr[x];}
			_Tp operator[](int x)const{return arr[x];}
			std::size_t size()const{return cur;}
			template<typename T>
			void push_back(T&&x){
				if((cur&(-cur))==cur) extend(cur,cur<<1);
				arr[cur++]=x;
			}
		};
		template<typename _Tp,typename _Allocator>
		_Allocator vector<_Tp,_Allocator>::Allocator;
	}
	namespace IO{
		namespace Flush{
			struct Flush_Base{};
			struct Input_Flush_Base:Flush_Base{char getc(){return getchar();}};
			template<std::size_t BUFSIZE>
			class Fast_Input_Flush_Base:Input_Flush_Base{
			protected:
				char buf[BUFSIZE],*cur=buf;
			public:
				Fast_Input_Flush_Base(){std::fread(buf,1,BUFSIZE,stdin);}
				char getc(){return*cur++;}
			};
			template<std::size_t BUFSIZE>
			class Fast_Input_Flush_Safer:Input_Flush_Base{
			protected:
				char buf[BUFSIZE],*cur,*nil;
				bool reload(){return (nil=(cur=buf)+std::fread(buf,1,BUFSIZE,stdin))!=buf;}
			public:
				Fast_Input_Flush_Safer(){reload();}
				char getc(){return (cur!=nil||reload())?*cur++:EOF;}
			};
			struct Output_Flush_Base:Flush_Base{void putc(char ch){putchar(ch);}};
			template<std::size_t BUFSIZE>
			class Fast_Output_Flush_Base:Output_Flush_Base{
			protected:
				char buf[BUFSIZE],*cur=buf;
			public:
				~Fast_Output_Flush_Base(){std::fwrite(buf,1,cur-buf,stdout);}
				void putc(char ch){*cur++=ch;}
			};
		}
		template<typename _Input_Flush=Flush::Input_Flush_Base>
		class Fast_InStream{
			static_assert(std::is_base_of<Flush::Input_Flush_Base,_Input_Flush>::value);
			static _Input_Flush Input;
			using List_Out=std::initializer_list<int>;
		public:
			template<typename _Tp>
			typename std::enable_if<std::is_integral<_Tp>::value,void>::type uread(_Tp&x){
				x=0;char Ch=Input.getc();
				for(;Ch<'0'||Ch>'9';Ch=Input.getc());
				for(;Ch>='0'&&Ch<='9';Ch=Input.getc()) x=x*10+(Ch&15);
			}
			template<typename _Tp>
			typename std::enable_if<std::is_integral<_Tp>::value,void>::type read(_Tp&x){
				x=0;bool sign=false;char Ch=Input.getc();
				for(;Ch<'0'||Ch>'9';Ch=Input.getc()) if(Ch=='-') sign=true;
				for(;Ch>='0'&&Ch<='9';Ch=Input.getc()) x=x*10+(sign?-(Ch&15):(Ch&15));
			}
			void read(char*str){
				while((*str=Input.getc())==' '||*str=='\n');
				while((*++str=Input.getc())!=' '&&*str!='\n');
				*str='\0';
			}
			template<typename ...Args>
			void read(Args&&...args){void(List_Out{(read(args),0)...});}
			template<typename T>
			T read(){
				static T x;
				return read(x),x;
			}
		};
		template<typename _Input_Flush>
		_Input_Flush Fast_InStream<_Input_Flush>::Input;
		template<typename _Output_Flush=Flush::Output_Flush_Base>
		class Fast_OutStream{
			static_assert(std::is_base_of<Flush::Output_Flush_Base,_Output_Flush>::value);
			static _Output_Flush Output;
			using List_Out=std::initializer_list<int>;
		public:
			template<typename _Tp>
			typename std::enable_if<std::is_integral<_Tp>::value,void>::type write(_Tp x){
				static char sta[114];
				int top=0;
				if(x<0){
					Output.putc('-');
					do sta[top++]=(-(x%10))|48,x/=10;
					while(x);
				}
				else
					do sta[top++]=(x%10)|48,x/=10;
					while(x);
				while(top) Output.putc(sta[--top]);
			}
			void write(char Ch){Output.putc(Ch);}
			void write(const char*Str){while(*Str) Output.putc(*Str++);}
			void write(char*Str){write(static_cast<const char*>(Str));}
			template<typename ...Args>
			void write(Args...args){void(List_Out{(write(args),0)...});}
			template<typename ...Args>
			void writeln(Args...args){write(args...),Output.putc('\n');}
		};
		template<typename _Output_Flush>
		_Output_Flush Fast_OutStream<_Output_Flush>::Output;
	}
	namespace DS{
		namespace Sgt{
			enum SegmentTree_Type{Single=1,Interval=2};
			template<typename Info,SegmentTree_Type _Modify,SegmentTree_Type _Query,typename _Allocator=Memory::Allocator_Base<Info>>
			class SegmentTree{};
			template<typename Info,typename _Allocator>
			class SegmentTree<Info,Interval,Interval,_Allocator>{
			private:
				static _Allocator allocator;
				int n;
				Info*tr;
				void build(int p,int l,int r){
					if(l==r) return tr[p].init(l);
					int mid=(l+r)>>1;
					build(p<<1,l,mid),build(p<<1|1,mid+1,r);
					tr[p].pull(tr[p<<1],tr[p<<1|1]);
				}
				void modify(int p,int l,int r,int L,int R,const Info&V){
					if(L<=l&&r<=R) return tr[p].get(V);
					int mid=(l+r)>>1;
					tr[p].push(tr[p<<1],tr[p<<1|1]);
					if(L<=mid) modify(p,l,mid,L,R,V);
					if(R>mid) modify(p<<1|1,mid+1,r,L,R,V);
					tr[p].pull(tr[p<<1],tr[p<<1|1]);
				}
				Info query(int p,int l,int r,int L,int R){
					if(L<=l&&r<=R) return tr[p].info;
					int mid=(l+r)>>1;
					tr[p].push(tr[p<<1],tr[p<<1|1]);
					if(L<=mid&&R>mid) return merge(query(p<<1,l,mid,L,R),query(p<<1|1,mid+1,r,L,R));
					else return L<=mid?query(p<<1,l,mid,L,R):query(p<<1|1,mid+1,r,L,R);
				}
			public:
				SegmentTree():n{}{tr=allocator.allocate(0);}
				void resize(int _n){allocator.deallocate(tr,n),tr=allocator.allocate((n=_n)<<2);}
				~SegmentTree(){allocator.deallocate(tr,n);}
				void build(){build(1,1,n);}
				void build(int _n){resize(_n),build(1,1,n);}
				void modify(int L,int R,const Info&V){modify(1,1,n,L,R,V);}
				Info query(int L,int R){return query(1,1,n,L,R);}
			};
			template<typename Info,typename _Allocator>
			_Allocator SegmentTree<Info,Interval,Interval,_Allocator>::allocator;
			template<typename Info,typename _Allocator>
			class SegmentTree<Info,Interval,Single,_Allocator>{
			private:
				static _Allocator allocator;
				int n;
				Info*tr;
				void build(int p,int l,int r){
					if(l==r) return tr[p].init(l);
					int mid=(l+r)>>1;
					build(p<<1,l,mid),build(p<<1|1,mid+1,r);
				}
				void modify(int p,int l,int r,int L,int R,const Info&V){
					if(L<=l&&r<=R) return tr[p].get(V);
					int mid=(l+r)>>1;
					tr[p].push(tr[p<<1],tr[p<<1|1]);
					if(L<=mid) modify(p<<1,l,mid,L,R,V);
					if(R>mid) modify(p<<1|1,mid+1,r,L,R,V);
				}
				Info query(int p,int l,int r,int X){
					if(l==r) return tr[p];
					int mid=(l+r)>>1;
					tr[p].push(tr[p<<1],tr[p<<1|1]);
					return X<=mid?query(p<<1,l,mid,X):query(p<<1|1,mid+1,r,X);
				}
			public:
				SegmentTree():n{}{tr=allocator.allocate(0);}
				void resize(int _n){allocator.deallocate(tr,n),tr=allocator.allocate((n=_n)<<2);}
				~SegmentTree(){allocator.deallocate(tr,n);}
				void build(){build(1,1,n);}
				void build(int _n){resize(_n),build(1,1,n);}
				void modify(int L,int R,const Info&V){modify(1,1,n,L,R,V);}
				Info query(int X){return query(1,1,n,X);}
			};
			template<typename Info,typename _Allocator>
			_Allocator SegmentTree<Info,Interval,Single,_Allocator>::allocator;
			template<typename Info,typename _Allocator>
			class SegmentTree<Info,Single,Interval,_Allocator>{
			private:
				static _Allocator allocator;
				int n;
				Info*tr;
				void build(int p,int l,int r){
					if(l==r) return tr[p].init(l);
					int mid=(l+r)>>1;
					build(p<<1,l,mid),build(p<<1|1,mid+1,r);
					tr[p].pull(tr[p<<1],tr[p<<1|1]);
				}
				void modify(int p,int l,int r,int X,const Info&V){
					if(l==r) return tr[p].get(V);
					int mid=(l+r)>>1;
					X<=mid?modify(p<<1,l,mid,X,V):modify(p<<1|1,mid+1,r,X,V);
					tr[p].pull(tr[p<<1],tr[p<<1|1]);
				}
				Info query(int p,int l,int r,int L,int R){
					if(L<=l&&r<=R) return tr[p];
					int mid=(l+r)>>1;
					if(L<=mid&&R>mid) return merge(query(p<<1,l,mid,L,R),query(p<<1|1,mid+1,r,L,R));
					else return L<=mid?query(p<<1,l,mid,L,R):query(p<<1|1,mid+1,r,L,R);
				}
			public:
				SegmentTree():n{}{tr=allocator.allocate(0);}
				void resize(int _n){allocator.deallocate(tr,n),tr=allocator.allocate((n=_n)<<2);}
				~SegmentTree(){allocator.deallocate(tr,n);}
				void build(){build(1,1,n);}
				void build(int _n){resize(_n),build(1,1,n);}
				void modify(int X,const Info&V){modify(1,1,n,X,V);}
				Info query(int L,int R){return query(1,1,n,L,R);}
			};
			template<typename Info,typename _Allocator>
			_Allocator SegmentTree<Info,Single,Interval,_Allocator>::allocator;
		}
	}
}
using namespace Default_Source;

/**
 * 建立 9 个变量,来表示每种平局的出现次数。
 * RRR PPP SSS
 * RPS PSR SRP
 * RSP PRS SPR
 * 可以列方程组:
 * x1+x4+x7=AR
 * x2+x5+x8=AP
 * x3+x6+x9=AS
 * x1+x6+x8=BR
 * x2+x4+x9=BP
 * x3+x5+x7=BS
 * x1+x5+x9=CR
 * x2+x6+x7=CP
 * x3+x4+x8=CS
 * 然后考虑乱消一波元,然后会发现一些美好的性质。
 * 当然我们为了方便可以先浅记一些量:
 * y1=x2-x1,y2=x3-x2
 * y3=x5-x4,y4=x6-x5
 * y5=x8-x7,y6=x9-x8
 * 然后等我搞亿哈哈:
 * BR-AR=y3+y4+y5
 * BP-AP=-y3+y6
 * BS-AS=-y4-y5-y6
 * CR-BR=-y4+y6
 * CP-BP=y3+y4-y5-y6
 * CS-BS=-y3+y5
 * CR-AR=y3+y5+y6
 * CP-AP=y4-y5
 * CS-AS=-y3-y4-y6
 * y6-y5=CP-AP-CR+BR
 * ......
 * 消不出来,我是垃圾。
 * 去问了下山哥,发现不要手动乱试,这个更适合用瞪眼法。
 * 比如 y1=x2-x1,会和 AR,AP,BR,Bp,CR,CP 的方程有关。
 * 然后把这俩坨放在一起,发现除了 x1,x2,剩下的未知数都相同,就能消掉。
 * 所以:
 * y1=(AP+BP+CP-AR-BR-CR)/3
 * y2=(AS+BS+CS-AP-BP-CP)/3
 * y3=(AP+BS+CR-AR-BP-CS)/3
 * y4=(AS+BR+CP-AP-BS-CR)/3
 * y5=(AP+BR+CS-AR-BS-CP)/3
 * y6=(AS+BP+CR-AP-BR-CS)/3
 * 啊非常滴不错
 * 然后我们考虑计数的部分。
 * 大概就是枚举 x1+x2+x3=n 的情况,然后贡献是一个多重排列。
 * 非常滴不错。
 * 然后大概就是拆拆贡献分到 x1,x2,x3 三个东西上面,接着大力 NTT 卷上。
 * y1=x2-x1,y2=x3-x2
 * y3=x5-x4,y4=x6-x5
 * y5=x8-x7,y6=x9-x8
 * =>
 * x2=x1+y1,x3=x1+y1+y2
 * x5=x4+y3,x6=x4+y3+y4
 * x8=x7+y5,x9=x7+y5+y6
*/

using ull=unsigned long long;
constexpr int N=1.5e6;
constexpr ull mod=998244353;
constexpr ull qpow(ull x,int pw){
	ull ret=1;
	for(;pw;pw>>=1,x=x*x%mod) if(pw&1) ret=ret*x%mod;
	return ret;
}

IO::Fast_InStream<> Input;
IO::Fast_OutStream<> Output;

int n,Ar,Ap,As,Br,Bp,Bs,Cr,Cp,Cs;
ull fac[N+1],inv[N+1];

signed main(){

	Input.read(n,Ar,Ap,As,Br,Bp,Bs,Cr,Cp,Cs);
	int y1=(Ap+Bp+Cp-Ar-Br-Cr)/3,y2=(As+Bs+Cs-Ap-Bp-Cp)/3,y3=(Ap+Bs+Cr-Ar-Bp-Cs)/3,y4=(As+Br+Cp-Ap-Bs-Cr)/3,y5=(Ap+Br+Cs-Ar-Bs-Cp)/3,y6=(As+Bp+Cr-Ap-Br-Cs)/3;

	fac[0]=inv[0]=1;
	for(int i=1;i<=n;++i) fac[i]=fac[i-1]*i%mod;
	inv[n]=qpow(fac[n],mod-2);
	for(int i=n-1;i;--i) inv[i]=inv[i+1]*(i+1ll)%mod;

	ull ans=0;
	for(int x1=0;x1<=Ar;++x1){
		for(int x4=0;x4<=Ar-x1;++x4){
			for(int x7=0;x7<=Ar-x1-x4;++x7){
				ans=(ans+fac[n]*inv[x1]%mod*inv[x1+y1]%mod*inv[x1+y1+y2]%mod*inv[x4]%mod*inv[x4+y3]%mod*inv[x4+y3+y4]%mod*inv[x7]%mod*inv[x7+y5]%mod*inv[x7+y5+y6])%mod;
			}
		}
	}
	Output.writeln(ans);

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3364kb

input:

2
2 0 0
1 1 0
1 0 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3296kb

input:

3
0 1 2
3 0 0
1 1 1

output:

6

result:

wrong answer 1st numbers differ - expected: '0', found: '6'