QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#217512 | #6325. Peaceful Results | CharlieVinnie | RE | 154ms | 45656kb | C++17 | 10.7kb | 2023-10-16 22:16:30 | 2023-10-16 22:16:30 |
Judging History
answer
#include "bits/stdc++.h"
#ifdef DEBUG
#include "PrettyDebug.hpp"
#else
#define debug(...) [](auto...){}(__VA_ARGS__)
#endif
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
#define assume(expr) ((!!(expr))||(exit((fprintf(stderr,"Assumption Failed: %s on Line %d\n",#expr,__LINE__),-1)),false))
#define range basic_string_view
using namespace std; typedef long long ll;
namespace Math::ZPoly
{
using LL=long long;
constexpr int MOD=998244353,G=114514,MAXN=1<<21;
int qpow(LL a,LL b) { LL r=1;for(;b;(b&1)?r=r*a%MOD:0,a=a*a%MOD,b>>=1);return r; }
int madd(int x) { return x; }
int mmul(int x) { return x; }
int msub(int x,int y) { return (x-=y)<0?x+=MOD:x; }
int mdiv(int x,int y) { return (LL)x*qpow(y,MOD-2)%MOD; }
template<typename ...Args>int madd(int x,Args ...y) { return (x+=madd(y...))>=MOD?x-=MOD:x; }
template<typename ...Args>int mmul(int x,Args ...y) { return (LL)x*mmul(y...)%MOD; }
class PolyTemp
{
private:
static PolyTemp V;
int g[MAXN+5],c1[MAXN+5],c2[MAXN+5];
PolyTemp()
{
int nn=1<<(__lg(MAXN-1)+1);
for(int i=2;i<=nn;i<<=1)
{
g[i>>1]=1;
int gn=qpow(G,(MOD-1)/i);
for(int j=(i>>1)+1;j<i;j++) g[j]=mmul(g[j-1],gn);
}
}
friend class Polynomial;
}PolyTemp::V{};
// A class for polynomials in F_{MOD}.
class Polynomial: public vector<int>
{
private:
static constexpr int NTT_LIM=100;
static constexpr auto &g=PolyTemp::V.g,&c1=PolyTemp::V.c1,&c2=PolyTemp::V.c2;
using BaseT=vector<int>;
#define NTT_CHECK(n,m) (n+m<=NTT_LIM || 1ll*n*m<5ll*(n+m)*__lg(n+m))
#define EXTEND(n) (1<<(__lg((n)-1)+1))
#define MCPY(a,b,s) memcpy(a,b,(s)*sizeof(int))
#define MSET(a,b,s) memset(a,b,(s)*sizeof(int))
public:
static void DIT(int *a,int len)
{
for(int i=len>>1;i;i>>=1)
for(int j=0;j<len;j+=i<<1)
for(int k=0,x,y;k<i;k++)
x=a[j+k],y=a[i+j+k],a[j+k]=madd(x,y),a[i+j+k]=mmul(g[i+k],msub(x,y));
}
static void DIF(int *a,int len)
{
for(int i=1;i<len;i<<=1)
for(int j=0;j<len;j+=i<<1)
for(int k=0,x,y;k<i;k++)
x=a[j+k],y=mmul(g[i+k],a[i+j+k]),a[j+k]=madd(x,y),a[i+j+k]=msub(x,y);
int x=qpow(len,MOD-2);
for(int i=0;i<len;i++) a[i]=mmul(a[i],x);
reverse(a+1,a+len);
}
private:
static void __polyinv(const int *a,int *b,int len)
{
if(len==1) return b[0]=qpow(a[0],MOD-2),void();
__polyinv(a,b,(len+1)>>1);
int nn=EXTEND(len<<1);
MCPY(c1,a,len);
MSET(b+len,0,nn-len);
MSET(c1+len,0,nn-len);
DIT(b,nn),DIT(c1,nn);
for(int i=0;i<nn;i++) b[i]=mmul(b[i],msub(2,mmul(b[i],c1[i])));
DIF(b,nn),MSET(b+len,0,nn-len);
}
static void __polyln(const int *a,int *b,int len)
{
__polyinv(a,b,len);
for(int i=1;i<len;i++) c1[i-1]=mmul(i,a[i]);
int nn=EXTEND(len<<1);
MSET(b+len,0,nn-len);
MSET(c1+len,0,nn-len);
DIT(b,nn),DIT(c1,nn);
for(int i=0;i<nn;i++) b[i]=mmul(b[i],c1[i]);
DIF(b,nn),MSET(b+len,0,nn-len);
for(int i=len-1;i>0;i--) b[i]=mdiv(b[i-1],i);
b[0]=0;
}
static void __polyexp(const int *a,int *b,int l,int r)
{
if(l==r-1) return b[l]=(l?mdiv(b[l],l):1),void();
int len=r-l,mid=(l+r)>>1;
__polyexp(a,b,l,mid);
for(int i=0;i<len;i++) c1[i]=a[i];
MCPY(c2,b+l,mid-l);
MSET(c2+mid-l,0,r-mid);
if(NTT_CHECK(len,len)) for(int i=len-1;i>=0;i--)
{
int tmp=0;
for(int j=0;j<=i;j++)
tmp=madd(tmp,mmul(c1[j],c2[i-j]));
c1[i]=tmp;
}
else
{
DIT(c1,len),DIT(c2,len);
for(int i=0;i<len;i++) c1[i]=mmul(c1[i],c2[i]);
DIF(c1,len);
}
for(int i=mid;i<r;i++) b[i]=madd(b[i],c1[i-l]);
__polyexp(a,b,mid,r);
}
public:
using BaseT::BaseT;
using BaseT::operator=;
int operator ()(int x)const
{
int res=0,sz=size();
for(int i=sz-1;i>=0;i--)
res=madd(mmul(res,x),(*this)[i]);
return res;
}
#define DEF_OP(op) \
Polynomial operator op(const Polynomial &p)const \
{ return Polynomial(*this)op##=p; } \
Polynomial &operator op##=(const Polynomial &p)
DEF_OP(+)
{
int n=size(),m=p.size();
if(n<m) resize(m);
for(int i=0;i<m;i++)
(*this)[i]=madd((*this)[i],p[i]);
return *this;
}
DEF_OP(-)
{
int n=size(),m=p.size();
if(n<m) resize(m);
for(int i=0;i<m;i++)
(*this)[i]=msub((*this)[i],p[i]);
return *this;
}
DEF_OP(*)
{
int n=size(),m=p.size(),sz=n+m-1;
if(!n || !m) return clear(),*this;
resize(sz);
if(NTT_CHECK(n,m))
{
MCPY(c1,data(),n);
MSET(c2,0,sz);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
c2[i+j]=madd(c2[i+j],mmul(c1[i],p[j]));
MCPY(data(),c2,sz);
}
else if(this==addressof(p))
{
int nn=EXTEND(sz);
MCPY(c1,data(),n);
MSET(c1+n,0,nn-n);
DIT(c1,nn);
for(int i=0;i<nn;i++) c1[i]=mmul(c1[i],c1[i]);
DIF(c1,nn);
MCPY(data(),c1,sz);
}
else
{
int nn=EXTEND(sz);
MCPY(c1,data(),n),MCPY(c2,p.data(),m);
MSET(c1+n,0,nn-n),MSET(c2+m,0,nn-m);
DIT(c1,nn),DIT(c2,nn);
for(int i=0;i<nn;i++) c1[i]=mmul(c1[i],c2[i]);
DIF(c1,nn);
MCPY(data(),c1,sz);
}
return *this;
}
DEF_OP(/) { return (*this)*=p.inv(); }
DEF_OP(%) { return (*this)=divr(*this,p).second; }
#undef DEF_OP
Polynomial &operator *=(int k)
{ for(auto &i: *this) i=mmul(i,k); return *this; }
friend Polynomial operator *(const Polynomial &p,int k)
{ return Polynomial(p)*=k; }
friend Polynomial operator *(int k,const Polynomial &p)
{ return Polynomial(p)*=k; }
friend Polynomial derivative(const Polynomial &p)
{
int sz=p.size();
Polynomial q(sz-1);
for(int i=1;i<sz;i++) q[i-1]=mmul(p[i],i);
return q;
}
friend Polynomial integral(const Polynomial &p)
{
int sz=p.size();
Polynomial q(sz+1);
for(int i=1;i<sz;i++) q[i+1]=mdiv(p[i],i+1);
return q;
}
Polynomial inv()const
{
if(empty() || front()==0) throw runtime_error("[x^0]f(x)=0, f(x)^-1 doesn't exist.\n");
int sz=size(),nn=1<<(__lg((sz<<1)-1)+1);
Polynomial q(nn);
__polyinv(data(),q.data(),sz);
return q.resize(sz),q;
}
friend Polynomial ln(const Polynomial &p)
{
if(p.empty() || p[0]!=1) throw runtime_error("[x^0]f(x)!=1, ln(f(x)) doesn't exist.\n");
int sz=p.size(),nn=1<<(__lg((sz<<1)-1)+1);
Polynomial q(nn);
__polyln(p.data(),q.data(),sz);
return q.resize(sz),q;
}
friend Polynomial exp(const Polynomial &p)
{
if(p.empty()) return Polynomial{1};
if(p[0]!=0) throw runtime_error("[x^0]f(x)!=0, exp(f(x)) doesn't exist.\n");
static int c[MAXN];
int sz=p.size(),nn=1<<(__lg(sz-1)+1);
for(int i=0;i<sz;i++) c[i]=mmul(i,p[i]);
Polynomial q(nn);
__polyexp(c,q.data(),0,nn);
return q.resize(sz),q;
}
friend pair<Polynomial,Polynomial> divr(const Polynomial &f,const Polynomial &g)
{
if(f.size()<g.size()) return make_pair(Polynomial{0},f);
int n=f.size()-1,m=g.size()-1;
Polynomial fr(n+1),gr(m+1);
for(int i=0;i<=n;i++) fr[i]=f[n-i];
for(int i=0;i<=m;i++) gr[i]=g[m-i];
fr.resize(n-m+1),gr.resize(n-m+1),fr*=gr.inv();
fr.resize(n-m+1),reverse(fr.begin(),fr.end());
gr=f-fr*g,gr.resize(m);
return make_pair(fr,gr);
}
#undef NTT_CHECK
#undef EXTEND
#undef MCPY
#undef MSET
};
} // namespace ZPoly
constexpr int mod=998244353;
inline int qpow(int x,int y){int res=1;while(y){if(y&1)res=1ll*res*x%mod;x=1ll*x*x%mod;y>>=1;}return res;}
signed main(){
atexit([](){cerr<<"Time = "<<clock()<<" ms"<<endl;});
int n,Ar,As,Ap,Br,Bs,Bp,Cr,Cs,Cp; cin>>n>>Ar>>As>>Ap>>Br>>Bs>>Bp>>Cr>>Cs>>Cp;
// RRR SSS PPP RSP SPR PRS RPS PSR SRP
ll co[9][10]={
{1,0,0,1,0,0,1,0,0,Ar},
{0,1,0,0,1,0,0,0,1,As},
{0,0,1,0,0,1,0,1,0,Ap},
{1,0,0,0,0,1,0,0,1,Br},
{0,1,0,1,0,0,0,1,0,Bs},
{0,0,1,0,1,0,1,0,0,Bp},
{1,0,0,0,1,0,0,1,0,Cr},
{0,1,0,0,0,1,1,0,0,Cs},
{0,0,1,1,0,0,0,0,1,Cp}
};
ll _co[9][10]; memcpy(_co,co,sizeof(co));
For(i,0,6){
int mx=0,p=1e9;
For(j,i,8){
int t=1e9; For(k,0,8) if(co[j][k]) { t=k; break; }
if(t<p) p=t,mx=j;
}
assert(p!=1e9);
assert(co[mx][p]);
if(mx!=i) swap(co[i],co[mx]);
assert(co[i][p]);
For(j,0,8) if(j!=i&&co[j][p]){
ll r=co[j][p]; For(k,0,9) co[j][k]=co[j][k]*co[i][p]-r*co[i][k];
}
For(_,0,8) debug(co[_]);; debug('\n');
}
For(i,0,8) debug(co[i]);
int a[9]={0};
For(i,0,6){
int p=0; while(!co[i][p]) p++;; if(co[i][9]%co[i][p]!=0) cout<<"0\n",exit(0);
a[p]=co[i][9]/co[i][p];
}
debug(a);
For(i,0,8){
int t=0; For(j,0,8) t=(t+1ll*_co[i][j]*a[j])%mod;; debug(i,t,_co[i][9]); assert((t+mod)%mod==_co[i][9]);
}
vector<int> cp(n*2+1); cp[0]=1; For(i,1,n*2) cp[i]=1ll*cp[i-1]*i%mod;
vector<int> ci(n*2+1); ci[n*2]=qpow(cp[n*2],mod-2); Rev(i,n*2-1,0) ci[i]=1ll*ci[i+1]*(i+1)%mod;
Math::ZPoly::Polynomial f(n+1),g(n+1),h(n+1);
int m0=min({a[0],a[1],a[2]}),m1=min({a[3],a[4],a[5]}),m2=min({a[6],a[7],a[8]});
For(i,0,n) f[i]=1ll*ci[a[0]-m0+i]*ci[a[1]-m0+i]%mod*ci[a[2]-m0+i]%mod;
For(i,0,n) g[i]=1ll*ci[a[3]-m1+i]*ci[a[4]-m1+i]%mod*ci[a[5]-m1+i]%mod;
For(i,0,n) h[i]=1ll*ci[a[6]-m2+i]*ci[a[7]-m2+i]%mod*ci[a[8]-m2+i]%mod;
// int ans=0; For(i,0,n) For(j,0,n) For(k,0,n) if(i+j+k==m0+m1+m2) ans=(ans+1ll*f[i]*g[j]%mod*h[k])%mod;
// cout<<1ll*ans*cp[n]%mod<<'\n';
cout<<1ll*(f*g*h)[m0+m1+m2]*cp[n]%mod<<'\n';
return 0;
}
// START TYPING IF YOU DON'T KNOW WHAT TO DO
// STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING
// CONTINUE, NON-STOPPING, FOR CHARLIEVINNIE
// Started Coding On: October 16 Mon, 21 : 07 : 54
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 14224kb
input:
2 2 0 0 1 1 0 1 0 1
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 10ms
memory: 12656kb
input:
3 0 1 2 3 0 0 1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 154ms
memory: 45656kb
input:
333333 111111 111111 111111 111111 111111 111111 111111 111111 111111
output:
383902959
result:
ok 1 number(s): "383902959"
Test #4:
score: -100
Runtime Error
input:
1500000 500000 500000 500000 500000 500000 500000 500000 500000 500000