「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;
}