Codeforces Round 258 (Div. 2) E. Devu and Flowers 生成函数

题目链接

题目大意

有 $n$ $(1\le n\le 20)$ 个花瓶，第 $i$ 个花瓶里有 $f_i$ $(1\le f_i\le 10^{12})$ 朵花。现在要选择 $s$ $(1\le s\le 10^{14})$朵花。

求出有多少种方案。两种方案不同当且仅当两种方案中至少有一个花瓶选择花的数量不同，答案对 $10^9+7$ 取模。

思路

取第 $i$ 种花的生成函数可以表示为 ：$f_i(x)=$$1+x+x^2+x^3+\cdot \cdot \cdot x^{f_i}$.

则选取方案的生成函数可以表示为 ：$G(x)=$$f_1(x)\cdot f_2(x)\cdot \cdot \cdot f_n(x)=$$\frac{(1-x^{f_1+1})(1-x^{f_2+1})(1-x^{f_3+1})\cdot \cdot \cdot (1-x^{f_n+1})}{(1-x{)}^n}$$=$ $\frac{{\prod }_{i=1}^n(1-x^{f_i+1})}{(1-x{)}^n}$$=$ ${\prod }_{i=1}^n(1-x^{f_i+1})$ $\cdot$${\sum }_{i=0}^{\infty }$ $\left(\genfrac{}{}{0ex}{}{i+n-1}{i}\right)$$x_i$$=$${\prod }_{i=1}^n(1-x^{f_i+1})$ $\cdot$${\sum }_{i=0}^{\infty }$ $\left(\genfrac{}{}{0ex}{}{i+n-1}{n-1}\right)$$x_i$ .

则$[x^s]G(x)$即为所求的答案。

令$A(x)={\prod }_{i=1}^n(1-x^{f_i+1})$,$B(x)={\sum }_{i=0}^{\infty }$ $\left(\genfrac{}{}{0ex}{}{i+n-1}{n-1}\right)x_i$.

由于 $n\le 20$ , 所以 $A(x)$ 最多只有 $2^{20}$ 项，可以直接枚举，即 $ans=[x^s]G(x)={\sum }_{i=0}^{2^n}[x^i]A(x)\cdot [x^{s-i}]B(x)=$ ${\sum }_{i=0}^{2^n}[x^i]A(x)\cdot \left(\genfrac{}{}{0ex}{}{s-i+n-1}{n-1}\right)$，由于 $n$ 很小可以暴力计算组合数，总的时间复杂度为 $O(n\cdot 2^n)$.

code

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pii pair<int, int>using namespace std;
const int mod = 1e9 + 7;
int f[30];int ksm(int x, int k)
{int res = 1;while (k > 0){if (k & 1)res = res * x % mod;x = x * x % mod;k >>= 1;}return res;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, s;cin >> n >> s;int fac = 1;for (int i = 1; i <= n; ++i){cin >> f[i - 1];if (i < n)fac = fac * i % mod;}int infac = ksm(fac, mod - 2);int ans = 0;for (int i = 0; i < (1ll << n); ++i){int cnt = 0, sum = 0;for (int j = 0; j < n; ++j){if ((1ll << j) & i)cnt++, sum += f[j] + 1;}if (sum > s)continue;int tmp = 1;for (int j = 0; j < n - 1; ++j){int p = (s - sum + n - 1 - j) % mod;tmp = tmp * p % mod;}tmp = tmp * infac % mod;ans = (ans + ((cnt & 1) ? mod - tmp : tmp) % mod) % mod;}cout << (ans + mod) % mod << '\n';return 0;
}