Submission #38831628

---

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=(1<<19)+10,mod=998244353,INF=1e9;
ll mypow(ll a,ll n){
    if(!n)return 1;
    ll tmp=mypow(a,n/2);tmp=tmp*tmp%mod;
    if(n&1)tmp=tmp*a%mod;return tmp;
}
ll myinv(ll a){return mypow(a,mod-2);}
void add(ll& x,ll v){x=(x+v)%mod;}
void sub(ll& x,ll v){x=(x+mod-v)%mod;}
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{
    ll f[MAXN],g[MAXN],h[MAXN],rev[MAXN],N;
    ll W[MAXN];
    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);
        ll S=mypow(rev,(mod-1)/N);
        W[0]=1;rep(i,1,N-1)W[i]=W[i-1]*S%mod;
        for(int len=2;len<=N;len<<=1){
            for(int i=0;i<N;i+=len){
                rep(j,0,len/2-1){
                    ll w=W[j*(N/len)];
                    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;
                }
            }
        }
    }
    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){
    if(p1.n<p2.n)swap(p1,p2);
    rep(i,0,p2.n)add(p1.a[i],p2.a[i]);
    return p1;
}
Poly operator*(int c,Poly p){
    rep(i,0,p.n)p.a[i]=1ll*c*p.a[i]%mod;
    return p;
}
Poly operator*(Poly p1,Poly p2){return NTT::ntt(p1,p2);}
//
namespace CFM{
const int MAXN=1e5+10,LIM=1e5;
ll fact[MAXN],invfact[MAXN];
ll f[MAXN],g[MAXN];

int p[4],t;

Poly pre_calc(int a,int b,int c){
    int A=(b-a)/2,B=(c-a)/2;
    Poly F(t),G(t);
    rep(i,0,t-B)F.a[i]=invfact[i]*invfact[i+A]%mod*invfact[i+B]%mod;
    rep(i,B,t)G.a[i]=invfact[i]*invfact[i-A]%mod*invfact[i-B]%mod;
    F=F*G;
    rep(i,1,t)F.a[i]=F.a[i]*mypow(fact[i],3)%mod;
    return F;
}
void solve(int l,int r){
    if(l==r)return;
    int mid=(l+r)>>1;
    solve(l,mid);

    Poly F(mid-l+1),G(r-l);
    rep(i,l,mid)F.a[i-l+1]=f[i];
    rep(i,1,r-l)G.a[i]=g[i];
    F=F*G;

    rep(i,mid+1,r)add(f[i],(mod-1)*F.a[i-l+1]%mod);

    solve(mid+1,r);
}
void main(){
    fact[0]=1;rep(i,1,LIM)fact[i]=fact[i-1]*i%mod;
    invfact[LIM]=myinv(fact[LIM]);per(i,LIM-1,0)invfact[i]=invfact[i+1]*(i+1)%mod;

    cin>>p[1]>>p[2]>>p[3]>>t;
    sort(p+1,p+4);
    if((p[1]==p[3])){
        if(t)cout<<"0";
        else cout<<"1";
        return;
    }else if(!t){cout<<"0";return;}

    Poly F=pre_calc(p[1],p[2],p[3]),G=pre_calc(0,0,0);

    rep(i,1,t)add(f[i],F.a[i]*(mod-1)%mod),add(g[i],G.a[i]);


    solve(0,t);

    ll ans=f[t]*(mod-1)%mod;

    cout<<ans*myinv(mypow(8,t))%mod;
}  
};
int main(){
    CFM::main();

    return 0;
}

Submission Info

Compile Error

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

Judge Result