【OGF、Lucas】P4640 [BJWC2008] 王之财宝

显然，就是有一些的 OGF 为 \(\frac{1}{1 - x}\)，有一些为 \(\frac{1 - x^{b_i + 1}}{1 - x}\)。乘起来即可。

发现不太好算分子，考虑枚举哪些算了。

然后我们考虑 \(2^t\) 的枚举子集。然后直接乘上对应的 \(b_i + 1\) 的系数即可。

然后我们要求分母第 \(i\) 位的系数，这个很典， \(i\) 个无标号元素放入，\(n\) 个有标号集合里的方案。直接插板即可。

然后我们答案要对这个求 \(1 \to k\) 的前缀和，那么我们直接用典恒等式有：

然后我们对于这个直接用 Lucas 求即可。

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i ++)
#define per(i, r, l) for (int i = r; i >= l; i --)
#define cpy(x, y, s) memcpy(x, y, sizeof(x[0]) * (s))
#define mem(x, k) memset(x, k, sizeof(x))
#define ll long long
#define int long long
// \yhx-12243/ 鱼大保佑！！

using namespace std;

const int _ = 1e6 + 5;

int power (int x, int y, int mod) {
	int res = 1;
	for ( ; y; x = x * x % mod, y >>= 1)
		if (y & 1) res = res * x % mod;
	return res;
}

int n, m, t, p, b[_];
int inv[_], fac[_], res;

int C (int n, int m) {
	return fac[n] * inv[m] % p * inv[n - m] % p;
}
int lucas (int n, int m) {
	if (n < m) return 0;
	if (n < p) return C(n, m);
	return lucas(n / p, m / p) * lucas(n % p, m % p) % p;
}
signed main () {
	cin >> n >> t >> m >> p;
	rep(i, 0, t - 1) cin >> b[i], b[i] ++;
	
	fac[0] = inv[0] = 1;
	rep(i, 1, p - 1) fac[i] = fac[i - 1] * i % p;
	rep(i, 1, p - 1) inv[i] = power(fac[i], p - 2, p);
	
	rep(i, 0, (1 << t) - 1) {
		int f = 1, sum = 0;
		rep(j, 0, t - 1) if ((i >> j) & 1) {
			sum += b[j], f = -f;
		} 
//		cout << i << " " <<  sum << " " << n + m - sum << " " << m - sum  << endl;
		(res += f * lucas(n + m - sum, m - sum)) %= p;
	}
	cout << (res + p) % p;
	return 0;
}