题解 | 中位数之和

#include <iostream>
#include<algorithm>
#include<cmath>
using namespace std;

typedef long long ll; 

const ll p = 1000000007;
const ll biggest = 200009; 
ll factorial[biggest], inverse[biggest];


ll fast_pow_mod(ll base, ll exp, ll p) {
	if (base == 0) return 0;
	ll ans = 1;
	while (exp > 0) {
		if(exp & 1) ans = (ans * base) % p;
		base = (base * base) % p;
		exp >>= 1;
	}
	return ans;
}

ll calcu_c(ll base, ll exp, ll p) {
	return ((factorial[base] * inverse[exp] % p) * inverse[base - exp]) % p; 
} 
//计算方法简单，但是对于对于取1的数量的约束较多，建议直接用代数理解
//0 <= i <= m, 0 <= subLen - i <= n, subLen / 2 + 1 <= i综合上述式子得到对于i的约束
int main() {
	//预处理
	factorial[0] = 1;
	factorial[1] = 1;
	for (int i = 2;i <= biggest; i++) {
		factorial[i] = factorial[i - 1] * i % p;
	}
	for (int i = 0; i <= biggest; i ++) {
		inverse[i] = fast_pow_mod(factorial[i], p - 2, p);
	} 
	int t;
	cin >> t;
	while (t-- > 0) {
		ll len, subLen, m = 0, n, ans = 0;
		cin >> len >> subLen;
		int tmp;
		for (int i = 0;i < len; i++) {
			cin >> tmp;
			m += tmp; 
		}
		n = len - m;
		ll left = max(subLen - n, subLen / 2 + 1);
		ll right = min(m, subLen);
		for (int i = left; i <= right; i++) {
			ans = (ans + (calcu_c(m, i, p) * calcu_c(n, subLen - i, p) % p)) % p;
		}
		cout << ans << endl;
	}
}