隐藏
「51nod1446」限制价值树 / 「NOI2017模拟20」苹果树 - 生成树计数+容斥原理+meet-in-the-middle | Bill Yang's Blog
0%

「51nod1446」限制价值树 / 「NOI2017模拟20」苹果树 - 生成树计数+容斥原理+meet-in-the-middle

题目大意

    有$N$个点($N\le40$)标记为$0,1,2,\ldots,N-1$,每个点$i$有个价值$val[i]$,如果$val[i]=-1$那么这个点被定义为bad,否则如果$val[i]\ge0$那么这个点为定义为good。现在给这$N$个点间连上$N-1$条边,使它们构成一个生成树,定义树中的点为great点当且仅当这个点本身是good点且与其相邻的点中至少有另一个good点。树的价值等于树中所有great点的价值和。定义限制价值树是指价值不大于$maxVal$的树,问对给定的$val[]$与$maxVal$,一共有多少种不同的限制价格树?由于答案太大,可取
$\mod 10^9+7$后的结果。
    说明:两棵树是不同的,指两棵树的边集不同,注意这里的边都是无向边。


题目分析

先考虑计数点,不考虑权值。
设$g(i)$为至少$i$个good点不是great点(称为rp点),构成的生成树个数。
那么这$i$个点只能向bad点连边,其他点可以任意连。
用矩阵树定理解出$g(i)$。

然而因为可能图中实际的rp点不止选出来的这些,因此需要容斥。
设$f(i)$为恰好$i$个rp点构成的生成树个数,一共有$x$个good点。

接下来考虑权值问题。
设$Hash(i)$表示选择$i$个good点使得权值和$\le lim$的方案数。
那么$\sum f(i)\cdot Hash(x-i)$就是答案。

$Hash()$可以通过搜索计算,然而搜索会超时,用meet-in-the-middle+排序双指针降低时间复杂度。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}

const int maxn=45,mod=1e9+7;

void add(LL &x,LL v) {x=x+v>=mod?x+v-mod:x+v;}

int n,m,lim;
LL a[maxn][maxn],v[maxn],f[maxn],g[maxn],Hash[maxn],Hashr[maxn],C[maxn][maxn];

int Gauss(int n) {
LL ans=1;
int bj=1;
for(int i=1; i<=n; i++) {
for(int j=i+1; j<=n; j++) {
LL A=a[i][i],B=a[j][i];
while(B) {
LL t=A/B;
A%=B;
swap(A,B);
for(int k=i; k<=n; k++)a[i][k]=(a[i][k]-a[j][k]*t%mod+mod)%mod;
for(int k=i; k<=n; k++)swap(a[i][k],a[j][k]);
bj*=-1;
}
}
ans=ans*a[i][i]%mod;
}
return (ans*bj+mod)%mod;
}

void AddEdge(int x,int y) {
a[x][x]++,a[y][y]++;
a[x][y]--,a[y][x]--;
}

LL Cal(int num) {
memset(a,0,sizeof(a));
for(int i=1; i<=num; i++)
for(int j=m+1; j<=n; j++)AddEdge(i,j);
for(int i=num+1; i<=n; i++)
for(int j=i+1; j<=n; j++)AddEdge(i,j);
return Gauss(n-1);
}

#define pii pair<int,LL>

void Dfs(int now,int end,int cnt,int val,vector<pii> &a) {
if(val>lim)return;
if(now==end) {a.push_back(pii(val,cnt));return;}
Dfs(now+1,end,cnt,val,a);
Dfs(now+1,end,cnt+1,val+v[now],a);
}

vector<pii> L,R;

int main() {
n=Get_Int();
lim=Get_Int();
for(int i=1; i<=n; i++)v[i]=Get_Int(),m+=v[i]!=-1;
sort(v+1,v+n+1,greater<int>());
for(int i=0; i<=m; i++)g[i]=Cal(i);
for(int i=0; i<=m; i++) {
C[i][0]=C[i][i]=1;
for(int j=1; j<i; j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
for(int i=m; i>=0; i--) {
f[i]=g[i];
for(int j=i+1; j<=m; j++)add(f[i],mod-C[m-i][j-i]*f[j]%mod);
}
Dfs(1,m/2+1,0,0,L);
Dfs(m/2+1,m+1,0,0,R);
sort(L.begin(),L.end()),sort(R.begin(),R.end());
for(pii x:R)Hashr[x.second]++;
int j=R.size()-1;
for(int i=1; i<=L.size(); i++) {
pii x=L[i-1];
while(~j&&x.first+R[j].first>lim)Hashr[R[j--].second]--;
for(int k=0; k<=n-m/2; k++)add(Hash[x.second+k],Hashr[k]);
}
LL ans=0;
for(int i=0; i<=m; i++)add(ans,f[i]*Hash[m-i]%mod);
printf("%lld\n",ans);
return 0;
}
姥爷们赏瓶冰阔落吧~