题解 P7418【[USACO21FEB] Counting Graphs P】

problem

Bessie 有一个连通无向图 \(G\)。\(G\) 有 \(N\) 个编号为 \(1\ldots N\) 的结点，以及 \(M\) 条边（\(1\le N\le 10^2, N-1\le M\le \frac{N^2+N}{2}\)）。\(G\) 有可能包含自环（一个结点连到自身的边），但不包含重边（连接同一对结点的多条边）。

令 \(f_G(a,b)\) 为一个布尔函数，对于每一个 \(1\le a\le N\) 和 \(0\le b\)，如果存在一条从结点 \(1\) 到结点 \(a\) 的路径恰好经过了 \(b\) 条边，则函数值为真，否则为假。如果一条边被经过了多次，则这条边会被计算相应的次数。

Elsie 想要复制 Bessie。具体地说，她想要构造一个无向图 \(G'\)，使得对于所有的 \(a\) 和 \(b\)，均有 \(f_{G'}(a,b)=f_G(a,b)\)。

你的工作是计算 Elsie 可以构造的图 \(G'\) 的数量，对 \(10^9+7\) 取模。与 \(G\) 一样，\(G'\) 可以包含自环而不能包含重边（这意味着对于 \(N\) 个有标号结点共有 \(2^{\frac{N^2+N}{2}}\) 个不同的图）。

每个输入包含 \(T\)（\(1\le T\le \frac{10^5}{4}\)）组独立的测试用例。保证所有测试用例中的 \(N^2\) 之和不超过 \(10^5\)。

solution

对于一个点，记 \((a, b)\) 为从 1 号点到达这个点的最短路为 \(a\)，与 \(a\) 奇偶性不同的最短路长度为 \(b\)。将所有边分为三类：

\((a, b)\to (a+1, b+1)\) 就是直接转移。
\((a, b)\to(a+1, b - 1)\)，注意这里是在说对于点 \((a, b)\)，如果同时存在与 \((a-1, b+1)\) 和 \((a+1, b-1)\) 的连边，那么它合法（因为无向图，这个差值不能超过 \(1\)）
\((a, a+1)\) 的自环。

记 \(cnt_{a, b}\) 表示最短路为 \((a, b)\) 的点数。

\(\not\exists b\)

这是一个二分图，所有 \((a, ?)\) 向 \((a+1, ?)\) 连边，答案为所有点任意向上一层连接。直接特判掉。

\[ans=\prod_{i}(2^{cnt[a-1][?]}-1)^{cnt[a][?]} \]

\(\exists b\)

令 \(s=cnt[i][j], sp=cnt[i+1][j-1], sd=cnt[i-1][j-1]\)。

首先按照 \(a+b\) 分层 DP，又因为同一层可以相邻连边，所以考虑设计：\(f(i, j, p)\) 表示已经确定了 \(a+b<i+j\lor( a+b=i+j\land a > i)\) 的所有 \((a, b)\)，将有 \(p\) 个点以类型二（纯的类型二）连出，剩余 \(s-p\) 个点强制必须由类型一导出，即使它还可以连类型二的边。它的状态数明显是 \(O(n)\) 的。

若 \(j\neq i+1\) 即不需要考虑自环。

\[f(i, j, p)=\binom s p(2^{sd}-1)^{s-p}\sum_{q=0}^{sp}h(p, s, q, sp)f(i - 1, j + 1, q) \]

\(h(p, s_p, q, s_q)\) 表示有一个二分图，左部点 \(s_p\) 个点，右部点 \(s_q\) 个点，需要在二分图中连边，要求是有（已经选定的）\(p\) 个左部点和（已经选定的）\(q\) 个右部点必须由连边，\(s_p-p\) 和 \(s_q-q\) 则是随便连边都行。直接容斥有 \(i\) 个必须点没连边，有 \(j\) 个必须点没连边。

\[h(p, s_p, q, s_q)=\sum_{i=0}^{p}\sum_{j=0}^{q}\binom{p}{i}\binom{q}{j}(-1)^{i+j}2^{(s_p-i)(s_q-j)} \]

注意还有自环边，不妨考虑 \(f_{i, i+1, p}\)，它是唯一一个不能从 \(sp\) 转移，但是是自己连自环消化掉，同时向下一层连边可以满足条件的。转移特殊。

