[bzoj5510]唱跳rap和篮球

显然答案可以理解为有（不是仅有）0对情况-1对情况+2对情况……

考虑这个怎么计算，先计算这t对情况的位置，有c(n-3t,t)种情况（可以理解为将这4个点缩为1个，然后再从中选t个位置），然后相当于在剩下n-4t的位置上摆上4种东西，且每种东西有数量限制（ai-t个）。

这个东西dp一下即可，用f[i][j]表示选了前i中东西，用了j个位置的方案数，则有转移$f[i][j]=\sum\limits_{ai-t\geq j-k\geq 0,j\geq 0}f[i-1][k]\cdot c(n-4t-k,n-4t-j)$，这样的时间复杂度是$o(n^{3})$（然后卡卡常就过去了，仅20s），无法通过。

显然发现可以用fft优化，具体操作将c(i,j)以j为第一维预处理，则第一维就不与k有关了，而第二位与fft的形式很像，只要注意删掉不合法的f状态（置为0）即可，总时间复杂度为$o(n^{2}log_{n})$

#include<bits/stdc++.h>
using namespace std;
#define mod 998244353
int n,ans,a[11],c[1001][1001],f[11][1001];
int main(){
    scanf("%d",&n);
    for(int i=0;i<4;i++)scanf("%d",&a[i]);
    for(int i=0;i<=n;i++)c[i][i]=c[i][0]=1;
    for(int i=2;i<=n;i++)
        for(int j=1;j<i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
    for(int i=0;i<=n/4;i++){
        memset(f,0,sizeof(f));
        for(int j=0;j<=a[0]-i;j++)f[0][j]=c[n-4*i][j];
        for(int j=1;j<4;j++)
            for(int k=0;k<=n-4*i;k++)
                for(int l=max(0,k-a[j]+i);l<=k;l++)
                    f[j][k]=(f[j][k]+1LL*f[j-1][l]*c[n-4*i-l][n-4*i-k])%mod;
        ans=(ans+1LL*(1-i%2*2+mod)*f[3][n-4*i]%mod*c[n-3*i][i])%mod;
    }
    printf("%d",ans);
}