0%

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

发表于 更新于 阅读次数： Valine：

题目链接

很巧妙的一道小清新题。

首先请搞明白“好苹果”，“坏苹果”，“有用的苹果”的定义，不要混了。

有一个很重要的结论，我们发现我们可以把树的形态和权值分开算。

那么我们设 \(f(s)\) 为恰好有 \(s\) 个好的但是没有用的苹果的树的数量，\(r(s)\) 为选出 \(s\) 个权值使得权值之和不大于 \(limit\) 的方案数，那么 \(ans=\sum\limits_{s=0}^k\frac{f(k-s)r(s)}{\binom{k}{s}}\)，这里要除一个组合数因为如果我们在选权值的时候选出了某些点作为有用的苹果，那么有用的苹果的集合是固定的，而按照 \(f\) 的定义，任何一种大小为 \(s\) 的没用的点的集合都被算了一遍，所以要除以选择大小为 \(s\) 的集合的方案数。

我们先来算比较好算的 \(r(s)\) 部分，注意到 \(n\leqslant 40\)，这启发我们用折半搜索，和 这题 类似，把数分为两部分，然后分别算出所有子集的和，对于前半部分直接按权值和排序，对于后半部分先把它放在子集大小对应的桶里每个桶里分别排序，然后双指针，复杂度依旧为 \(O(n2^{\frac{n}{2}})\)。

然后我们来算 \(f(s)\) 部分，看到求生成树的数量和较小的数据范围，不难想到使用矩阵树定理，但是我们直接做肯定是不能算出来恰好 \(s\) 个有用的苹果的。所以我们考虑钦定 \(s\) 个然后二项式反演，如果钦定有用的苹果，那么还需要考虑内部连边和连通块的方案，难以计算。所以我们钦定好的但是没有用的苹果，因为这一部分一定只和坏苹果连边。这样的话假设钦定了 \(s\) 个好的但是没有用的苹果，连边就是 \([1,s]\) 向 \([1,s]\cup [k+1,n]\) 连边，\([s+1,k]\) 向 \([k+1,n]\) 连边，\([k+1,n]\) 向 \([k+1,n]\) 连边。

然后这个地方的二项式反演和普通的钦定二项式反演不太一样，如果我们按照上面的方法求出行列式，实际上求出的不是 \(g(s)\)，而是 \(g'(s)\)，其中满足 \(g(s)=\binom{k}{s}g'(s)\)。因为行列式是强制了钦定集合为 \([k-s+1,k]\)，而正常我们二项式反演时所有大小为 \(s\) 的集合都会被钦定，而对于任何一个集合连边的方案都是相同的，所以要成上组合数。

那么对于 \(f(s)\) 和 \(g(s)\) 它们的关系和正常的钦定型二项式反演一样，满足： \[ f(s)=\sum\limits_{i=s}^k\binom{i}{s}(-1)^{i-s}g(i) \] 这样这道题就做完了。总复杂度 \(O(n2^{\frac{n}{2}}+n^4)\)。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
int const p=1e9+7;
typedef pair<int,int> pii;
int pw(int x,int y)
{
    int res=1;
    while(y)
    {
        if(y&1)res=1ll*res*x%p;
        x=1ll*x*x%p;
        y>>=1;
    }
    return res;
}
bool cmp(int x,int y){return x>y;}
void mod(int &x){if(x>=p)x-=p;}
int n,a[45],head[25],r[45],g[45],c[45][45],e[45][45];
vector<int>v[2],buc[25];
vector<pii>q;
void add(int x,int y){e[x][y]--,e[y][x]--,e[x][x]++,e[y][y]++;}
int det()
{
    int ans=1;
    for(int i=1;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
            if((!e[i][i])&&e[j][i]){swap(e[i],e[j]);ans=p-ans;break;}
        int inv=pw(e[i][i],p-2);
        for(int j=i+1;j<n;j++)
        {
            int t=1ll*e[j][i]*inv%p;
            for(int k=i;k<n;k++)
                e[j][k]-=1ll*e[i][k]*t%p,e[j][k]+=p,mod(e[j][k]);
        }
    }
    for(int i=1;i<n;i++)ans=1ll*ans*e[i][i]%p;
    return ans;
}
int main()
{
    int limit,k=0;
    scanf("%d%d",&n,&limit);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]!=-1)k++;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=(k>>1);i++)v[0].pb(a[i]);
    for(int i=(k>>1)+1;i<=k;i++)v[1].pb(a[i]);
    for(int i=0;i<(1<<v[0].size());i++)
    {
        q.pb(mp(0,__builtin_popcount(i)));
        for(int j=0;j<v[0].size();j++)
            if(i&(1<<j))q[i].first+=v[0][j];
    }
    sort(q.begin(),q.end());
    for(int i=0;i<(1<<v[1].size());i++)
    {
        int t=__builtin_popcount(i);
        buc[t].pb(0);
        for(int j=0;j<v[1].size();j++)
            if(i&(1<<j))buc[t][buc[t].size()-1]+=v[1][j];
    }
    for(int i=0;i<=v[1].size();i++)
        sort(buc[i].begin(),buc[i].end()),head[i]=buc[i].size();
    for(int i=0;i<q.size();i++)
    {
        for(int j=0;j<=v[1].size();j++)
        {
            while(head[j]&&buc[j][head[j]-1]+q[i].first>limit)head[j]--;
            r[j+q[i].second]+=head[j],mod(r[j+q[i].second]);
        }
    }
    c[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        c[i][0]=1;
        for(int j=1;j<=i;j++)
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;
    }
    for(int s=0;s<=k;s++)
    {
        memset(e,0,sizeof(e));
        for(int i=1;i<=k-s;i++)
        {
            for(int j=i+1;j<=k-s;j++)
                add(i,j);
            for(int j=k+1;j<=n;j++)
                add(i,j);
        }
        for(int i=k-s+1;i<=k;i++)
            for(int j=k+1;j<=n;j++)
                add(i,j);
        for(int i=k+1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
                add(i,j);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(e[i][j]<0)e[i][j]+=p;
        g[s]=1ll*det()*c[k][s]%p;
    }
    int ans=0;
    for(int s=0;s<=k;s++)
    {
        int res=0;
        for(int i=s;i<=k;i++)
            res+=1ll*c[i][s]*(((i-s)&1)?p-1:1)%p*g[i]%p,mod(res);
        ans+=1ll*res*r[k-s]%p*pw(c[k][s],p-2)%p,mod(ans);
    }
    printf("%d",ans);
    return 0;
}