51nod1446 限制价值树

有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;

}

巴特西

51nod1446 限制价值树

题解

代码

最新文章

热门文章