题解 P5339 【[TJOI2019]唱、跳、rap和篮球】

Fading · 2019-05-10 16:22:31 · 题解

首先转换一下问题：

我们求有多少个排布方案，满足至少有1堆人讨论鸡你太美。

怎么求呢？

我们可以枚举有i堆人讨论鸡你太美，这样放置的方案数是

为什么呢？

第一个方法是整体法（感谢@千年之狐_天才 大佬）

首先，对于每一种方案，有n-4i个没有被选中的位置。

我们可以考虑枚举这些没有被选中的位置。

把每一个讨论鸡你太美的组看成一个整体，缩成一个点。

这样就有n-3i个点了。

对于所有n-3i个点，如果被选中，成为一个讨论鸡你太美的组，那么这个点就要被展开代表4个人。

否则就代表一个人。

我们直接从这n-3i个点中选取n-4i个点作为没有被选为组的点。

这样方案数就是C_{n-3i}^{n-4i}=C_{n-3i}^i

显然这样的枚举对应的方案是唯一的（可以把这些选为组的点展开，再顺序标号）。

第二个方法是转化法。

可以考虑转化一下问题。这等价于求1~n-3放置i个数且i个数两两距离\geq 4的组合数,即a_j+4\leq a_{j+1}

设b_j=a_j-3\times j,显然

所以我们枚举b的组合，就可以得到满足条件的a的组合

所以答案就等于b的组合个数

然后这么多位置已经固定了，怎么计算剩余不讨论鸡你太美的人的排列数呢？？？

真心难算！因为可能有些排列会有不只i个人讨论鸡你太美！

所以我们考虑用容斥原理，枚举有i~\frac n4组人讨论鸡你太美。

这样就可以排除干扰，对剩下的乱排列了。

设初始4个数最小值为mini

答案ans=

这个为什么对呢？

发现枚举至少一组的时候，对于一种可行的方案（这里代指枚举方案）会算2次至少两组的贡献，算3次至少三组的贡献。

枚举至少两组的时候，会算3次至少三组的贡献，算6次至少四组的贡献。

枚举至少i组的时候，会算C_j^i次至少j组的贡献(j\geq i)

所以我们可以通过容斥

来算出单个的贡献。这可以通过二项式展开来证明。

所以答案ans=

设喜欢4种大法的人初始有x_1,x_2,x_3,x_4个

这时候分别还剩下x_1-i,x_2-i,x_3-i,x_4-i个人

相当于求有重复元素的排列！

我们知道，如果x_1+x_2+x_3+x_4=n

那么排列答案就是\frac {(n-4i)!}{(x_1-i)!(x_2-i)!(x_3-i)!(x_4-i)!}

如果x_1+x_2+x_3+x_4<n，答案就是0。

如果x_1+x_2+x_3+x_4>n呢？考虑暴力枚举+排列。

这就是一个四元卷积啦！

维护4个数组，里面元素全是阶乘值（显然有上界），做NTT即可。

模数真良心

我们前面还要用所有排列的个数减去答案，所以真正的答案其实就是

一个标准的容斥式子。

数学真是美妙啊！！！

对了，复杂度是O(n^2log_2n)，比较慢。

代码如下：

#include<bits/stdc++.h>
#define ll long long
#define ljc 998244353
using namespace std;
ll n,m,r[40006],lim;
ll a[20001],w[20001],b[20001],mini,num[4],c[20001],d[20001],fac[20010],inv[20001];
inline ll fast_pow(ll a,ll b,ll p){
    ll t=1;a%=p;
    while (b){
        if (b&1) t=t*a%p;
        b>>=1;a=a*a%p;
    }
    return t;
}
inline void NTT(ll f[],int lim,int id){
    for (int i=0;i<lim;i++){
        if (i<r[i]) swap(f[r[i]],f[i]);
    }
    w[0]=1;
    for (int len=1;len<lim;len<<=1){
        ll gen=fast_pow(3,(ljc-1)/(len<<1)*id+ljc-1,ljc);
        for (int i=1;i<len;i++) w[i]=w[i-1]*gen%ljc;
        for (int i=0;i<lim;i+=len<<1){
            ll *f1=f+i,*f2=f1+len;
            for (int j=0;j<len;j++){
                ll x=f1[j],y=f2[j]*w[j]%ljc;
                f1[j]=(x+y)%ljc;
                f2[j]=(x-y+ljc)%ljc;
            }
        }
    }
    if (id==1) return;
    ll Inv=fast_pow(lim,ljc-2,ljc);
    for (int i=0;i<lim;i++) f[i]=f[i]*Inv%ljc;
}
inline ll P(ll n,ll A,ll B,ll C,ll D){
    if (n>A+B+C+D) return 0;
    if (n<0) return 0;
    ll lim=1,len=0;
    while (lim<(A+B+C+D<<1)) lim<<=1,len++;
    for (int i=0;i<lim;i++) r[i]=(r[i>>1LL]>>1LL)|(((1LL*i)&1)<<(len-1LL));
    for (int i=0;i<lim;i++) a[i]=(i<=A)?inv[i]:0;
    for (int i=0;i<lim;i++) b[i]=(i<=B)?inv[i]:0;
    for (int i=0;i<lim;i++) c[i]=(i<=C)?inv[i]:0;
    for (int i=0;i<lim;i++) d[i]=(i<=D)?inv[i]:0;
    NTT(a,lim,1);NTT(b,lim,1);NTT(c,lim,1);NTT(d,lim,1);
    for (int i=0;i<lim;i++) a[i]=a[i]*b[i]%ljc*c[i]%ljc*d[i]%ljc;
    NTT(a,lim,-1);
    return fac[n]*a[n]%ljc;
}
inline ll C(ll m,ll n){
    if (m<n) return 0;
    return (fac[m]*inv[n]%ljc*inv[m-n]%ljc);
}
inline void init(int n){
    n*=2;
    inv[0]=inv[1]=1;fac[0]=1;
    for (int i=1;i<=n;i++) fac[i]=fac[i-1]*i%ljc;
    for (int i=2;i<=n;i++) inv[i]=(ljc-(ljc/i)*inv[ljc%i]%ljc)%ljc;
    for (int i=2;i<=n;i++) inv[i]=inv[i-1]*inv[i]%ljc;
}
int main(){
    cin>>n>>num[0]>>num[1]>>num[2]>>num[3];
    mini=min(num[0],min(num[1],min(num[2],num[3])));
    init(n);
    ll ans=0,one=1;
    for (int i=0;i<=min(mini,n/4);i++){
        ans=(ans+one*C(n-3*i,i)%ljc*P(n-4*i,num[0]-i,num[1]-i,num[2]-i,num[3]-i)%ljc)%ljc;
        one=ljc-one;        
    }
    cout<<ans;
    return 0;
}