\[f(i, i+1, p)=\binom s p (2^{sd}-1)^{s-p}T(s, p) \]

\(T(s, p)\) 表示 \(s\) 个点玩自环，\(p\) 个点必须连边。容斥。

\[T(s, p) = \sum_{i=0}^p \binom p i (-1)^i 2^{(s-i)(s-i+1)/2} \]

答案是每一层的乘积。

\[Ans=\prod_{i=0}f(0, i, cnt[0][i]) \]

乘上和根不连通的点乱连。这里是因为最短路为 \(0\) 的 1 号点它必然没有下面的任何边给它，同时也没有其他点的最短路是 \(1\)，这样能统计到答案。

现在 \(O(n^4)\)。优化是关于 \(f(i, j, p)\) 的。

\[\begin{aligned} f(i, j, p)&=\binom s p(2^{sd}-1)^{s-p}\sum_{q=0}^{sp}\sum_{x=0}^{p}\sum_{y=0}^{q}\binom{p}{x}\binom{q}{y}(-1)^{x+y}2^{(s-x)(sp-y)}f(i - 1, j + 1, q)\\ &=\binom s p(2^{sd}-1)^{s-p}\sum_{q=0}^{sp}f(i - 1, j + 1, q)\sum_{x=0}^{p}\binom{p}{x}(-1)^x\sum_{y=0}^{q}\binom{q}{y}(-1)^y(2^{(s-x)})^{(sp-y)}\\ &=\binom s p(2^{sd}-1)^{s-p}\sum_{q=0}^{sp}f(i - 1, j + 1, q)\sum_{x=0}^{p}\binom{p}{x}(-1)^x(2^{(s-x)})^{(sp-q)}\sum_{y=0}^{q}\binom{q}{y}(-1)^y(2^{(s-x)})^{(q-y)}\\ &=\binom s p(2^{sd}-1)^{s-p}\sum_{q=0}^{sp}f(i - 1, j + 1, q)\sum_{x=0}^{p}\binom{p}{x}(-1)^x(2^{(s-x)})^{(sp-q)}(2^{(s-x)}-1)^q\\ \end{aligned} \]

\(O(n^3)\)。

