「2017 山东一轮集训 Day5」苹果树

\(n\leq 40\)

折半搜索+矩阵树定理。

没有想到折半搜索。

首先我们先枚举\(k\)个好点，我们让它们一定没有用的。要满足这个条件就要使它只能和坏点相连。其他的点没有要求。这样算出来了至少\(k\)个点没有用的生成树个数，我们要得到恰好\(k\)个点的生成树个数就简单容斥一下就好了。

然后我们要得到有\(k\)个点没有用的情况下的点集的方案数。看到\(40\)这个范围我们容易想到折半搜索。

然后就没了。

但是我没写容斥，写的枚举集合划分(被吊打

代码：

#include<bits/stdc++.h>

#define ll long long

#define N 45

using namespace std;

inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

const ll mod=1e9+7;

int n;

ll lim;

int a[N];

ll c[N][N];

ll fac[N],ifac[N],g[N];

ll w[N][N];

ll sum;

ll ksm(ll t,ll x) {

	ll ans=1;

	for(;x;x>>=1,t=t*t%mod)

		if(x&1) ans=ans*t%mod;

	return ans;

}

ll f[N];

ll ned;

int good[N];

ll bad;

int num[N];

ll ans;

ll Gauss(ll a[][45],int n) {

	ll ans=1;

	for(int i=2;i<=n;i++) {

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

			if(a[j][i]) {

				ans=ans*(mod-1)%mod;

				swap(a[i],a[j]);

				break;

			}

		}

		if(!a[i][i]) return 0;

		ans=ans*a[i][i]%mod;

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

			if(!a[j][i]) continue ;

			ll tem=ksm(a[i][i],mod-2)*a[j][i]%mod;

			for(int k=i;k<=n;k++) a[j][k]=(a[j][k]-tem*a[i][k]%mod+mod)%mod;

		}

	}

	return ans;

}

vector<int>st;

ll cal() {

	if(!f[num[1]]) return 0;

	int tot=bad;

	st.clear();

	for(int i=1;i<=n;i++) for(int j=1;j<=num[i];j++) st.push_back(i);

	for(int i=1;i<=n;i++) tot+=num[i];

	memset(w,0,sizeof(w));

	for(int i=0;i<st.size();i++) {

		w[i+1][i+1]=st[i]*bad;

		for(int j=st.size()+1;j<=tot;j++) {

			w[i+1][j]=mod-st[i];

		}

	}

	for(int i=st.size()+1;i<=tot;i++) {

		w[i][i]=n-1;

		for(int j=st.size()+1;j<=tot;j++)

			if(i!=j) w[i][j]=mod-1;

		for(int j=0;j<st.size();j++)

			w[i][j+1]=mod-st[j];

	}

	ll ans=f[num[1]];

	ans=ans*fac[n-bad-num[1]]%mod%mod;

	for(int i=2;i<=n;i++) {

		ans=ans*ksm(ifac[i],num[i])%mod;

		ans=ans*ksm(g[i],num[i])%mod;

		ans=ans*ifac[num[i]]%mod;

	}

	ll tem=Gauss(w,tot);

	return ans*tem%mod;

}

int mid;

void dfs(int v,int lim,ll now,int cnt,vector<int>*a) {

	if(v>lim) return ;

	dfs(v+1,lim,now,cnt,a);

	a[cnt+1].push_back(now+good[v]);

	dfs(v+1,lim,now+good[v],cnt+1,a);

}

void meet_in_the_middle() {

	mid=good[0]>>1;

	vector<int>a[N],b[N];

	dfs(1,mid,0,0,a);

	dfs(mid+1,good[0],0,0,b);

	for(int i=1;i<=mid;i++) sort(a[i].begin(),a[i].end());

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

		for(int j=0;j<a[i].size();j++)

			if(a[i][j]>=ned) f[i]++;

	for(int i=1;i<=good[0]-mid;i++) {

		for(int j=0;j<b[i].size();j++) {

			if(b[i][j]>=ned) f[i]++;

			for(int k=1;k<=mid;k++) {

				(f[i+k]+=a[k].end()-lower_bound(a[k].begin(),a[k].end(),ned-b[i][j]))%=mod;

			}

		}

	}

}

int dep;

void dfs(int v,int res) {

	if(!res) {

		dep++;

		(ans+=cal())%=mod;

		return ;

	}

	if(!v) return ;

	dfs(v-1,res);

	for(int i=1;i*v<=res;i++) {

		num[v]=i;

		dfs(v-1,res-i*v);

		num[v]=0;

	}

}

bool cmp(int a,int b) {return a>b;}

int main() {

	n=Get(),lim=Get();

	fac[0]=1;

	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;

	ifac[n]=ksm(fac[n],mod-2);

	for(int i=n-1;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;

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

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

			c[i][j]=(!j||i==j)?1:(c[i-1][j-1]+c[i-1][j])%mod;

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

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

		if(a[i]>0) {

			good[++good[0]]=a[i];

			sum+=a[i];

		} else bad++;

	}

	ned=sum-lim;

	if(sum<=lim) {

		cout<<ksm(n,n-2)%mod;

		return 0;

	}

	if(!bad) {cout<<0;return 0;}

	sort(good+1,good+good[0]+1,cmp);

	meet_in_the_middle();

	g[0]=g[1]=1;

	for(int i=2;i<=n;i++) g[i]=ksm(i,i-2)%mod;

	dfs(good[0],good[0]);

	cout<<ans;

	return 0;

}