题解 【P3301 [SDOI2013]方程】

如果没有任何限制，那么插板可得方案数就是 $\tbinom{n-1}{m-1}$。

对于大于等于的限制，这种情况直接把 $m$ 减去 $A_i-1$ 即可。

而小于等于的限制推了一波没搞出来什么东西，又注意到 $n$ 非常小（只有 $8$），所以直接枚举子集容斥。

容斥的方法是从考虑了大于等于限制的总方案数中减去至少有一个小于等于条件不满足的方案数，再加上至少有两个小于等于条件不满足的……最终答案写成式子就是（$m$ 已经减去了所有大于等于的限制的情况）：

$$\sum ((-1)^{\lvert S\rvert}\tbinom{n-1}{m-1-\sum\limits_{i\in S}A_i})$$

式子很显示出来很挤很丑，将就着看吧

$S$ 表示枚举的集合。

由于模数比较恶心，需要扩展卢卡斯。由于扩展卢卡斯是 $O(p\log p)$，结合枚举子集就是 $O(2^{n1}p\log p)$，加上多测显然过不去，但实际上扩卢时间复杂度很假很玄学，所以是能过的（

关于常数

值得一提的是，按照上面的做法直接写是过不去的（（（

扩卢预处理一下每个模数因子的阶乘就可以跑过去了。

#include <cstdio>
#define int long long

int a[10005], b[10005], f[1005], len, id;

int qpow(int a, int b, int mod) {
	int ret = 1LL;
	while (b) {
		if (b & 1) ret = ret * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ret;
}
void exgcd(int a, int b, int &x, int &y) {
	if (!b) x = 1, y = 0;
	else exgcd(b, a % b, y, x), y -= a / b * x;
}
int inv(int a, int p) {
	int x, y;
	exgcd(a, p, x, y);
	x = (x % p + p) % p;
	if (!x) return p;
	return x;
}
int fact(int n, int p, int mod, int id) {
	if (!n) return 1;
	int sum = 1LL;
	sum = qpow(f[id], n / mod, mod);//本来f[id]是要算的，但由于预处理了就不用
	for (int i = 1; i <= n % mod; ++ i)
		if (i % p) sum = sum * i % mod;
	return sum * fact(n / p, p, mod, id) % mod;
}
int C(int n, int m, int p, int mod, int id) {
	if (n < m) return 0;
	if (!n || !m || n == m) return 1;
	int cnt = 0, k = n - m, ans;
	ans = fact(n, p, mod, id) * inv(fact(m, p, mod, id), mod) % mod * inv(fact(k, p, mod, id), mod) % mod;
	while (n) n /= p, cnt += n;
	while (m) m /= p, cnt -= m;
	while (k) k /= p, cnt -= k;
	ans = ans * qpow(p, cnt, mod) % mod;
	return ans;
}

int CRT() {
	int ans = 0LL, sum = 1LL;
	for (int i = 1; i <= len; ++ i) sum *= a[i];
	for (int i = 1; i <= len; ++ i) {
		int m = sum / a[i] * inv(sum / a[i], a[i]) % sum;
		ans = (ans + b[i] * m % sum) % sum;
	}
	return ans;
}

int exLucas(int n, int m, int p) {
	if (n <= 0 || n < m) return 0;
	len = 0;
	int k = 1, id = 0;
	while (p != 1) {
		++ k;
		if (p % k) continue;
		int cnt = 0, mod = 1LL;
		while (p % k == 0) ++ cnt, p /= k, mod *= k;
		a[++ len] = mod, b[len] = C(n, m, k, mod, ++ id);
	}
	return CRT();
}

void init(int p) {
	int k = 1;
	while (p != 1) {
		++ k;
		if (p % k) continue;
		int cnt = 0, mod = 1LL;
		while (p % k == 0) ++ cnt, p /= k, mod *= k;
		++ id;
		f[id] = 1LL;
		for (int i = 1; i <= mod; ++ i)
			if (i % k) f[id] = f[id] * i % mod;//预处理阶乘
	}
}
int A[10];

signed main() {
	int T, p;
	scanf("%lld%lld", &T, &p);
	init(p);
	while (T --) {
		int n, n1, n2, m, ans = 0;
		scanf("%lld%lld%lld%lld", &n, &n1, &n2, &m);
		for (int i = 1; i <= n1; ++ i) scanf("%lld", A + i);
		for (int i = 1; i <= n2; ++ i) {
			int x;
			scanf("%lld", &x);
			m -= x - 1;
		}
		for (int S = 0; S < 1 << n1; ++ S) {
			int cnt = 0, tmp = m;
			for (int i = 1; i <= n1; ++ i)
				if (S & 1 << i - 1) ++ cnt, tmp -= A[i];
			ans = (ans + (cnt & 1 ? -1 : 1) * exLucas(tmp - 1, n - 1, p)) % p;
		}
		printf("%lld\n", (ans + p) % p);
	}
	return 0;
}