<h1>CF1097G</h1>

题意大概是给 $n$ 个点的树,定义 $f(S)$ 表示 $S$ 中所有的点构成的斯坦纳树的大小。求
$$\sum_{S \subseteq [1,2,\cdots,n],S \neq \emptyset} f(S)^k$$
解:首先看到 $k$ 次方和发现不太好求,我们可以拆成斯特林数的形式:
$$x^k = \sum_{i=0}^k i! (^x_i) &#92;{^k_i&#92;}$$
其中 $&#92;{^a_b&#92;}$ 表示第二类斯特林数,组合意义是将 $a$ 个有标号的求放进 $b$ 个无标号的箱子的方案数。
考虑组合意义,枚举最后一个球怎么放可以写出递推方程:
$$&#92;{^n_m&#92;} = m&#92;{^{n-1}_ m&#92;} + &#92;{^{n-1}_ {m-1}&#92;}$$
边界状态为 $&#92;{^0_0&#92;} = 1$
然后我们考虑为什么对 $x^k$ 的展开是对的:我们只需要考虑组合意义是否相同。
左边的组合意义:有 $k$ 个球,$x$ 中颜色,染色方案是 $x^k$
右边的组合意义:首先将相同颜色的球锁起来,枚举有多少种不同颜色的球 $i$,首先要从这 $x$ 种颜色选出 $i$ 中互不相同的颜色 ($(^x_i)$),然后要将这个 $k$ 个球染上 $i$ 种颜色(相当于将 $k$ 个 有标号的球放入 $i$ 个有标号的箱子里,也就是 $i! &#92;{^k_i&#92;}$)
所以左右两边组合意义相同,等式成立。
然后代入原式可以得到
$$\sum_{S} \sum_{i=0}^k i! (^{f(S)}_ i) &#92;{^k_i&#92;}$$
$$\sum_{i=0}^k i! &#92;{^k_i&#92;} \sum_{S} (^{f(S)}_ i)$$
发现我们只需要算 $\sum_{S} (^{f(S)}_ i)$ 了,这个式子其实计算的是所有点集的斯坦纳树中选择 $i$ 条边的方案数,这个树形背包做就好了。
设 $f_{i,j}$ 表示以 $i$ 为根的子树内选择了 $j$ 条边的方案数,转移时考虑:

  1. 不选这个子树
  2. 只选这个子树
  3. 同时选这个子树和其他子树

就可以了。最后代入原式计算即可。

/*
 * Author: RainAir
 * Time: 2019-08-03 20:00:00
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define Re register
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int LL
const int MAXN = 1e5 + 5;
const int ha = 1e9 + 7;

std::vector<int> G[MAXN];
int n,K;
int fac[205],S205;
int fMAXN,sz[MAXN],ans[MAXN];

inline void dfs(int v,int fa=0){
    sz[v] = 1;fv = 1;
    for(auto x:G[v]){
        if(x == fa) continue;
        dfs(x,v);
        static int tmp[500+5];CLR(tmp,0);
        FOR(i,0,(int)sz[v]-1){
            if(i > K) break;
            FOR(j,0,(int)sz[x]-1){
                if(i+j > K) break;
                (tmp[i+j] += fv*fx%ha) %= ha;
                (tmp[i+j+1] += fv*fx%ha) %= ha;
                (ans[i+j] += fv*fx%ha) %= ha;
                (ans[i+j+1] += fv*fx%ha) %= ha;
            }
        }
        FOR(i,0,K) fv = (fv + tmp[i] + fx + ((i == 0) ? 0 : fx))%ha;
        sz[v] += sz[x]; 
    }
}

signed main(){
    scanf("%lld%lld",&n,&K);
    FOR(i,1,n-1){
        int u,v;scanf("%lld%lld",&u,&v);
        G[u].pb(v);G[v].pb(u);
    }
    S0 = 1;fac[0] = 1;
    FOR(i,1,K){
        fac[i] = 1llfac[i-1]i%ha;
        FOR(j,1,K){
            Si = (1llSi-1j%ha+Si-1) % ha;
        }
    }
    dfs(1);int res = 0;
    FOR(i,0,K){
        (res += 1llfac[i]SK%ha*ans[i]%ha) %= ha;
    }
    printf("%lldn",res);
    return 0;
}
Last modification:April 7th, 2020 at 10:14 pm
如果觉得我的文章对你有用,请随意赞赏