比赛 五一大礼包 评测结果
题目名称 孤独摇滚! 最终得分 0
用户昵称 HXF 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2026-05-04 15:35:08
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define pir pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
inline int re()
{
    int f=1,num=0;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
    return num*f;
}
int T;
void clear();
const int N=3010,MOD=998244353;
int n;
int a[10];
int C[N][N];
int fac[N],ny[N];
void add(int &a,int b){a=(a+b>=MOD?a+b-MOD:a+b);}
int qpow(int a,int b=MOD-2)
{
    int mul=1;
    while(b)
    {
        if(b&1) mul=mul*a%MOD;
        b>>=1;
        a=a*a%MOD;
    }
    return mul;
}
const int ntt=3,invntt=qpow(3),invn=qpow(2048);
void init()
{
    C[0][0]=1;
    for(int i=1;i<=N-5;i++)
    {
        C[i][0]=1;
        for(int j=1;j<=i;j++)
        {
            add(C[i][j],C[i-1][j]);
            add(C[i][j],C[i-1][j-1]);
        }
    }
    fac[0]=ny[0]=1;for(int i=1;i<=N-5;i++) fac[i]=fac[i-1]*i%MOD;
    ny[N-5]=qpow(fac[N-5]);
    for(int i=N-6;i>=1;i--) ny[i]=ny[i+1]*(i+1)%MOD;
    return;
}
int f[N],g[N],tran[N];
void NTT(int *f,int n,bool flag)
{
    for(int i=0;i<n;i++) tran[i]=(tran[i>>1]>>1)|((i&1)?1024:0);
    for(int i=0;i<n;i++) if(i<tran[i]) swap(f[i],f[tran[i]]);
    for(int len=2;len<=n;len<<=1)
    {
        int buf=(flag?qpow(invntt,(MOD-1)/len):qpow(ntt,(MOD-1)/len));
        for(int p=0;p<n;p+=len)
        {
            int now=1;
            for(int l=p;l<p+(len>>1);l++)
            {
                int tmp=now*f[l+(len>>1)]%MOD;
                f[l+(len>>1)]=(f[l]-tmp+MOD)%MOD;
                add(f[l],tmp);
                now=now*buf%MOD;
            }
        }
    }
    if(flag) for(int i=0;i<n;i++) f[i]=f[i]*invn%MOD;
    return;
}
int calc(int s,int a,int b,int c,int d)
{
    int up=2048;
    for(int i=0;i<=a;i++) f[i]=ny[i];for(int i=a+1;i<up;i++) f[i]=0;
    NTT(f,up,0);
    for(int i=0;i<=b;i++) g[i]=ny[i];for(int i=b+1;i<up;i++) g[i]=0;NTT(g,up,0);for(int i=0;i<up;i++) f[i]=f[i]*g[i]%MOD;
    for(int i=0;i<=c;i++) g[i]=ny[i];for(int i=c+1;i<up;i++) g[i]=0;NTT(g,up,0);for(int i=0;i<up;i++) f[i]=f[i]*g[i]%MOD;
    for(int i=0;i<=d;i++) g[i]=ny[i];for(int i=d+1;i<up;i++) g[i]=0;NTT(g,up,0);for(int i=0;i<up;i++) f[i]=f[i]*g[i]%MOD;
    NTT(f,up,1);
    return f[s]*fac[s]%MOD;
}
void work()
{
    clear();
    n=re();
    for(int i=1;i<=4;i++) a[i]=re();
    int ans=0;
    for(int i=0;i*4<=n;i++)
    {
        if(i>min({a[1],a[2],a[3],a[4]})) break;
        int res=C[i+n-4*i][i]*((i&1)?MOD-1:1)%MOD;
        res=res*calc(n-4*i,a[1]-i,a[2]-i,a[3]-i,a[4]-i)%MOD;
        // cout<<"calc "<<i<<' '<<n-4*i<<' '<<a[1]-i<<' '<<a[2]-i<<' '<<a[3]-i<<' '<<a[4]-i<<' '<<calc(n-4*i,a[1]-i,a[2]-i,a[3]-i,a[4]-i)<<endl;
        add(ans,res);
    }
    printf("%lld\n",ans);
    return;
}
signed main()
{
    init();
    T=1;
    while(T--) work();
    return 0;
}
void clear()
{
    return;
}