[51nod 1446] 价值限制树

[51nod 1446] 价值限制树

思路

今日份的“调了一下午”,让我从一个不会容斥、矩阵树定理和折半搜索的sb变成了一个会容斥、矩阵树定理和折半搜索的sb

设$f[i]$为$i$个great点构成生成树的方案数,$g[i]$为$i$个great点构成的限制价值树的方案数

求$g[i]$

折半搜索,第一次dfs中记录所有的方案,将方案按$val_i$的和排序,维护一个$cnt[i][j]$表示前$i$个方案,有$j$个great点的方案数。进行第二次搜索的时候运用二分查找直接就可以统计

求$f[i]$

设$h[i]$为最多$i$个great点构成生成树的方案数,将$i$个great点间相互连边,bad点与所有点之间连边,跑矩阵树定理即可求出$h[i]$

由容斥原理可知$f[n]=h[n]-\sum \limits_{i=0}^{n}f[i]\cdot C_{n}^{i}$

答案即为$\sum \limits_{i=0}^{N}f[i]\cdot g[i]$

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int mod=1000000007;
int N, maxval, val[45], cnt1, cnt[1048580][21], cntb, cntg, C[41][41];
long long g[41], f[41];

pair<int, int>a[1048580];

void dfs1(int x, int sum, int num){
	if(x==N/2+1){
		a[++cnt1].second=num;
		a[cnt1].first=sum;
		return;
	}
	if(val[x]!=-1 && sum+val[x]<=maxval)
		dfs1(x+1, sum+val[x], num+1);
	dfs1(x+1, sum, num);
}

void dfs2(int x, int sum, int num){
	if(x==N+1)	return;
	if(val[x]!=-1){
		int pos=upper_bound(a+1, a+cnt1+1, make_pair(maxval-sum-val[x], 0x3f3f3f3f))-a-1;
		for(int i=0; i<=N/2; i++)
			g[i+num+1]=(long long)(g[i+num+1]+cnt[pos][i])%mod;	
	}
	if(val[x]!=-1 && val[x]+sum<=maxval)
		dfs2(x+1, sum+val[x], num+1);
	dfs2(x+1, sum, num);
}

long long solve(int x){
	long long A[45][45];
	memset(A, 0, sizeof(A));
	for(int i=1; i<=x; i++)
		for(int j=i+1; j<=x; j++)
			A[i][j]=-1, A[j][i]=-1, A[i][i]++, A[j][j]++;
	for(int i=N-cntb+1; i<=N; i++)
		for(int j=1; j<i; j++)
			A[i][j]=-1, A[j][i]=-1, A[i][i]++, A[j][j]++;
	long long ans=1;
	for(int i=1; i<N; i++){
		for(int j=i+1; j<N; j++)
			while(A[j][i]){
				long long tmp=A[i][i]/A[j][i];
				for(int k=i; k<N; k++)
					A[i][k]=((A[i][k]-tmp*A[j][k]%mod)%mod+mod)%mod, swap(A[i][k], A[j][k]);
				ans=-ans;
			}
		ans=(ans*A[i][i]%mod+mod)%mod;
	}
	ans=(ans+mod)%mod;
	return ans;
}

int main(){
	int T;
	scanf("%d", &T);
	C[1][1]=1;
	for(int i=0; i<=40; i++)
		C[i][0]=1;
	for(int i=2; i<=40; i++)
		for(int j=1; j<=i; j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	while(T--){
		long long ans=0;
		memset(cnt, 0, sizeof(cnt));
		memset(g, 0, sizeof(g));
		cntb=cntg=cnt1=0;
		scanf("%d%d", &N, &maxval);
		for(int i=1; i<=N; i++){
			scanf("%d", &val[i]);
			if(val[i]==-1)	cntb++;
			else		cntg++;
		}
		dfs1(1, 0, 0);
		sort(a+1, a+cnt1+1);
		for(int i=1; i<=cnt1; i++){
			for(int j=0; j<=N/2; j++)
				cnt[i][j]=cnt[i-1][j];
			cnt[i][a[i].second]++;
		}
		for(int i=0; i<=N/2; i++)
			g[i]=1LL*cnt[cnt1][i];
		dfs2(N/2+1, 0, 0);	
		for(int i=0; i<=cntg; i++)
			f[i]=(long long)solve(i)%mod;
		for(int i=1; i<=cntg; i++)
			for(int j=0; j<i; j++)
				f[i]=((f[i]-f[j]*C[i][j]%mod)%mod+mod)%mod;
		for(int i=0; i<=cntg; i++)
			ans=(long long)(ans+g[i]*f[i]%mod)%mod;
		printf("%lld\n", ans);
	}
	return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注