Go语言视频零基础入门到精通

admin

写在这道题前面 : 网上的一些题解都不讲那个系数是怎么推得真的不良心 TAT
(不是每个人都有那么厉害啊 , 我好菜啊)
而且 LOJ 过的代码千篇一律 ... 那个系数根本看不出来是什么啊 TAT
后来做了 HDU 4035 终于会了.... 感谢 雕哥的帮助 !!!

题意 : #2542. 「PKUWC 2018」随机游走
题解 :

原本的模型好像我不会那个暴力dp .... 就是直接统计点集中最后经过的点的期望 , 也就是点集中到所有点步数最大值的期望 . (也许可以列方程高斯消元 ? 似乎没分)
但我们考虑转化一下 (因为原来 有道CLJ的题 也是求这个) 把最大值的期望用 最值反演(MinMax容斥) 转化成最小值的期望 就可以算了 ...

最值反演 (又称 MinMax容斥 ) :
\[\displaystyle \max\{S\}=\sum_{T\subseteq S}(-1)^{|T|-1}\min\{T\}\]
其中 \(S\) 是全集 , \(T\) 是它的一个子集 , 就有这个神奇的定理 ...
证明 ( 来自 DOFY大大的博客 ) :
设最大值为 \(x \in S\) ，那么构造映射 \(f(T) \to x \in T~?~T−x:T+x\) ， 也就是有 \(x\) 就去掉 ， 没有就加上 。那么当 \(T\) 不为空和 \({x}\) 时，\(T\) 与 \(f(T)\) 因为只相差一个最大值，最小值肯定相同，集合大小只相差 \(1\) ，就抵消了（一一映射），因为空集没有最小值，所以最后只剩下 \(\{x\}\) 的贡献。

然后有了这个 , 每次我们只需要求经过点集中点步数最少的贡献 .
假设我们当前有一个集合 \(S\) , 我们用 \(f(u)\) 表示从 \(u\) 出发 , 第一次访问 \(S\) 中节点的期望步数 .
所以我们有一些显然的式子 :

\(u \in S:\) \[f(u)=0\]
\(u \not \in S:\) 令 \(d\) 为 \(u\) 在树上的度数(连出来边数) , \(\mathrm{ch}\) 为 \(u\) 的儿子 , \(\mathrm{fa}\) 为 \(u\) 的父亲 . \[\displaystyle f(u)=[f(\mathrm{fa})+1+\sum (f(\mathrm{ch})+1)] \times \frac{1}{d}\] \[\displaystyle =\frac{1}{d}f(\mathrm{fa})+\frac{1}{d}\sum f(\mathrm{ch})+1\]

不难发现 每个点的答案可以只保留它父亲的答案和一个常数的贡献
( 可以理解成全都能倒推回去 , 因为那个就算没有 \(u \in S\) 的限制 , 叶子的贡献也只与父亲有关 )
假设令它为 \[f(u)=A_uf(\mathrm{fa})+B_u\] 以及 \(v = \mathrm{ch}\)
那么有 \[\displaystyle \sum f(\mathrm{ch})=\sum f(v) = \sum(A_v f_u + B_v)\]
把这个回代就有
\[\displaystyle (1-\frac{\sum A_v}{d}) f(u) = \frac{1}{d}f(\mathrm{fa})+(1+\frac{B_v}{d})\]
除过去就可以得到每个递推式的 \(A,B\) 了 qwq
然后随便写写就行啦 , 复杂度 \(O((n+Q) \cdot 2^n)\) ... 其实后面那个复杂度是对于每个询问枚举子集 .
预处理的话 , 复杂度就变成 \(O(n\cdot 2^n + 3^n)\) 啦 ...
似乎都可以轻松过掉 ?

代码 :

1. [code]#include <bits/stdc++.h>
2. #define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
3. #define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
4. #define Set(a, v) memset(a, v, sizeof(a))
5. using namespace std;
7. inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
8. inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}
10. inline int read() {
11.     int x = 0, fh = 1; char ch = getchar();
12.     for (; !isdigit(ch); ch = getchar()) if (ch == "-") fh = -1;
13.     for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
14.     return x * fh;
15. }
17. void File() {
18. #ifdef zjp_shadow
19.     freopen ("2542.in", "r", stdin);
20.     freopen ("2542.out", "w", stdout);
21. #endif
22. }
24. typedef long long ll;
25. const int Mod = 998244353;
27. inline ll fpm(ll x, int power) {
28.     ll res = 1; x = (x % Mod + Mod) % Mod;
29.     for (; power; power >>= 1, (x *= x) %= Mod)
30.         if (power & 1) (res *= x) %= Mod;
31.     return res;
32. }
34. const int N = 20;
35. int n, Q, rt, d[N];
36. vector<int> G[N]; ll A[N], B[N], invd[N];
38. void Dp(int u, int fa, int S) {
39.     if ((1 << (u - 1)) & S) { A[u] = B[u] = 0; return ; }
41.     ll totA = 0, totB = 0;
42.     for (int v : G[u]) if (v ^ fa)
43.         Dp(v, u, S), totA += A[v], totB += B[v];
44.     totA %= Mod, totB %= Mod;
46.     ll coef = fpm(Mod + 1 - totA * invd[u], Mod - 2);
47.     A[u] = invd[u] * coef % Mod;
48.     B[u] = (1 + totB * invd[u] % Mod) * coef % Mod;
49. }
51. ll Minv[1 << 18]; int bit[1 << 18];
53. int main () {
54.     File();
56.     n = read(); Q = read(); rt = read();
57.     For (i, 1, n - 1) {
58.         int u = read(), v = read();
59.         G[u].push_back(v); G[v].push_back(u);
60.         ++ d[u]; ++ d[v];
61.     }
62.     For (i, 1, n) invd[i] = fpm(d[i], Mod - 2);
64.     int maxsta = (1 << n) - 1;
65.     For (i, 0, maxsta) {
66.         Dp(rt, 0, i);
67.         Minv[i] = B[rt];
68.         bit[i] = bit[i >> 1] + (i & 1);
69.     }
71.     while (Q --) {
72.         int k = read(), sta = 0;
73.         while (k --) sta |= (1 << (read() - 1));
74.         ll ans = 0;
75.         for (int i = sta; i; i = (i - 1) & sta)
76.             ans += (bit[i] & 1 ? 1 : -1) * Minv[i];
77.         ans = (ans % Mod + Mod) % Mod;
78.         printf ("%lld\n", ans);
79.     }
81.     return 0;
82. }

复制代码

[/code]