自动搬运

查看原文

来自洛谷，原作者为

	yzy1 Меня мое сердце, в тревожную даль зовёт.

搬运于2025-08-24 22:29:00，当前版本为作者最后更新于2022-01-12 20:18:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

一年前，我报名了 MCOI Round 4，发现自己一道题也不会做，遗憾爆零。
一天前，我从比赛列表里挑了一场比赛开始 VP，发现这场比赛一年前自己打过，但是基本没有印象。想了俩小时 A 发现做法假了，后来一直卡在 A 上，遗憾爆零。

简要题意

为表述方便和个人习惯原因，下面出现的所有大写字母 $K$ 均代表原题面中小写字母 $k$ 的含义。

给定无自环无重边的无向图，$K$ 回合中每回合可以删去现有点集的任意真子集，求所有方案中每回合后剩下的图最大团大小之和模 $10^9+7$。

观察题意，发现这题是个二合一，首先预处理出所有子集的最大团后对于每个集合进行贡献的计算，累加即可。

1. DP 部分

首先我们考虑枚举子集，对于每个子集求出最大团的大小，这是一个基础的状压 DP，题解中不做过多讲述。预处理出 $F(i)$ 表示点集的所有大小为 $i$ 的子集的最大团大小之和，以便下一部分使用。

2. 计算贡献

对于每一种情况计算贡献。即答案为：在第 $k$ 回合结束后，剩下 $s$ 个点没被删的方案数乘上 $F(s)$。所以我们先要求出这个「方案数」。

这个部分我一开始想到的是一种假做法。具体可以见 这篇帖子。这个东西并不是组合数，原因是同一个点在不同的时间被删也是不同的方案。换句话说，我在帖子中的做法问题转化为把长度为 $k$ 的单调不升序列计数，是忘了点与点之间有区别，即把有标号计数想成了成无标号计数。

正确的做法为：假设在第 $k$ 回合结束时剩下 $s$ 个点没被删，则有 $(n-s)$ 个点在前 $k$ 回合的某个时刻被删了，单独对每个点考虑，只要两种方案中某个点被删的时刻不一样，这两种方案就不一样，共 $s^{n-k}$ 种。在 $k$ 回合后同理，有 $s$ 个点在后面的 $K-k$ 回合被删了，或者没被删，一共是 $k-y+1$ 种，所以是 $(k-y+1)^x$。综上，第 $k$ 回合结束时剩下 $s$ 个点没被删的方案数为 $k^{n-s}((K-k+1)^s-(K-k)^s)$。

枚举 $k,s$，则我们要求的答案为：

$$\sum_{k=0}^{K-1} \sum_{s=1}^n F(s) (K-k)^{n-s}((k+1)^s-k^s) $$

把 $F(s)$ 提出来，得：

$$\sum_{s=1}^n (F(s) \sum_{k=0}^{K-1} (K-k)^{n-s}((k+1)^s-k^s)) $$

发现要枚举一个 $k$，而 $K$ 的范围为 $10^9$，复杂度不能接受，考虑把式子中的 $(K-k)^{n-s}$ 和 $((k+1)^s-k^s)$ 拆开，根据二项式定理得：

