Vexoben
Mar 31, 2019
题意
\(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;
}