题解 P5339 【[TJOI2019]唱、跳、rap和篮球】
wjyyy
2019-06-15 11:07:38
[**在我的博客查看**](https://www.wjyyy.top/3653.html)
## 题解
没学过生成函数，暴力容斥了。
感觉这种在序列上的组合问题会一下子想到容斥。
用 `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：
```cpp
#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;
}
```