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

· · 题解

题面非常好

据说要用NTT和生成函数搞

然而我都不会

于是我就用组合数强行算出来了

首先，如果每种爱好没有人数限制？

这样，我们可以分别计算至少有0组讨论cxk，至少1组，至少2组……

最后容斥一下就可以，系数为(-1)^i

而这种情况下，只需要选择讨论cxk的组所在位置就可以，剩下的位置就是4^k种情况

这个可以DP出来，但我不是这样算的

可以把讨论cxk的组插入到剩余部分中，这样就是可重复选择的组合数，也就是(^{r+t}_t)，r表示剩余部分人数，t表示讨论cxk的组数

或者将讨论cxk的组作为一个整体，然后求组合数也可以

接下来考虑人数限制

考虑把剩下的位置分步计算

直接的想法是这样的：

\sum _{i=0} ^a (^n_i) \sum_{j=0} ^{n-i} (^{n-i}_j)\sum_{k=0} ^{n-i-j} (^{n-i-j}_k)

（注意这里对人数的限制可能不完整）

也就是，先从n个位置中选出i个位置是唱，再从剩下的n-i个位置中选出j个位置是跳，再从剩下的n-i-j个位置中选出k个位置是rap，最后剩下的部分是篮球

然后你会发现，这个式子复杂度是O(n^3)的，再加上容斥，就是O(n^4)，即使用前缀和优化一下，也是O(n^3)的

可能还有其它方法能算出来，但我不会

如果换一个办法算？

当然可以

\sum_{r=0}^n [(^n_r)\cdot(\sum_{k=r-b}^a (_k^r))\cdot (\sum_{k=n-r-d}^b (_k^{n-r}))]

首先选出r个位置唱或跳，剩下的部分rap或篮球

然后，对两部分分别求方案数，这样就可以了

发现\sum_{k=r-b}^a (_k^r)和\sum_{k=n-r-d}^b (_k^{n-r})都可以用前缀和求出来

这样，只要枚举r就可以了

具体实现时，先用杨辉三角把\leq n的组合数求出来，然后求每一行的前缀和，随后先枚举至少有几组讨论cxk，再枚举r，容斥一下就可以

小心边界情况

代码

#include<cstdio>
const long long M=998244353;
long long C[1024][1024];
long long suf[1024][1024];
int a,b,c,d,n,t;
int read(){
    int n=0;bool f=0;char c=getchar();
    while(c!='-'&&(c<'0'||c>'9'))c=getchar();
    if(c=='-'){f=1;c=getchar();};
    while(c>='0'&&c<='9'){
        n=n*10+c-'0';
        c=getchar();
    }
    if(f==1)return -n;
    else return n;
}
char res[25];
void write(long long n){
    if(n==0){putchar('0');return;};
    if(n<0){putchar('-');n=-n;}
    int t=0;
    while(n){res[t++]=n%10+'0';n/=10;};
    while(t--)putchar(res[t]);
    return;
}
void calc(){//求组合数及前缀和
    for(int i=0;i<=n;i++){
        C[i][0]=1;
        for(int j=1;j<=i;j++){
            C[i][j]=C[i-1][j-1]+C[i-1][j];
            if(C[i][j]>=M)C[i][j]-=M;
        }
    }
    for(int i=0;i<=n;i++){
        suf[i][0]=1;
        for(int j=1;j<=n;j++){
            suf[i][j]=suf[i][j-1]+C[i][j];
            if(suf[i][j]>=M)suf[i][j]-=M;
        }
    }
}
long long grange(int t,int l,int r){//求一段区间的和
    if(l>r)return 0;
    if(l<=0)return suf[t][r];//不特判会RE
    long long res=suf[t][r]-suf[t][l-1];
    if(res<0)res+=M;
    return res;
}
long long ans;
long long rs;
int main(){
    n=read();a=read();b=read();c=read();d=read();
    if(a>n)a=n;//如果求组合数的时候，只求到n
    if(b>n)b=n;//那么这里必须这样做
    if(c>n)c=n;//否则计算时会取到没计算过的数值
    if(d>n)d=n;//然后就会WA
    calc();
    //这里n,a,b,c,d表示剩余部分的人数，t表示有多少组讨论cxk
    while(n>=0&&a>=0&&b>=0&&c>=0&&d>=0){
        rs=0;
        for(int r=0;r<=n;r++){
            rs+=C[n][r]*grange(r,r-b,a)%M*grange(n-r,n-r-d,c)%M;
            if(rs>=M)rs-=M;
        }
        rs=rs*C[n+t][t]%M;
        if(t&1){
            ans-=rs;
            if(ans<0)ans+=M;
        }else{
            ans+=rs;
            if(ans>=M)ans-=M;
        }
        n-=4;a--;b--;c--;d--;t++;
    }
    ans%=M;
    if(ans<0)ans+=M;
    write(ans);
}