Submission #35750498

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN=1e4+10,LIM=1e4,mod=998244353;
int mypow(int a,int n){
    if(!n)return 1;
    int tmp=mypow(a,n/2);tmp=1ll*tmp*tmp%mod;
    if(n&1)tmp=1ll*tmp*a%mod;return tmp;
}
int myinv(int a){return mypow(a,mod-2);}
int fact[MAXN],factinv[MAXN];
int C(int n,int m){
    if(n<m || m<0)return 0;
    return 1ll*fact[n]*factinv[m]%mod*factinv[n-m]%mod;
}
void add(int& x,int y){x=(x+y)%mod;}
void sub(int& x,int y){x=(x-y+mod)%mod;}
int P(int x){return (odd(x))?(mod-1):(1);}
//
int n,r1,r2,c1,c2,ans;
int pw[MAXN],piv[MAXN];
struct Poly{
    vector<ll>a;
    int n;
    Poly(int N=0){a.resize(N+1,0);n=N;}
    void split(int N,int mode=0){if(mode || (n>N) ){a.resize(N+1,0);n=N;}}
    void output(){rep(i,0,n)cout<<a[i]<<" ";cout<<"\n";}
};
namespace NTT{
    const int MAXN=1e5;
    ll f[MAXN],g[MAXN],h[MAXN],rev[MAXN],N;
    void change(ll* f,int N){rep(i,0,N-1)if(i<rev[i])swap(f[i],f[rev[i]]);}
    void DFT(ll* f,int N,ll rev){
        change(f,N);
        for(int len=2;len<=N;len<<=1){
            ll step=mypow(rev,(mod-1)/len);
            for(int i=0;i<N;i+=len){
                ll w=1;
                rep(j,0,len/2-1){
                    ll x=f[i+j],y=f[i+j+len/2];
                    f[i+j]=(x+w*y)%mod;
                    f[i+j+len/2]=(x-w*y%mod+mod)%mod;
                    w=1ll*w*step%mod;
                }
            }
        }
    }
    Poly ntt(Poly F,Poly G){
        int n=F.n,m=G.n;N=1;
        while(N<=(n+m))N<<=1;
        rep(i,0,N-1)f[i]=g[i]=h[i]=0;
        rep(i,0,N-1){
            rev[i]=rev[i>>1]>>1;
            if(i&1)rev[i]|=(N>>1);
        }
        rep(i,0,n)f[i]=F.a[i];
        rep(i,0,m)g[i]=G.a[i];
        DFT(f,N,3);DFT(g,N,3);
        rep(i,0,N-1)h[i]=1ll*f[i]*g[i]%mod;
        DFT(h,N,myinv(3));
        ll inv=myinv(N);
        rep(i,0,N-1)h[i]=1ll*h[i]*inv%mod;
        Poly ret(n+m);
        rep(i,0,n+m)ret.a[i]=h[i];
        return ret;
    }
};
Poly operator*(Poly p1,Poly p2){return NTT::ntt(p1,p2);}
//
int main(){
    fact[0]=1;rep(i,1,LIM)fact[i]=1ll*fact[i-1]*i%mod;
    factinv[LIM]=myinv(fact[LIM]);per(i,LIM-1,0)factinv[i]=1ll*factinv[i+1]*(i+1)%mod;
    
    pw[0]=1;rep(i,1,LIM)pw[i]=pw[i-1]*2%mod;
    piv[LIM]=myinv(pw[LIM]);per(i,LIM-1,0)piv[i]=piv[i+1]*2%mod;

    //
    cin>>n;
    rep(i,1,n){
        int r;cin>>r;
        if(r==1)r1++;else if(r==2)r2++;
    }
    rep(i,1,n){
        int c;cin>>c;
        if(c==1)c1++;else if(c==2)c2++;
    }
    if(r1+2*r2 != c1+2*c2){cout<<"0";return 0;}
    Poly F(n),G(n),H(n);
    int m=min(r2,c2);
    rep(i,0,m)F.a[i]=1ll*C(r2,i)*C(c2,i)%mod*fact[i]%mod*fact[r2-i]%mod*fact[c2-i]%mod*piv[r2+c2-2*i]%mod;
    rep(i,0,m)G.a[i]=1ll*P(i)*pw[i]%mod*factinv[i]%mod;
    rep(i,0,m)H.a[i]=1ll*fact[c1+2*(c2-i)]*factinv[r2-i]%mod*factinv[c2-i]%mod;

    F=F*G;
    rep(i,0,m)F.a[i]=1ll*F.a[i]*H.a[i]%mod,add(ans,F.a[i]);
    
    cout<<ans;

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int mypow(int, int)’:
./Main.cpp:19:5: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   19 |     if(n&1)tmp=1ll*tmp*a%mod;return tmp;
      |     ^~
./Main.cpp:19:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
   19 |     if(n&1)tmp=1ll*tmp*a%mod;return tmp;
      |                              ^~~~~~

Judge Result