QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#217512#6325. Peaceful ResultsCharlieVinnieRE 154ms45656kbC++1710.7kb2023-10-16 22:16:302023-10-16 22:16:30

Judging History

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

  • [2023-10-16 22:16:30]
  • 评测
  • 测评结果:RE
  • 用时:154ms
  • 内存:45656kb
  • [2023-10-16 22:16:30]
  • 提交

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

output:


result: