51nod 1446 限制價值樹 矩陣樹定理+折半搜尋+容斥

題意

有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後的結果。

說明：兩棵樹是不同的，指兩棵樹的邊集不同，注意這裡的邊都是無向邊。

1<=T<=5，1<=N<=40，0<=maxVal<=1,000,000,000，-1<=val[i]<=25,000,000。

分析

一開始想到一個奇奇怪怪的做法，然後就開始碼碼碼，結果發現居然是錯的。。。

首先注意到方案隻跟great點的數量有關，設有x個good點。

設 g[i] 表示前i個good點不great其餘不管的方案，也就是至少有i個不great點的方案。那麼前i個點隻能向bad點連邊，其餘點随意，可以用矩陣樹定理來求生成樹方案。

設 f[i] 表示隻有前i個good點不great的方案，也就是恰好有i個不great點的方案。不難得到遞推式

f[i]=g[i]−∑xj=i+1Cj−ix−i∗f[j] 。

那麼剩下的隻要求出 h[i] 表示有多少種選i個點的方式使得其val的和不超過maxVal，這個可以用折半搜尋來解決。

代碼

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long LL;

const int N=;
const int inf=;
const int MOD=;

int n,jc[N],ny[N],mat[N][N],m,cnt[][],tot,tot_bad,val[N],f[N],h[N],g[N];
pair<int,int> a[];

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

void updata(int &x,int y)
{
    x+=y;x-=x>=MOD?MOD:;
}

int ksm(int x,int y)
{
    int ans=;
    while (y)
    {
        if (y&) ans=(LL)ans*x%MOD;
        x=(LL)x*x%MOD;y>>=;
    }
    return ans;
}

void dfs1(int x,int y,int s,int w)
{
    if (x>y) {a[++tot]=make_pair(w,s);return;}
    dfs1(x+,y,s,w);
    if (w+val[x]<=m) dfs1(x+,y,s+,w+val[x]);
}

void dfs2(int x,int y,int s,int w)
{
    if (x>y)
    {
        pair<int,int> u=make_pair(m-w,n+);
        int p=upper_bound(a+,a+tot+,u)-a-;
        for (int i=;i<=n/;i++) updata(h[i+s],cnt[p][i]);
        return;
    }
    dfs2(x+,y,s,w);
    if (w+val[x]<=m) dfs2(x+,y,s+,w+val[x]);
}

void prepare()
{
    jc[]=jc[]=ny[]=ny[]=;
    for (int i=;i<=;i++) jc[i]=(LL)jc[i-]*i%MOD,ny[i]=(LL)(MOD-MOD/i)*ny[MOD%i]%MOD;
    for (int i=;i<=;i++) ny[i]=(LL)ny[i-]*ny[i]%MOD;
}

int det(int n)
{
    int ans=;
    for (int i=;i<=n;i++)
    {
        if (!mat[i][i]) return ;
        for (int j=i+;j<=n;j++)
            while (mat[j][i])
            {
                if (mat[j][i]<mat[i][i])
                {
                    ans=-ans;
                    for (int k=;k<=n;k++) swap(mat[i][k],mat[j][k]);
                }
                int w=mat[j][i]/mat[i][i];
                for (int k=;k<=n;k++) updata(mat[j][k],MOD-(LL)mat[i][k]*w%MOD);
            }
        ans=(LL)ans*mat[i][i]%MOD;
    }
    ans+=ans<?MOD:;
    return ans;
}

int solve(int x)
{
    memset(mat,,sizeof(mat));
    for (int i=;i<=x;i++)
        for (int j=n+;j<=n+tot_bad;j++)
            mat[i][j]=mat[j][i]=MOD-,mat[i][i]++,mat[j][j]++;
    for (int i=x+;i<n+tot_bad;i++)
        for (int j=i+;j<=n+tot_bad;j++)
            mat[i][j]=mat[j][i]=MOD-,mat[i][i]++,mat[j][j]++;
    return det(n+tot_bad-);
}

void dp()
{
    for (int i=;i<=n;i++) g[i]=solve(i);
    for (int i=n;i>=;i--)
    {
        f[i]=g[i];
        for (int j=i+;j<=n;j++) updata(f[i],MOD-(LL)jc[n-i]*ny[j-i]%MOD*ny[n-j]%MOD*f[j]%MOD);
    }
}

int main()
{
    prepare();
    int T=read();
    while (T--)
    {
        n=read();m=read();tot_bad=;
        for (int i=;i<=n;i++) val[i]=read();
        sort(val+,val+n+);int tmp=n;
        for (int i=;i<=n;i++) if (val[i]==-) tot_bad++,val[i]=inf,tmp--;
        sort(val+,val+n+);n=tmp;
        tot=;dfs1(,n/,,);
        sort(a+,a+tot+);
        for (int i=;i<=tot;i++)
        {
            for (int j=;j<=n/;j++) cnt[i][j]=cnt[i-][j];
            cnt[i][a[i].second]++;
        }
        memset(h,,sizeof(h));
        dfs2(n/+,n,,);
        dp();
        int ans=;
        for (int i=;i<=n;i++) updata(ans,(LL)h[n-i]*f[i]%MOD);
        printf("%d\n",ans);
    }
    return ;
}