Vexoben
Mar 31, 2019
题目链接:51nod1446 限制价值树
(刷新以获取数学公式)
题意
有个点（）标记为,每个点有个价值,如果那么这个点被定义为，否则如果那么这个点为定义为。现在给这个点间连上条边，使它们构成一个生成树，定义树中的点为点当且仅当这个点本身是点且与其相邻的点中至少有另一个点。树的价值等于树中所有点的价值和。定义限制价值树是指价值不大于的树，问对给定的 ,，一共有多少种不同的限制价格树？由于答案太大，可取 后的结果。
说明：两棵树是不同的，指两棵树的边集不同，注意这里的边都是无向边。
题解
显然使得一个给定点集为的生成树个数只和这个点集的大小有关。
设为有个点是点的方案数，为选出个点，其权值和不大于的方案数，那么答案就是
显然直接一下就好了，考虑计算
在点之间两两连边，和点之间两两连边，非点的点和点之间两两连边，点之间两两连边，求这样的图生成树数量，记为，那么有：
用定理直接计算即可。
#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 = 51;
const int mod = 1000000007;
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, good, maxval;
int a[N], f[N], g[N];
int fac[N], fav[N], inv[N];
void init() {
fac[0] = fav[0] = 1;
inv[1] = fac[1] = fav[1] = 1;
for (int i = 2; i < N; ++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;
}
}
int C(int x, int y) {
return 1LL * fac[x] * fav[y] % mod * fav[x - y] % mod;
}
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;
}
int Inv(int x) {
return Qpow(x, mod - 2);
}
int matrix_tree(int x) {
static int a[N][N];
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
a[i][j] = 0;
}
}
int c, d;
for (int i = 1; i <= n; ++i) {
if (i <= x) c = 1;
else if (i <= good) c = 2;
else c = 3;
for (int j = i + 1; j <= n; ++j) {
if (j <= x) d = 1;
else if (j <= good) d = 2;
else d = 3;
if (c + d == 2 || c == 3 || d == 3) {
a[i][j] = a[j][i] = mod - 1;
++a[i][i]; ++a[j][j];
}
}
}
int ans = 1;
for (int i = 1; i < n; ++i) {
if (a[i][i] == 0) {
ans = -ans;
for (int j = i + 1; j < n; ++j) {
if (a[i][j] > 0) {
for (int k = i; k < n; ++k) {
swap(a[i][k], a[j][k]);
}
break;
}
}
}
if (a[i][i] == 0) return 0;
for (int j = i + 1; j < n; ++j) {
int t = 1LL * Inv(a[i][i]) * a[j][i] % mod;
for (int k = i; k < n; ++k) {
int d = 1LL * t * a[i][k] % mod;
a[j][k] -= d;
if (a[j][k] < 0) a[j][k] += mod;
}
}
}
if (ans < 0) ans += mod;
for (int i = 1; i < n; ++i) {
ans = 1LL * ans * a[i][i] % mod;
}
return ans;
}
void calcf() {
for (int i = 0; i <= good; ++i) {
f[i] = matrix_tree(i);
for (int j = 0; j < i; ++j) {
int t = 1LL * C(i, j) * f[j] % mod;
t = mod - t;
f[i] += t;
if (f[i] >= mod) f[i] -= mod;
}
}
}
void dfs(int x, int lim, int choose, int val, vector<int> *s) {
if (val > maxval) return;
if (x > lim) {
s[choose].push_back(val);
return;
}
dfs(x + 1, lim, choose, val, s);
dfs(x + 1, lim, choose + 1, val + a[x], s);
}
void calcg() {
vector<int> s1[N], s2[N];
sort(a + 1, a + n + 1);
reverse(a + 1, a + n + 1);
dfs(1, good / 2, 0, 0, s1);
dfs(good / 2 + 1, good, 0, 0, s2);
for (int i = 0; i < good; ++i) {
sort(s1[i].begin(), s1[i].end());
sort(s2[i].begin(), s2[i].end());
}
for (int i = 0; i <= good; ++i) {
g[i] = 0;
for (int j = 0; j <= i; ++j) {
int p = ((int) s2[i - j].size()) - 1;
for (int k = 0; k < (int) s1[j].size(); ++k) {
while (p >= 0 && s1[j][k] + s2[i - j][p] > maxval) --p;
if (p >= 0) g[i] += p + 1;
if (g[i] >= mod) g[i] -= mod;
}
}
}
}
void solve() {
read(n); read(maxval);
good = 0;
for (int i = 1; i <= n; ++i) {
read(a[i]);
if (a[i] >= 0) ++good;
}
calcf();
calcg();
int ans = 0;
for (int i = 0; i <= good; ++i) {
ans = (ans + 1LL * f[i] * g[i]) % mod;
}
cout << ans << endl;
}
int main() {
init();
int T;
read(T);
while (T--) solve();
return 0;
}