「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点。

$$f(i)=g(i)-\sum_{j=i+1}^{x}\binom{x-i}{j-i}f(j)$$

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

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

---

代码

#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;
}