$\text{Describe}$

给定四种颜色($\text{a,b,c,d}$)的球各$a,b,c,d$个，求有多少种序列使得不存在任意长度为四的子段的颜色分别为$a,b,c,d$。

$\text{sol}$

首先考虑转化为求至少。

先求出全集大小。

显然可以构造四个$\text{EGF}$之后求积 具体地：

对于每一种颜色（这里以颜色$a$为例），构造组合类。

$\mathcal{A}=\{\mathcal{E},\circ,\circ\circ,\circ\circ\circ,\circ\circ\circ\circ,....\}$

其$\text{EGF}$
$$ A(z)=\sum_{i\ge0}\frac{1}{i!}z^i[i\le a] $$

全集是由这样的四个组合类拼接而成的。

那么全集大小
$$ |S|=[z^n]A(z)B(z)C(z)D(z) $$

直接$NTT$处理即可。

接下来考虑求至少出现$k > 1$个不合法的位置的排列数。

发现不合法序列本质上是上述四个组合类和一个新的组合类$\mathcal{P}$的拼接。

其中$\mathcal{P}=\{\circ{a}\circ b\circ c\circ d\}$ 即依次由颜色为$a,b,c,d$拼接而成的组合对象构成的大小为$1$组合类。

枚举组合类$\mathcal{P}$内组合对象大小函数的值与其他四个组合类拼接直接生成函数暴力草过，同理直接$NTT$即可。

最后套二项式反演即可。

复杂度$O(n^2\log n)$。

手 段 极 其 暴 力

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

namespace poly{
    #define int long long
    const int N = 4.2e6,mod = 998244353,G = 3,Gi = 332748118;
    int rev[N],c[N];
    inline void change(int f[],int len){
        for (int i = 0; i < len; i++){
            rev[i] = rev[i >> 1] >> 1;
            if (i & 1) rev[i] |= len >> 1;
        }
        for (int i = 0; i < len; i++)
            if (i < rev[i]) std::swap(f[i],f[rev[i]]);
    }
    inline int ffpow(int a,int b){
        int res = 1;
        for (;b;b >>= 1){
            if (b & 1) res = 1ll * res * a % mod;
            a = 1ll * a * a % mod;
        }
        return res;
    }
    inline void NTT(int f[],int len,int op){
        change(f,len);
        for (int mid = 1; mid < len; mid <<= 1){
            int wn = ffpow(G,(mod - 1) / (mid << 1));
            if (op == -1) wn = ffpow(wn,mod - 2);
            for (int j = 0; j < len; j += (mid << 1)){
                int cur = 1;
                for (int k = 0; k < mid; k++){
                    int u = f[j + k];
                    int t = cur * f[j + k + mid] % mod;
                    f[j + k] = (u + t) % mod;
                    f[j + k + mid] = (u - t + mod) % mod;
                    cur = (cur * wn) % mod;
                }
            }
        }
        int inv = ffpow(len,mod - 2);
        if (op == -1)
            for (int i = 0; i < len; i++)
                f[i] = (f[i] * inv) % mod;
    }
}
namespace wxy{
    #define int long long
    const int N = 4.2e6,mod = 998244353;
    int a,b,c,d,n,m;
    int A[N],B[N],C[N],D[N],P[N],f[N],ret[N],res[N],fac[N],invfac[N];
    int rr[N];
    inline void init(){
        fac[0]=invfac[0]=invfac[1]=1;
        for(int i=1;i<=1005;i++)fac[i]=(long long)fac[i-1]*i%mod;
        for(int i=2;i<=1005;i++)invfac[i]=(long long)(mod-mod/i)*invfac[mod%i]%mod;
        for(int i=2;i<=1005;i++)invfac[i]=(long long)invfac[i-1]*invfac[i]%mod;
    }
    inline int mul(int a,int b){return a * b % mod;}
    void main(){
        init();
        std::cin >> n >> a >> b >> c >> d;
        int limit = 1; while (limit < 2015) limit <<= 1;
        for (int i = 0; i <= a; i++) A[i] = invfac[i];
        for (int i = 0; i <= b; i++) B[i] = invfac[i];
        for (int i = 0; i <= c; i++) C[i] = invfac[i];
        for (int i = 0; i <= d; i++) D[i] = invfac[i];
        poly::NTT(A,limit,1); poly::NTT(B,limit,1); 
        poly::NTT(C,limit,1);poly::NTT(D,limit,1);
        for (int i = 0; i < limit; i++) rr[i] = A[i] * B[i] % mod * C[i] % mod * D[i] % mod;
        poly::NTT(rr,limit,-1); int sum = mul(rr[n],fac[n]);
        int cnt = std::min(a,std::min(std::min(b,c),d));
        memset(P,0,sizeof P);
        poly::NTT(P,limit,1);
        f[0] = sum;
        for (int i = 1; i <= cnt; i++){
            poly::NTT(A,limit,-1); poly::NTT(B,limit,-1); 
            poly::NTT(C,limit,-1); poly::NTT(D,limit,-1);
            poly::NTT(P,limit,-1);
            A[a + 1 - i] = 0; B[b + 1 - i] = 0;
            C[c + 1 - i] = 0; D[d + 1 - i] = 0;
            P[i] = invfac[i];
            P[i - 1] = 0;
            poly::NTT(P,limit,1);
            poly::NTT(A,limit,1); poly::NTT(B,limit,1); 
            poly::NTT(C,limit,1); poly::NTT(D,limit,1); 
            for (int j = 0; j < limit; j++) res[j] = mul(mul(mul(mul(P[j],A[j]),B[j]),C[j]),D[j]);
            poly::NTT(res,limit,-1);
            f[i] = mul(res[n - 3 * i],fac[n - 3 * i]);
        }
        int ans = 0;
        for (int i = 0; i <= cnt; i++){
            if (i % 2 == 0){
                ans = (ans + f[i]) % mod;
            }else{
                ans = (ans - f[i] + mod) % mod;
            }
        }
        std::cout << ans;
    }
}signed main(){wxy::main();return 0;}