组合容斥问题。
定义 \(\operatorname{sum}(i)\) 为至少有 \(i\) 组人会讨论的方案数。
那么最终答案就为 \(\sum\limits_{i=0}(-1)^i\times \operatorname{sum}(i)\)。
在 \(n\) 个人中选 \(m\) 组人讨论的方案数为 \(\dbinom{n-3\times m}{m}\),相当于将 \(m\) 组 \(4\) 个人捆绑起来当成一个人来算。
接下来的 \(n,a,b,c,d\) 均为扣除 \(m\) 组人后的数量。
考虑 \(n\) 个人的排列方法,容易得到如下式子:
\[\sum\limits_{i=0}^{\min(n,a)}\dbinom{n}{i}\cdot \sum\limits_{j=0}^{\min(n-i,b)}\dbinom{n-i}{j}\cdot\sum\limits_{k=0}^{\min(c,n-i-j)}[i+j+k\ge n-d]\dbinom{n-i-j}{k}
\]
直接算 \(O(n^3)\),用前缀和优化掉最后一个 \(\sum\) 后是 \(O(n^2)\)。需要降到 \(O(n)\)。
考虑枚举前两种人被选的个数,然后 \(a,b\) 和 \(c,d\) 分别用前缀和 \(O(1)\)算,式子如下:
\[\sum\limits_{mid=\max(0,n-c-d)}^{\min(n,a+b)}\dbinom{n}{mid}\left[\sum\limits_{i=\max(0,mid-b)}^{\min(mid,a)}\dbinom{mid}{i}\cdot \sum\limits_{\max(0,n-mid-d)}^{\min(c,n-mid)}\dbinom{n-mid}{j}\right]
\]
上下界一定要卡好,复杂度 \(O(n)\)。总复杂度 \(O(n^2)\)。
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000+5,mod=998244353;
ll n,a,b,c,d,C[N][N],sum[N][N];
ll get(int l,int r,int x){
l=max(l,0);
return (sum[x][r]-(l>0?sum[x][l-1]:0)+mod)%mod;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>a>>b>>c>>d;
for(int i=0;i<=n;++i){
C[i][0]=sum[i][0]=1;
for(int j=1;j<=i;++j)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod,sum[i][j]=(sum[i][j-1]+C[i][j])%mod;
}
ll m=n,up=min(a,min(b,min(c,min(d,n/4)))),ans=0,ta=a,tb=b,tc=c,td=d;
for(int i=0;i<=up;++i){
n=m-4*i;a=ta-i;b=tb-i;c=tc-i;d=td-i;ll res=0;
for(ll mid=max(n-c-d,0LL);mid<=min(n,a+b);++mid)res=(res+C[m-3*i][i]*C[n][mid]%mod*get(mid-b,min(mid,a),mid)%mod*get(n-mid-d,min(c,n-mid),n-mid)%mod)%mod;
if(i&1)ans=(ans-res+mod)%mod;
else ans=(ans+res)%mod;
}
cout<<ans<<endl;
return 0;
}