$$\sum_{s=1}^n (F(s) \sum_{k=0}^{K-1} ((\sum_{i=0}^{n-s}\binom{n-s}{i}K^i(-k)^{n-s-i})(\sum_{i=0}^{s-1} \binom{s}{i} k^i)) $$

这是两个关于 $k$ 的最高次为 $n$ 的多项式，由于 $n$ 范围很小，我们可以把它们 $O(n^2)$ 暴力乘起来，得到一个最高次为 $2n$ 的多项式，我们记这个多项式的 $i$ 次项系数为 $P_i$，则：

$$\sum_{s=1}^n (F(s) \sum_{p=0}^{2n} (P_p\sum_{k=0}^{K-1} k^p)) $$

这就是一个经典的自然数幂和，直接伯努利数 $O(n^2)$ 预处理后 $O(n)$ 计算。

至此，我们以 $O(n^3)$ 的复杂度计算出了贡献。如果你在计算多项式乘法时使用了 $O(n\log n)$ 的算法，复杂度将优化至 $O(n^2 \log n)$，但是介于此题的数据范围，没有必要。

后来读 std 代码时发现其用了拉格朗日插值而不是暴力拆二项式化简，算是一题多解了。

3. 常数优化

如果你按照 $1\sim 2$ 中的步骤写完了代码，你会发现你的 $2^n$ 跑不过去 $n=28$，所以需要一些常数优化。

优化 A

首先，在写这篇题解时，本题的空间限制为 $160\text{ MB}$。你根本开不下 $2^{28}$ 个 int 甚至是 $2^{28}$ 个 unsigned char。所以可以采用一种特殊的方法来卡内存，由于图的最大团大小最大为点数，我们可以把一个 int 拆成六个来用，每个数字只用其中的 $5$ 个 bit 即 $2^5=32$，压缩空间来卡进本题的空间限制。

优化 B

我们可以把 $n$ 中的点拆成两部分，第一部分用普通的 $2^n$ DP。包含第二部分的点的点集的最大团在每次进行第一部分的 DP 转移时顺便转移。由于第二部分的点有三种状态：不选、选但不包括在最大团内，选且包括在最大团内，所以是 $O(3^n)$。这样的话设第一部分包含前 $n_0$ 个点，第二部分包括后 $n-n_0$ 个点，则时间复杂度为 $O(2^{n_0} 3^{n-n_0})$，空间复杂度为 $O(\max\{2^{n_0},3^{n-n_0}\})$，看似时间复杂度更劣但是在 $(n-n_0)$ 非常小的时候跑得比 $2^n$ 暴力 DP 要快接近 $400\text{ ms}$。

• 如果仅使用优化 A，可以做到 $840\text{ ms / }131\text{ MB}$，可以通过此题但是常数仍然不够优秀。
• 如果把优化 A 和 B 结合起来，$n_0$ 取 $n-1$，则可以做到 $620\text{ ms / }44\text{ MB}$，内存约为 std 的 $\dfrac 1 3$，但是用时较慢。
• 如果仅使用优化 B，$n_0$ 取 $n-2$，则可以做到 $330\text{ ms / }64\text{ MB}$，时间略优于 std 的同时内存只有 std 的 $\dfrac 1 2$。

代码参考

$O(n^2)$ 暴力计算多项式乘法，仅使用优化 B 且 $n_0=n-2$：

const int mo = 1e9 + 7;
const int N = 139;
int n, m, K, cnt[30], jc[N], jcinv[N], e[30], B[N], Binv[N], pwk[N], P[N];
// unsigned sz[(1 << 28) / 2 / 6 + 9];
unsigned char sz[(1 << 28) / 4 + 9];

ll Pow(ll a, ll b, const ll &m) {
  ll res = 1;
  a %= m;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m, b >>= 1;
  }
  return res;
}
inline int C(int n, int m) {
  if (m > n) return 0;
  return 1ll * jc[n] * jcinv[m] % mo * jcinv[n - m] % mo;
}
int Calc(int n, int k) {
  if (k == 0) return n;
  int res = 0;
  re (i, k + 1)
    res = (res + 1ll * C(k + 1, i) * B[k + 1 - i] % mo * Pow(n + 1, i, mo)) % mo;
  int ans = 1ll * res * Pow(k + 1, mo - 2, mo) % mo;
  return ans;
}
// inline unsigned char Get(int pos) { return (sz[pos / 6] >> (pos % 6 * 5)) & 0b11111; }
// inline void Set(int pos, unsigned char x) { sz[pos / 6] |= x << (pos % 6 * 5); }
#define Get(x) sz[x]
#define Set(x, y) sz[x] = y

signed main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m >> K;
  pwk[0] = jc[0] = jcinv[0] = 1;
  re (i, N - 1)
    jc[i] = 1ll * jc[i - 1] * i % mo, jcinv[i] = Pow(jc[i], mo - 2, mo),
    pwk[i] = 1ll * pwk[i - 1] * K % mo;
  B[0] = 1;
  re (i, 100) {
    B[i] = 0;
    rep (j, 0, i - 1)
      B[i] += 1ll * C(i + 1, j) * B[j] % mo, umod(B[i]);
    B[i] = (1ll * B[i] * -Pow(i + 1, mo - 2, mo) % mo + mo) % mo;
  }
  rep (i, 0, n - 1)
    e[i] |= 1 << i;
  re (i, m) {
    int f, t;
    cin >> f >> t, e[f] |= 1 << t, e[t] |= 1 << f;
  }
  cnt[1] = 2;
  cnt[2] = 1 + (e[n - 2] >> (n - 1));
  re (S, (1 << (n - 2)) - 1) {
    unsigned char res = max<unsigned char>(Get(S ^ lb(S)),
                                           Get((S ^ lb(S)) & e[__builtin_ctz(lb(S))]) + 1),
                  popc = __builtin_popcount(S);
    Set(S, res), cnt[popc] += res;
    unsigned char res2;
    cnt[popc + 1] += (res2 = max<unsigned char>(res, Get(S & e[n - 1]) + 1));
    cnt[popc + 1] += max<unsigned char>(res, Get(S & e[n - 2]) + 1);
    up(res2, Get(S & e[n - 2]) + 1);
    cnt[popc + 2] +=
        max<unsigned char>(res2, Get(S & e[n - 1] & e[n - 2]) + (e[n - 2] >> (n - 1)) + 1);
  }
  // 共 K 回合，第 k 回合时剩下一个大小为 s 的点集的方案数
  // 方案数 = k^(n-s)*((K-k+1)^s-(K-k)^s)
  int ans = 0;
  re (s, n) {
    int res = 0;
    memset(P, 0, sizeof P);
    rep (i, 0, n - s)
      rep (j, 0, s - 1)
        P[n - s - i + j] +=
            (((n - s - i) & 1) ? mo - 1ll : 1ll) * C(n - s, i) % mo * pwk[i] % mo * C(s, j) % mo,
            umod(P[n - s - i + j]);
    rep (p, 0, 2 * n) {
      int x = p == 0;
      x += Calc(K - 1, p);
      res += 1ll * x * P[p] % mo, umod(res);
    }
    ans += 1ll * res * cnt[s] % mo, umod(ans);
  }
  cout << ans << '\n';
  return 0;
}