Devu and Flowers

题目大意

你有 nn 个花瓶，第 ii 个花瓶中有 fif_i 朵花，现在要选出 ss 朵花，求方案数对 109+710^9+7 取模的结果。

其中数据范围满足，1≤n≤20,0≤fi≤1012,0≤s≤10141\le n\le 20,0\le f_i\le 10^{12},0\le s\le 10^{14}。

思路

先考虑 fi→∞f_i\to \infty 时选择 ss 朵花的方案数，考虑使用插板法求解。

ss 朵花中间一共有一些空子，因为可以留空所以每次插入一个隔板可以插入的地方都会增加 11。

所以总共的方案数为 ∏i=s+1n+s−1i\prod\limits_{i=s+1}^{n+s-1} i，但是去除本质相同的也就得到：

∏i=s+1n+s−1i(n−1)!=(n+s−1)!s!⋅(n−1)!=Cs+n−1s=Cs+n−1n−1\dfrac{\prod\limits_{i=s+1}^{n+s-1} i}{(n-1)!}=\dfrac{(n+s-1)!}{s!\cdot (n-1)!}=C_{s+n-1}^{s}=C_{s+n-1}^{n-1}

其中运用了组合数的性质：

Cnm=Cnn−mC_{n}^m=C_{n}^{n-m}

定义 sis_i 表示第 ii 种花选取了超过 fif_i 个，那么答案显然为：

Cs+n−1s−∣⋃i=1nsi∣C_{s+n-1}^{s}-\lvert\bigcup\limits_{i=1}^{n}s_i\rvert

因为直接求解非常困难，考虑容斥。

对于 sis_i，首先我们需要选出 fi+1f_i+1 朵花用于购买第 ii 中花保证其不合法，接着随意的购买其余的花。显然，这样操作的方案数为 Cs−fi−1nC_{s-f_i-1}^{n}。

对于 si∪sjs_i\cup s_j，与上面的思路一样我们应该用 fi+1f_i+1 和 fj+1f_j+1 朵花分别购买第 ii 种和第 jj 中保证其并不合法，接下来随意的购买任意的花。容易得到，这样操作的方案数为 Cs−fi−fj−2nC_{s-f_i-f_j-2}^{n}。

根据这个思路可以得到对于选取集合 gg，其方案数为：

Cn−∑i∈g(fi+1)n\huge{C_{n-\sum_{i\in g} (f_i+1)}^{n}}

直接穷举所有的集合 gg，接着对上面的式子进行容器即可，时间复杂度为 O(2n⋅n)O(2^n\cdot n)。

Submission #271015900 - Codeforces