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

· · 题解

在我的博客查看

题解

没学过生成函数，暴力容斥了。

感觉这种在序列上的组合问题会一下子想到容斥。

用 c,t,r,l 分别表示喜欢唱、跳、rap、篮球的同学。

首先，如果要用容斥解决的话，可以从序列中连续的 c,t,r,l 的个数入手。

首先需要计算当 a,b,c,d 都无穷大，即每个位置都可以放 c,t,r,l 中任意一个同学时，长为 n 的序列中有 m 个连续的 c,t,r,l 的方案。

定义 \mathrm{C}_n^m 为长为 n 的序列里选 m 个元素，且被选出的任意两个元素之间距离不小于 4，那么上面所提到的方案的计算式就是 \mathrm{C}_{n-3}^m。

而根据组合意义，\mathrm{C}_n^m=\sum_{i=0}^{n-3}\mathrm{C}_{i}^{m-1}。

而在本题中，n\le 1000，因此有效的 \mathrm{C}_n^m 不超过 1000^2 个，而且 0\le m\le\lfloor\frac{n-1}4\rfloor+1，所以常数也比较小。

递推时，只需要处理 \mathrm{C}_i^m 关于 i 的前缀和 \mathrm{C}_0^m+\mathrm{C}_1^m+\cdots，就可以做到 O(n^2) 了。

有了所有的 \mathrm{C}_n^m 之后，就可以开始容斥了。

当序列中有至少 0 个连续的 c,t,r,l 时，所有位置上都可以任选。

这是一个可重组合数问题，但是由于只有四种元素，我们可以先确定四种喜好的同学分别有多少个。四种喜好的人数依次设为 A,B,C,D(0\le A\le a,0\le B\le b,0\le C\le c,0\le D\le d)，令 k=\min\{a,b,c,d\}。

那么接下来就是求合法的（A+B+C+D=n）四元组 (A,B,C,D) 的个数了。

直接枚举是 O(k^3) 的，而对于每个 i(0\le i\le\lfloor\frac{n-1}4\rfloor) 都要做一遍，这是承受不了的。

我们可以通过枚举二元组 (A,B) 来预处理有多少个二元组满足 A+B=t，再枚举 (C,D)，和 (C,D) 能匹配上的 (A,B) 的数量就是满足 A+B=n-C-D 的二元组 (A,B) 数量。

也就是说，如果用 cnt_t 来表示有多少个二元组 (A,B) 满足 A+B=t，那么对于二元组 (C,D)，能匹配上它的有 cnt_{n-C-D} 种。

上面解释了一个 meet-in-middle 的思路，复杂度为 O(k^2)，小常数 O(nk^2) 级别还是可以接受的。

这时，我们得到了合法的四元组 (A,B,C,D) 的数目了，现在转化为可重排列问题，这个用阶乘算一下就可以了。

但是我们只知道数目，不知道具体的 (A,B,C,D)。可重排列数中，分子上是 n!，而分母上是 A!B!C!D!。根据不同的 (A,B,C,D)，这个数不尽相同。

我们可以在上面算贡献的时候，对于二元组 (A,B)，对 cnt_{A+B} 的贡献就是 \frac{1}{A!B!}；而当 (C,D) 找回去的时候，就用 \frac1{C!D!} 去乘 cnt_{n-C-D}。

这样就有了“至少 0 个”，也就是任意位置上都随便放的方案数。

至少 1 个的方案数，就是把上面“至少 0 个”方案数中的 n 换成 n-4，然后乘上上面所定义的 \C_n^1。

依此类推，直到至少 k 个会把 c,t,r,l 中最少的一个用完，或者至少 \frac n4 个。连续的 c,t,r,l 填满了所有位置。

答案就是至少 0 个 - 至少 1 个 + 至少 2 个 +\cdots+(-1)^{\min(k,\frac n4)}\times 至少 \min(k,\frac n4) 个。

时间复杂度 O(nk^2)，常数在 \frac 14 左右。

trick：

从这题可以看出来组合数的一种推法。当间隔不大于 1 时，也就是原意义下的组合数，\mathrm{C}_n^m=\sum_{i=0}^{n-1}\mathrm{C}_i^{m-1}。

Code：

#include<cstdio>
#include<cstring>
#define p 998244353
#define ll long long
int Min(int x,int y){return x<y?x:y;}
ll qpow(ll x,ll y)
{
    ll ans=1;
    while(y)
    {
        if(y&1)
            ans=ans*x%p;
        x=x*x%p;
        y>>=1;
    }
    return ans;
}
int f[1010][300];
ll sum[300],func[1010],inv[1010];
int cnt[1010];
int main()
{
    int n;
    scanf("%d",&n);
    func[0]=1;
    f[0][0]=1;
    for(int i=1;i<=n;++i)
    {
        func[i]=func[i-1]*i%p;
        f[i][0]=1;
        for(int j=1;j<=i/4;++j)
        {
            sum[j-1]=(sum[j-1]+f[i-4][j-1])%p;
            f[i][j]=sum[j-1];
        }
    }
    inv[n]=qpow(func[n],p-2);
    for(int i=n-1;i>=0;--i)
        inv[i]=inv[i+1]*(i+1)%p;
    int a,b,c,d;
    scanf("%d%d%d%d",&a,&b,&c,&d);
    int mn=a<b?(a<c?(a<d?a:d):(c<d?c:d)):(b<c?(b<d?b:d):(c<d?c:d)),ans=0;
    //int mn=Min(Min(a,b),Min(c,d)),ans=0;
    for(int i=0,tot=n;i<=mn&&i<=n/4;++i,--a,--b,--c,--d,tot-=4)
    {
        memset(cnt,0,sizeof(cnt));
        long long op=0;
        for(int A=0;A<=a;++A)
            for(int B=0;B<=b;++B)
                cnt[A+B]=(cnt[A+B]+inv[A]*inv[B])%p;
        for(int C=0;C<=c;++C)
            for(int D=0;D<=d&&C+D<=tot;++D)
                op=(op+cnt[tot-C-D]*inv[C]%p*inv[D])%p;
        op=op*func[tot]%p;
        if(i&1)
            ans=(ans+p-op*f[n][i]%p)%p;
        else
            ans=(ans+op*f[n][i]%p)%p;
    }
    printf("%d\n",ans);
    return 0;
}