QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#288670 | #6325. Peaceful Results | qL | WA | 0ms | 3364kb | C++14 | 13.0kb | 2023-12-23 11:14:32 | 2023-12-23 11:14:32 |
Judging History
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'