code

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <queue>
#include <tuple>
#include <vector>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
template <unsigned umod>
struct modint {
  static constexpr int mod = umod;
  unsigned v;
  modint() : v(0) {}
  template <class T>
  modint(T x) {
    x %= mod;
    if (x < 0) x += mod;
    v = x;
  }
  modint operator+() const { return *this; }
  modint operator-() const { return modint() - *this; }
  friend int raw(const modint &self) { return self.v; }
  modint &operator+=(const modint &rhs) {
    v += rhs.v;
    if (v >= umod) v -= umod;
    return *this;
  }
  modint &operator-=(const modint &rhs) {
    v -= rhs.v;
    if (v >= umod) v += umod;
    return *this;
  }
  modint &operator*=(const modint &rhs) {
    v = static_cast<unsigned>(1ull * v * rhs.v % umod);
    return *this;
  }
  modint &operator/=(const modint &rhs) {
    assert(rhs.v);
    return *this *= qpow(rhs, mod - 2);
  }
  template <class T>
  friend modint qpow(modint a, T b) {
    modint r = 1;
    for (; b; b >>= 1, a *= a)
      if (b & 1) r *= a;
    return r;
  }
  friend modint operator+(modint lhs, const modint &rhs) { return lhs += rhs; }
  friend modint operator-(modint lhs, const modint &rhs) { return lhs -= rhs; }
  friend modint operator*(modint lhs, const modint &rhs) { return lhs *= rhs; }
  friend modint operator/(modint lhs, const modint &rhs) { return lhs /= rhs; }
  friend bool operator==(const modint &lhs, const modint &rhs) {
    return lhs.v == rhs.v;
  }
  friend bool operator!=(const modint &lhs, const modint &rhs) {
    return lhs.v != rhs.v;
  }
};
typedef modint<1000000007> mint;
template <int N>
struct C_prime {
  mint fac[N + 10], ifac[N + 10];
  C_prime() {
    for (int i = raw(fac[0] = 1); i <= N; i++) fac[i] = fac[i - 1] * i;
    ifac[N] = 1 / fac[N];
    for (int i = N; i >= 1; i--) ifac[i - 1] = ifac[i] * i;
  }
  mint operator()(int n, int m) {
    return n >= m ? fac[n] * ifac[m] * ifac[n - m] : 0;
  }
};
C_prime<100010> binom;
int n, m;
bool g[110][110];
int dis[110][2];
mint T[210][210];
void reset() {
  for (int i = 1; i <= n; i++) dis[i][0] = dis[i][1] = 1e9;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) g[i][j] = 0;
  }
}
bool bfs() {
  queue<pair<int, int>> q;
  q.emplace(1, 0);
  dis[1][0] = 0;
  while (!q.empty()) {
    int u, d;
    tie(u, d) = q.front();
    q.pop();
    for (int v = 1; v <= n; v++)
      if (g[u][v]) {
        if (dis[v][!d] > dis[u][d] + 1) {
          dis[v][!d] = dis[u][d] + 1;
          q.emplace(v, !d);
        }
      }
  }
  return dis[1][1] < 1e9;
}
mint bindp() {
  vector<int> cnt(n + 1, 0);
  for (int i = 1; i <= n; i++) cnt[min(dis[i][0], dis[i][1])]++;
  mint ans = 1;
  for (int i = 0; i < n; i++)
    ans *= qpow(qpow(mint(2), cnt[i]) - 1, cnt[i + 1]);
  return ans;
}
mint H(int p, int s, int q, int sp) {
  mint ans = 0;
  for (int x = 0; x <= p; x++) {
    mint tmp = qpow(mint(2), s - x);
    ans +=
        binom(p, x) * (x & 1 ? -1 : 1) * qpow(tmp, sp - q) * qpow(tmp - 1, q);
  }
  return ans;
}
mint dp() {
  vector<vector<int>> cnt(n * 3 + 10, vector<int>(n * 3 + 10));
  for (int i = 1; i <= n; i++) {
    if (dis[i][0] > dis[i][1]) swap(dis[i][0], dis[i][1]);
    cnt[dis[i][0]][dis[i][1]]++;
  }
  mint ans = 1;
  for (int sum = 1; sum <= 3 * n; sum += 2) {
    vector<vector<mint>> f((sum + 1) / 2);
    [&]() -> void {
      int i = (sum - 1) / 2;
      int s = cnt[i][i + 1], sd = i ? cnt[i - 1][i] : 0;
      f[i] = vector<mint>(s + 1);
      for (int p = 0; p <= s; p++) {
        f[i][p] = binom(cnt[i][i + 1], p) * qpow(qpow(mint(2), sd) - 1, s - p) *
                  T[s][p];
      }
    }();
    for (int i = (sum - 1) / 2 - 1; i >= 0; i--) {
      int s = cnt[i][sum - i], sd = i ? cnt[i - 1][sum - i - 1] : 0;
      int sp = cnt[i + 1][sum - i - 1];
      f[i] = vector<mint>(s + 1);
      for (int p = 0; p <= s; p++) {
        for (int q = 0; q <= sp; q++) {
          f[i][p] += H(p, s, q, sp) * f[i + 1][q];
        }
        f[i][p] *= binom(s, p) * qpow(qpow(mint(2), sd) - 1, s - p);
      }
    }
    ans *= f[0][cnt[0][sum]];
  }
  return ans;
}
int mian() {
  scanf("%d%d", &n, &m);
  reset();
  for (int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    g[u][v] = g[v][u] = true;
  }
  if (!bfs()) {
    printf("%d\n", raw(bindp()));
  } else {
    printf("%d\n", raw(dp()));
  }
  return 0;
}
void init() {
  for (int s = 0; s <= 200; s++) {
    for (int p = 0; p <= s; p++) {
      for (int i = 0; i <= p; i++) {
        T[s][p] += (i & 1 ? -1 : 1) * binom(p, i) *
                   qpow(mint(2), (s - i) * (s - i + 1) / 2);
      }
    }
  }
}
int main() {
  init();
  int T;
  scanf("%d", &T);
  while (T--) mian();
  return 0;
}