2021牛客暑期多校训练营4 G Product

题目概述

给定三个整数$n,k,D$,设数列$a_i,i=1,2,…,n$,求对于所有数列满足$\forall i \in [1,n],a_i \geq 0$​且$\sum_{i=1}^na_i=D$​的情况下，

$$\frac{D!}{\prod_{i=1}^n(a_i+k)!}$$

的总和。

数据范围

$$1 \leq n \leq 50\\ 0\leq k \leq 50\\ D \leq 10^8$$

分析与解

此题比较神仙。首先分母上$(a_i+k)!$​不太好看，假设一个$a_i :=a_i+k$​.我们考虑一个组合模型，一个长度为D的数列，每个位置上可以填$[1,n]$中的任何正整数，一共有多少中填法。通过算两次，假设我们枚举$i$出现的次数为$a_i$​，或者直接乘法原理，那么这个组合模型的描述为

$$(\sum_{a_i\geq0}=D) \prod_{i=1}^n \frac{D!}{a_i!}=n^D$$

那么回到本题。如果不要求$a_i \geq 0$即$a_i+k \geq k$时，则答案就是$n^{D+nk}$

现在问题就是必须要求$a_i+k\geq k$。因此我们用容斥原理做。

由于$n,k$都比较小，所以不妨记$dp[i][j]$表示“有$i$个数不满足要求且这$i$个数的和是$j$”，对于剩下的$n-i$​个数可以满足要求也可以不满足要求，其和也是确定的$D+nk-j$.因此我们可以求出”至少有$i$​个数不满足要求时对答案的贡献”:

$$C_{n}^{i} \cdot \sum_j dp[i][j]\cdot(n-i)^{D+nk-j}$$

因此答案就是$n^{D+nk}$减去”至少一个违反条件的”加上“至少两个违反条件的”减去“至少三个违反条件的”…如此递推即可。

最后再乘上$\frac{D!}{(D+nk)!}$满足题意。