【LOJ#6072】苹果树（矩阵树定理，折半搜索，容斥）

时间：2023-03-09 08:53:53
【LOJ#6072】苹果树（矩阵树定理，折半搜索，容斥）

【LOJ#6072】苹果树（矩阵树定理，折半搜索，容斥）

题面

LOJ

题解

emmmm,这题似乎猫讲过一次。。。

显然先\(meet-in-the-middle\)搜索一下对于每个有用的苹果数量，满足权值小于\(lim\)的方案数

，那么只需要考虑它们构成生成树的方案数就好了。

显然有用的可以和所有的有用的或者是坏的连边，好的但不有用的只能和坏的连边，而坏的随意。

但是这样子算出来的结果是至多，因此还需要额外容斥一下计算生成树的个数。

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

#define MAX 50

#define MOD 1000000007

void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int n,limit,m,c[MAX];

struct Node{int S,d;}S1[1050000],S2[1050000];

bool operator<(Node a,Node b){return a.S<b.S;}

int top1,top2;

void dfs1(int x,int S,int D)

{

	if(S>limit)return;

	if(x==m+1){S1[++top1]=(Node){S,D};return;}

	dfs1(x+1,S,D);

	if(c[x]>-1)dfs1(x+1,S+c[x],D+1);

}

void dfs2(int x,int S,int D)

{

	if(S>limit)return;

	if(x==n+1){S2[++top2]=(Node){S,D};return;}

	dfs2(x+1,S,D);

	if(c[x]>-1)dfs2(x+1,S+c[x],D+1);

}

int Cnt[MAX],cc[MAX];

int Sum[MAX],tot;

int a[MAX][MAX],C[MAX][MAX];

int fpow(int a,int b)

{

	int s=1;

	while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}

	return s;

}

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

int Matrix_Tree(int k)

{

	for(int i=1;i<=n;++i)

		for(int j=1;j<=n;++j)a[i][j]=0;

	for(int i=1;i<=n;++i)

		for(int j=i+1;j<=n;++j)

			if(i<=k){if(j<=k||j>tot)link(i,j);}

			else if(i>tot)link(i,j);

			else if(j>tot)link(i,j);

	for(int i=1;i<=n;++i)

		for(int j=1;j<=n;++j)

			a[i][j]=(a[i][j]+MOD)%MOD;

	int ans=1;

	for(int i=1;i<n;++i)

	{

		for(int j=i+1;j<n;++j)

		{

			int t=1ll*a[j][i]*fpow(a[i][i],MOD-2)%MOD;

			for(int k=i;k<n;++k)a[j][k]=(a[j][k]+MOD-1ll*t*a[i][k]%MOD)%MOD;

		}

		ans=1ll*ans*a[i][i]%MOD;

	}

	return ans;

}

int main()

{

	n=read();limit=read();m=(n+1)/2;

	for(int i=1;i<=n;++i)c[i]=read();

	for(int i=1;i<=n;++i)tot+=(c[i]!=-1);

	dfs1(1,0,0);dfs2(m+1,0,0);

	sort(&S1[1],&S1[top1+1]);sort(&S2[1],&S2[top2+1]);

	for(int i=top1,j=1;i;--i)

	{

		while(j<=top2&&S1[i].S+S2[j].S<=limit)cc[S2[j].d]+=1,++j;

		for(int k=0;k<=n;++k)add(Cnt[S1[i].d+k],cc[k]);

	}

	for(int i=0;i<=n;++i)C[i][0]=1;

	for(int i=1;i<=n;++i)

		for(int j=1;j<=i;++j)

			C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;

	for(int i=0;i<=tot;++i)Sum[i]=Matrix_Tree(i);

	for(int i=1;i<=tot;++i)

		for(int j=0;j<i;++j)

			Sum[i]=(Sum[i]+MOD-1ll*C[i][j]*Sum[j]%MOD)%MOD;

	int ans=0;

	for(int i=0;i<=tot;++i)add(ans,1ll*Cnt[i]*Sum[i]%MOD);

	printf("%d\n",ans);

	return 0;

}

相关文章