「CF1097G」Vladislav and a Great Legend

发布于 17 天前  74 次阅读


CF1097G

题意大概是给 $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) \{^k_i\}$$
其中 $\{^a_b\}$ 表示第二类斯特林数,组合意义是将 $a$ 个有标号的求放进 $b$ 个无标号的箱子的方案数。
考虑组合意义,枚举最后一个球怎么放可以写出递推方程:
$$\{^n_m\} = m\{^{n-1}_ m\} + \{^{n-1}_ {m-1}\}$$
边界状态为 $\{^0_0\} = 1$
然后我们考虑为什么对 $x^k$ 的展开是对的:我们只需要考虑组合意义是否相同。
左边的组合意义:有 $k$ 个球,$x$ 中颜色,染色方案是 $x^k$
右边的组合意义:首先将相同颜色的球锁起来,枚举有多少种不同颜色的球 $i$,首先要从这 $x$ 种颜色选出 $i$ 中互不相同的颜色 ($(^x_i)$),然后要将这个 $k$ 个球染上 $i$ 种颜色(相当于将 $k$ 个 有标号的球放入 $i$ 个有标号的箱子里,也就是 $i! \{^k_i\}$)
所以左右两边组合意义相同,等式成立。
然后代入原式可以得到
$$\sum_{S} \sum_{i=0}^k i! (^{f(S)}_ i) \{^k_i\}$$
$$\sum_{i=0}^k i! \{^k_i\} \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],S[205][205];
int f[MAXN][205],sz[MAXN],ans[MAXN];

inline void dfs(int v,int fa=0){
    sz[v] = 1;f[v][0] = 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] += f[v][i]*f[x][j]%ha) %= ha;
                (tmp[i+j+1] += f[v][i]*f[x][j]%ha) %= ha;
                (ans[i+j] += f[v][i]*f[x][j]%ha) %= ha;
                (ans[i+j+1] += f[v][i]*f[x][j]%ha) %= ha;
            }
        }
        FOR(i,0,K) f[v][i] = (f[v][i] + tmp[i] + f[x][i] + ((i == 0) ? 0 : f[x][i-1]))%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);
    }
    S[0][0] = 1;fac[0] = 1;
    FOR(i,1,K){
        fac[i] = 1ll*fac[i-1]*i%ha;
        FOR(j,1,K){
            S[i][j] = (1ll*S[i-1][j]*j%ha+S[i-1][j-1]) % ha;
        }
    }
    dfs(1);int res = 0;
    FOR(i,0,K){
        (res += 1ll*fac[i]*S[K][i]%ha*ans[i]%ha) %= ha;
    }
    printf("%lld\n",res);
    return 0;
}

一个OIer。