Link

Desciption

求一个可重集 \(S\) 的 \(m\) 子集的个数。\(S\) 的不同元素个数为 \(n\)，\(n\leq 20\)。每种元素的个数 \(a_i\leq 10^{12}\) 。答案对 \(10^9+7\) 取模。

Solution

如果每种元素都有无数种的话，那么直接用插板法可得方案数为 \(\binom{m+n-1}{n-1}\)。但是问题是每种元素个数都有一个上界，这样会得到一些不合法的方案。考虑将其减去。令 \(f_{sta}\) 表示强制令元素集合为 \(sta\) 的所有元素都超上界的方案，其中 \(sta\) 是一个状态，也是一个集合。那么有

\[f_{sta}=\binom{m+n-1-\sum_{i\in sta} (a_i+1)}{n-1} \]