Crash的游戏

Vexoben

Mar 31, 2019

It takes 6 minutes to read this article.

题意

$T$ 组数据，每组给定 $n$ , $m$ , $k$ ,计算 $\sum_{i=0}^{m} \dbinom{m}{i} \dbinom{n-m+2i}{k} mod \; 1e9+7$

数据范围： $T≤300,N≤10^9,M≤10^9,K≤300$

题解

下文中我们用 $n$ 代替 $n-m$

考虑组合意义：有 $m$ 个二元组和 $n$ 个一元组，选出任意多个二元组和所有的一元组，在其中选出 $k$ 个数，求方案。

假设在一元组中选出了 $x$ 个数，那么就要在二元组中选出 $k-x$ 个数。假设这选出的 $k-x$ 个数来自于 $y$ 个二元组，那么其余 $m-y$ 个二元组都可以任意选择选或不选。设 $f_{i,j}$ 表示从 $i$ 个二元组中选出 $j$ 个数，每个二元组中至少选一个数的方案数，那么答案就是：

$\sum_{x=0}^{k} \dbinom{n}{x} \sum_{y=0}^{k} \dbinom{m}{y} 2^{m-y} f_{y,k - x}$

$f$ 可以直接递推： $f_{i,j} = 2f_{i-1,j-1} + f_{i-1,j-2}$

复杂度 $O(Tk^2)$

#include<bits/stdc++.h>
#define fi first
#define se second
#define R register
#define mp make_pair
#define pb push_back
#define LL long long
#define Ldb long double
#define pii pair<int, int>
using namespace std;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;

template <typename T> void read(T &x) {
	int f = 0;
	R char c = getchar();
	while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
	for (x = 0; c >= '0' && c <= '9'; c = getchar())
		x = (x << 3) + (x << 1) + (c ^ '0');
	if (f) x = -x;
}

int n, m, k;
int inv[N], fac[N], fav[N];
int cn[N], cm[N];
int f[303][303];

int add(int x, int y) {
	static int z;
	return ((z = x + y) >= mod) ? (z - mod) : z;
}

int Qpow(int x, int p) {
	int ans = 1;
	while (p) {
		if (p & 1) ans = 1LL * ans * x % mod;
		x = 1LL * x * x % mod;
		p >>= 1;
	}
	return ans;
}

void solve() {
	read(n); read(m); read(k);
	n -= m;
	f[0][0] = 1;
	for (int i = 1; i <= k; ++i) {
		for (int j = i; j <= k; ++j) {
			f[i][j] = add(f[i - 1][j - 1], f[i - 1][j - 1]);
			if (j > 1) f[i][j] = add(f[i][j], f[i - 1][j - 2]);
		}
	}
	
	fac[0] = fav[0] = 1;
	inv[1] = fac[1] = fav[1] = 1;
	for (int i = 2; i <= k; ++i) {
		inv[i] = 1LL * -mod / i * inv[mod % i] % mod + mod;
		fac[i] = 1LL * fac[i - 1] * i % mod;
		fav[i] = 1LL * fav[i - 1] * inv[i] % mod;
	}fuzadu
	
	cn[0] = 1;
	for (int i = 1; i <= k; ++i) {
		cn[i] = 1LL * cn[i - 1] * (n - i + 1) % mod;	
	}
	for (int i = 1; i <= k; ++i) {
		cn[i] = 1LL * cn[i] * fav[i] % mod;
	}
	cm[0] = 1;
	for (int i = 1; i <= k; ++i) {
		cm[i] = 1LL * cm[i - 1] * (m - i + 1) % mod;
	}
	for (int i = 1; i <= k; ++i) {
		cm[i] = 1LL * cm[i] * fav[i] % mod;
	}
	
	int ans = 0;
	for (int i = 0; i <= k && i <= n; ++i) {
		int pw = 1LL * cn[i] * Qpow(2, m) % mod;
		for (int j = 0; j <= k && j <= m; ++j) {
			ans = add(ans, 1LL * pw * f[j][k - i] % mod * cm[j] % mod);
			pw = 1LL * pw * inv[2] % mod;
		}
	}
	cout << ans << endl;
}

int main() {
	int T;
	read(T);
	while (T--) solve();
	return 0;
}