E. Devu and Flowers

题意

有 \(n(1\le n\le 20)\) 个不同颜色的球，每种颜色的球有 \(f_i(1\le f_i \le 10^{12})\) 个，问拿 \(s(1\le s\le 10^{14})\) 个球的方案数。

题解

考虑生成函数

\[F(x)=\prod_{i=1}^n(\sum_{j=0}^{f_i}x_j)=\frac{\prod_{i=1}^n(1-x^{f_i+1})}{(1-x)^n}=(\prod_{i=1}^n(1-x^{f_i+1}))\times(\sum_{i=0}\binom{n+i-1}{i}x^i) \]

求这玩意 \(x^s\) 的系数，因为分子的幂最多就 \(2^n\) 中，把分子每个幂的贡献算一下就完事。

AC代码

#include 
#define rep(i,a,b) for(int i=a;i>=1,a=a*a%P)if(b&1)res=res*a%P;
	return res;
}

ll C(ll n, ll k) {
	if (k > n) return 0;
	if (k > n-k) k = n-k;
	ll res = 1;
	rep(i,0,k)res=(n-i)%P*res%P;
	return res*qpow(fac[k], P-2)%P;
}

void pre() {
	fac[0] = 1;
	rep(i,1,50) fac[i] = fac[i-1]*i%P;
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
#endif
	cin.tie(nullptr)->ios::sync_with_stdio(false);
	pre();
	ll n,s,ans=0; cin>>n>>s;
	vector a(n);
	rep(i,0,n)cin>>a[i];
	rep(st,0,(1<>i)&1){
				pw+=a[i]+1;
				coe ++;
			}
		}
		if(pw>s) continue;
		if(coe&1) ans=(ans-C(n+s-pw-1,n-1)+P)%P;
		else ans=(ans+C(n+s-pw-1,n-1))%P;
	}
	cout<

注意第 20 行，必须先模后乘，否则爆long long。