P7347 题解
yzy1
·
2022-01-12 20:18:17
·
题解
一年前，我报名了 MCOI Round 4，发现自己一道题也不会做，遗憾爆零。
简要题意
为表述方便和个人习惯原因，下面出现的所有大写字母 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 。
代码参考
```cpp
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;
}
```