51nod1446 限制价值树

短命女 2022-01-06 16:04 188阅读 0赞

有N个点（N<=40）标记为0,1,2，...N-1,每个点i有个价值val\[i\],如果val\[i\]=-1那么这个点被定义为bad，否则如果val\[i\] >=0那么这个点为定义为good。现在给这N个点间连上N-1条边，使它们构成一个生成树，定义树中的点为great点当且仅当这个点本身是good点且与其相邻的点中至少有另一个good点。树的价值等于树中所有great点的价值和。定义限制价值树是指价值不大于maxVal的树，问对给定的val\[\]与maxVal，一共有多少种不同的限制价格树？由于答案太大，可取

modulo 1,000,000,007后的结果。

说明：两棵树是不同的，指两棵树的边集不同，注意这里的边都是无向边。

#### 题解 ####

首先我们发现我们只需要求一个数组f表示有i个点是\\(sweet\\)的方案数。

然后我们再去搜出所有组合情况来乘一下就好了，这个就是折半搜索+排序+双指针。

然后我们再去设\\(g\[i\]\\)表示钦点i个点不能是\\(sweet\\)的方案数，这个用\\(matrix-tree\\)高斯消元就可以求出来。

于是：  
\\\[ f\_i=g\_i-\\sum\_\{j=i+1\}^\{x\}f\_j\*\\binom\{x-i\}\{j-i\} \\\]

#### 代码 ####

#include<bits/stdc++.h> using namespace std; #define N 43 typedef long long ll; const int mod=1e9+7; const int maxn=40; ll a[N][N],c[N][N],sum[N],f[N],g[N],tong[N],cnt1,cnt2,mxval,x,val[N],num[N]; int n; inline ll rd(){ ll x=0;char c=getchar();bool f=0; while(!isdigit(c)){if(c=='-')f=1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return f?-x:x; } inline void MOD(ll &x){x=x>=mod?x-mod:x;} struct node{ int sum,cnt; inline bool operator <(const node &b)const{ return sum<b.sum; } }a1[1<<20],a2[1<<20]; void dfs1(int now,int sum,int cnt){ if(now>x){ a1[++cnt1]=node{sum,cnt}; return; } dfs1(now+1,sum,cnt); dfs1(now+1,sum+num[now],cnt+1); } void dfs2(int now,int sum,int cnt){ if(now>num[0]){ a2[++cnt2]=node{sum,cnt}; return; } dfs2(now+1,sum,cnt); dfs2(now+1,sum+num[now],cnt+1); } inline ll power(ll x,ll y){ ll ans=1; while(y){ if(y&1)ans=ans*x%mod;x=x*x%mod;y>>=1; } return ans; } inline ll ni(ll x){return power(x,mod-2);} inline ll guass(int n){ ll ans=1; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j)MOD(a[i][j]=a[i][j]+mod); for(int i=1;i<=n;++i){ for(int j=i+1;j<=n;++j)if(i!=j){ ll x=a[j][i]*ni(a[i][i])%mod; for(int k=1;k<=n;++k)a[j][k]=(a[j][k]-x*a[i][k]%mod+mod)%mod; } } for(int i=1;i<=n;++i)ans=ans*a[i][i]%mod; return ans; } inline void solve(){ num[0]=0; memset(tong,0,sizeof(tong)); memset(f,0,sizeof(f)); memset(g,0,sizeof(g)); memset(sum,0,sizeof(sum)); n=rd();mxval=rd(); for(int i=1;i<=n;++i)val[i]=rd(); sort(val+1,val+n+1); for(int i=1;i<=n;++i)if(val[i]!=-1){ num[++num[0]]=val[i]; } for(int i=0;i<=num[0];++i){ //you i ge bu xiang memset(a,0,sizeof(a)); for(int j=1;j<=i;++j) for(int k=num[0]+1;k<=n;++k){ a[j][k]--;a[k][j]--; a[j][j]++;a[k][k]++; } for(int j=i+1;j<=n;++j) for(int k=j+1;k<=n;++k){ a[j][k]--;a[k][j]--; a[j][j]++;a[k][k]++; } g[i]=guass(n-1); } x=num[0]/2; cnt1=cnt2=0; dfs1(1,0,0); dfs2(x+1,0,0); sort(a1+1,a1+cnt1+1); sort(a2+1,a2+cnt2+1); for(int i=num[0];i>=0;--i){ f[i]=g[i]; for(int j=i+1;j<=num[0];++j)MOD(f[i]=f[i]-f[j]*c[num[0]-i][j-i]%mod+mod); } int p=1; for(int i=cnt2;i>=1;--i){ while(p<=cnt1&&a1[p].sum+a2[i].sum<=mxval){ tong[a1[p].cnt]++; p++; } for(int j=0;j<=num[0]-a2[i].cnt;++j)MOD(sum[j+a2[i].cnt]+=tong[j]); } ll ans=0; /* for(int i=0;i<=num[0];++i)cout<<sum[i]<<" ";puts(""); for(int i=0;i<=num[0];++i)cout<<g[i]<<" ";puts(""); for(int i=0;i<=num[0];++i)cout<<f[i]<<" ";puts("");*/ for(int i=0;i<=num[0];++i)MOD(ans+=f[num[0]-i]*sum[i]%mod); printf("%lld\n",ans); } int main(){ // freopen("1.in","r",stdin); c[0][0]=1; for(int i=1;i<=maxn;++i){ c[i][0]=1; for(int j=1;j<=maxn;++j)MOD(c[i][j]=c[i-1][j]+c[i-1][j-1]); } int T=rd(); while(T--)solve(); return 0; }

转载于:https://www.cnblogs.com/ZH-comld/p/10885765.html