传送门

那啥，其实。。。cxk是我（b站上的）最喜欢的偶像。

话说没有朴素的$O(n^3)$容斥+$DP$的题解诶。。。

一脸套路容斥。枚举有$i$个不合法组，容斥系数$(-1)^i$，$C_{n-3i}^i$选位置，剩下了$a-i$、$b-i$、$c-i$、$d-i$个人和$n-4i$个位置，要给他们任意安排位置。

直接组合数学不太会做的样子，咱也不会$NTT$和生成函数，考虑$DP$。

设$f(i,j)$为前$i$种爱好放了$j$个人的方案数。

枚举每种爱好有多少人，插进当前的队伍里：$f(i,j)=\sum\limits_{k=0}^{a/b/c/d}f(i-1,j-k)\times C_j^{j-k}$

套路容斥：$ans=\sum\limits_{i=0}^{\min\{\frac{n}{4},a,b,c,d\}}(-1)^iC_{n-3i}^if(4,n-4i)$。注意每个$i$的$a,b,c,d$都不一样，需要重新$DP$。

复杂度$O(n^3)$，然而实际上常数极小甚至（应该）到不了$\dfrac{1}{10}$。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 1005
#define inf 0x3f3f3f3f

const int mod = 998244353;

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
int f[maxn],c[maxn][maxn],a[5];
inline int calc(int n){
    memset(f,0,sizeof f);
    f[0]=1;
    for(register int i=1,sum=0;i<=4;++i){
        sum=min(sum+a[i],n);
        for(register int j=sum;j;--j)
            for(register int k=min(j,a[i]);k;--k)
                (f[j]+=1ll*f[j-k]*c[j][j-k]%mod)%=mod;
        --a[i];
    }
    return f[n];
}
inline long long pow1(int x){return x&1?-1ll:1ll;}
int main(){
    int n=read(),mi=n>>2,ans=0;
    for(register int i=1;i<=4;++i)mi=min(a[i]=read(),mi);
    c[0][0]=1;
    for(register int i=1;i<=n;++i){
        c[i][0]=1;
        for(register int j=1;j<=i;++j)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
    }
    for(register int i=0;i<=mi;++i)(ans+=pow1(i)*c[n-i*3][i]*calc(n-(i<<2))%mod)%=mod;
    printf("%d\n",(ans+mod)%mod);
}