P4517 [JSOI2018] 防御网络

考虑 $G$ 是树，根据期望线性性以及各边独立性将贡献分摊至每条边。

$S$ 固定时，$|H(S)|$ 等于 $S$ 张成的虚树大小。设 $e = (u, v)$ 两端子树大小分别为 $x$ 和 $y$，则 $e = (u, v)$ 被选中当且仅当 $u, v$ 子树内存在点属于 $S$，情况数为 $(2 ^ x - 1)(2 ^ y - 1)$。

考虑 $G$ 是基环树。将贡献分摊至每条边与唯一的环。给环 $C$ 上的点依次标号为 $1, 2, \cdots, |C|$。

$S$ 固定时，每条非环边产生贡献当且仅当其两端子图均存在属于 $S$ 的点。环稍显棘手，其贡献为连通「子树内存在点属于 $S$」的环点的最小代价。称环点被点亮当且仅当子树内存在点属于 $S$，易知贡献为环长减去最远的相邻两个被点亮环点的距离。

据此，枚举该距离 $L$，枚举编号最小的被点亮的点 $p$ 破环成链，容易设计 DP $f_{i, 0 / 1}$ 表示考虑到前 $i$ 个环点，当 $i$ 被点亮且是否存在相邻两个被点亮的环点相距 $L$ 时的总方案数。初始值 $f_{p, 0} = 1$，转移依次枚举 $i \in [p + 1, |C|]$，

$$\begin{aligned} f_{i, 0} & = v_i \sum\limits_{j = i - L + 1} ^ i f_{j, 0} \\ f_{i, 1}& = v_i \left(f_{i - L, 0} + \sum\limits_{j = i - L} ^ i f_{j, 1} \right) \end{aligned}$$

其中 $v_i = 2 ^ {|\mathrm{subtree}(i)|} - 1$，环点 $i$ 子树存在点属于 $S$ 的方案数。

每个 $f_{i, 0}$ 和 $f_{i, 1}$ 以 $i$ 作为编号最大的被点亮的环点的形式贡献至答案。根据实际意义，$p + |C| - i \leq L$ 时 $f_{i, 1}$ 贡献至答案，$p + |C| - i = L$ 时 $f_{i, 0}$ 贡献至答案。贡献系数为 $|C| - L$。

• 仅求出 $F_L$ 表示所有相邻被点亮的环点距离不超过 $L$ 的方案数，则 $F_L - F_{L - 1}$ 等于最长相邻被点亮环点距离为 $L$ 的方案数。这样可以省去第二维。

朴素 DP 时间复杂度 $\mathcal{O}(n ^ 2)$。算上枚举的两个值，总复杂度 $\mathcal{O}(n ^ 4)$。使用前缀和优化即可做到 $\mathcal{O}(n ^ 3)$。

当 $G$ 是仙人掌时，每个环贡献独立。用圆方树求得图上所有环，对每个环类似基环树一样做即可。时间复杂度 $\mathcal{O}(n ^ 3)$。

#include <bits/stdc++.h>
using namespace std;
bool Mbe;
constexpr int N = 400 + 5;
constexpr int mod = 1e9 + 7;
void add(int &x, int y) {x += y, x >= mod && (x -= mod);}
int ksm(int a, int b) {
  int s = 1;
  while(b) {
    if(b & 1) s = 1ll * s * a % mod;
    a = 1ll * a * a % mod, b >>= 1;
  }
  return s;
}
int n, m, ans, node;
vector<int> e[N], g[N];
int dn, dfn[N], low[N], stc[N], top;
void tarjan(int id) {
  dfn[id] = low[id] = ++dn, stc[++top] = id;
  for(int it : e[id]) {
    if(!dfn[it]) {
      tarjan(it), low[id] = min(low[id], low[it]);
      if(low[it] >= dfn[id]) {
        g[++node].push_back(id);
        g[id].push_back(node);
        for(int x = 0; x != it; ) {
          x = stc[top--];
          g[node].push_back(x);
          g[x].push_back(node);
        }
      }
    }
    else low[id] = min(low[id], dfn[it]);
  }
}
int find(int id, int ff) {
  int sz = id <= n;
  for(int it : g[id]) if(it != ff) sz += find(it, id);
  return sz;
}
bool Med;
int main() {
  // cout << 597656258ll * 256 % mod << endl;
  fprintf(stderr, "%.4lf\n", (&Mbe - &Med) / 1048576.0);
  #ifdef ALEX_WEI
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
  #endif
  cin >> n >> m, node = n;
  for(int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    e[x].push_back(y), e[y].push_back(x);
  }
  tarjan(1);
  for(int i = n + 1; i <= node; i++) {
    static long long val[N];
    int m = g[i].size();
    for(int j = 1; j <= m; j++) val[j] = ksm(2, find(g[i][j - 1], i)) - 1;
    if(m == 2) { // 一条边
      ans = (ans + val[1] * val[2]) % mod;
      continue;
    }
    for(int L = 1; L < m; L++)
      for(int p = 1; p <= L; p++) {
        static int f[N][2], s[N][2];
        memset(f, 0, sizeof(f));
        memset(s, 0, sizeof(s));
        f[p][0] = s[p][0] = val[p];
        for(int q = p + 1; q <= m; q++) {
          f[q][0] = s[q][0] = s[q - 1][0];
          f[q][1] = s[q][1] = s[q - 1][1];
          if(q >= L) add(f[q][0], mod - s[q - L][0]);
          if(q >= L + 1) add(f[q][1], mod - s[q - L - 1][1]);
          if(q >= L) add(f[q][1], f[q - L][0]);
          f[q][0] = f[q][0] * val[q] % mod;
          f[q][1] = f[q][1] * val[q] % mod;
          add(s[q][0], f[q][0]);
          add(s[q][1], f[q][1]);
          int cyc = p + m - q;
          if(cyc <= L) {
            add(ans, 1ll * (m - L) * f[q][1] % mod);
            if(cyc == L) add(ans, 1ll * (m - L) * f[q][0] % mod);
          }
        }
      }
  }
  cout << 1ll * ans * ksm(ksm(2, n), mod - 2) % mod << endl;
  return cerr << "Time: " << clock() << "\n", 0;
}
/*
2022/7/6
start thinking at 8:28
根据期望的线性性，把贡献摊到每条边 / 每个环上。
每条边的贡献显然好算。
每个环的贡献考虑给定 S 怎么做。
仅关心当前环，变成基环树，设环上一个点被点亮当且仅当其子树内有属于 S 的点。
答案是环长减去环上最远的两个被点亮的点的距离。
枚举这个距离，再破环成链枚举第一个点，随便 DP 再前缀和优化一下就做完了吧？
黑牌咋这么简单（
start coding at 8:38
finish debugging at 9:21
犯了一个铸币错误。。。m 打成 n 咧。
*/