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

2019-06-15 11:07:38


在我的博客查看

题解

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

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

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;
}