【题解】[GDOI2018D2T2] 滑稽子图 树形 dp+第二类 stirling 数 ——quhengyi11

看题目可以去这个 blog 看看

题解

首先简化一下题目

它要求的就是
$$\sum_{S \in V} |f(S)|^m$$

其中 $S$是一个点集，$f(S)$指的是点集所形成的边集，形式化来讲就是 $f(S)=\{(u,v)|u\in S \&\& v\in S\&\&(u,v)\in E\}$

然后我们考虑用第二类 $stirling$数来做一下变换

$$\sum_{S \in V} \sum_{k=0}^m S_m^k C_{f(S)}^k k!$$

交换枚举顺序

$$\sum_{k=0}^m S_m^k k! \sum_{S \in V} C_{f(S)}^k$$

前面的东西用 $O(k^2)$的复杂度就能算出来，考虑求后面的这部分

$$\sum_{S \in V} C_{f(S)}^k$$

这个式子相当于是说求在图中挑 k 条边的生成边集的方案数

于是我们可以树形 $dp$解决

记 $f[u][k][0/1]$表示在第 $u$个点的子树中，已经有 $k$条边被选中，且 $u$是否被选中的目标点集数 (因为要合并信息所以 $u$的状态必不可少)(并且这里的目标点集中的生成边集不一定是 $=k$的，$\geq k$这样的边集也可以选 $k$条边)

对于一个 $u$的儿子节点 $v$，我们有
$$f[u][j+k][0] = f[u][j][0] * (f[v][k][0]+f[v][k][1])$$
$$f[u][j+k][1]=f[u][j][1]*(f[v][k][0]+f[v][k][1]+f[v][k-1][1])$$
因为当 $u,v$都被选中的时候这条边也会对答案有贡献，所以第二条式子会要 $f[v][k-1][1]$

因为众所周知 $GDOI$题目有版权所以我没有数据，这个程序只手玩了几组样例，不保证正确性= =

#include<bits/stdc++.h>
#define Re register
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define mod 998244353
#define eps 1e-4
#define lowbit(x) (x & -x)
#define N 100005
#define ls (u << 1)
#define rs (u << 1 | 1)
#define cl(arr) memset(arr, 0, sizeof arr)
inline void read (int &x)
{
    x = 0;
    Re char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
}
int n, m, K;
struct edge {
    int nxt, v;
} e[N << 1];
int head[N], tot;
inline void addedge (int u, int v)
{
    e[++tot] = (edge) { head[u], v };
    head[u] = tot;
}
ll f[N][12][2], g[12][2];
inline void dfs (int u, int fa)
{
    f[u][0][0] = 0; f[u][0][1] = 1; //挑不挑自己
    edge (i, u)
    {
        if (v == fa) continue;
        dfs(v, u);
        memcpy(g, f[u], sizeof g);
        fo (j, 0, K) (g[j][0] += f[v][j][0] + f[v][j][1]) %= mod;
        fo (j, 0, K)
            fo (k, 0, K - j)
            {
                (g[j + k][0] += (f[v][k][0] + f[v][k][1]) * f[u][j][0]) %= mod;
                if (k > 0)
                    (g[j + k][1] += (f[v][k][0] + f[v][k][1] + f[v][k - 1][1]) * f[u][j][1]) %= mod;
                else
                    (g[j + k][1] += (f[v][k][0] + f[v][k][1]) * f[u][j][1]) %= mod;
            }
        memcpy(f[u], g, sizeof g);
    }
}
ll s[15][15], fac[15], ans[15], sum;
int main ()
{
    read(n); read(m); read(K);
    fo (i, 1, m)
    {
        int u, v;
        read(u); read(v);
        addedge(u, v);
        addedge(v, u);
    }
    dfs(1, 0);
    fac[0] = 1; s[0][0] = 1;
    fo (i, 1, K) fac[i] = fac[i - 1] * i % mod;
    fo (i, 1, K)
        fo (j, 1, i)
            s[i][j] = (s[i - 1][j - 1] + s[i - 1][j] * j) % mod;
    fo (i, 1, K) (sum += s[K][i] * fac[i] % mod * (f[1][i][0] + f[1][i][1]) % mod) % mod;
    printf("%lld", sum);
    return 0;
}