题目描述
给定一棵 $n(n<=18)$ 个结点的树,你从点 $x$ 出发,每次等概率随机选择一条与所在点相邻的边走过去。
有 $Q(Q<=5000)$ 次询问,每次询问给定一个集合 $S$,求如果从 $x$ 出发一直随机游走,直到点集 $S$ 中所有点都至少经过一次的话,期望游走几步。
特别地,点 $x$(即起点)视为一开始就被经过了一次。
答案对 $998244353$ 取模。
Solution
这题首先我们要知道min-max容斥。
我们可以试着可以证明:
首先我们将$x$从小到大排序,则有$$max\left\{x_1,x_2,…x_n\right\}=\sum_{i=1}^{n}\sum_{j=0}^{n-i}(\binom{n-i}{j}*(-1)^{j+2})*x_i$$
即我们算每一个$x_i$的贡献,枚举最小的$x_i$,然后在$i$后面选任意多数,那么最小值为$x_i$。
然后我们发现中间的$\sum_{j=0}^{n-i}(\binom{n-i}{j}*(-1)^{j+2})$只在$n-i=0$时为$1$,其余情况和均为$0$,所以我们发现这个式子的结果最终等于$x_n$,即$max\left\{x_1,x_2,…x_n\right\}$。
那么我们回到这题,令$Ci$为第i个点到达的时刻。
令$E[max\left\{S\right\}]=\max_{i\in S}c[i]$,$E[min\left\{S\right\}]=\min_{i\in S}c[i]$。
$$E[max\left\{S\right\}]=\sum_{S’\subseteq S}(-1)^{\left|S’\right|+1}*E[min\left\{S’\right\}]$$
那么要求的就是$E[max\left\{x_1,x_2,…x_t\right\}]$,所以我们只要求出$E[min\left\{x_1,x_2,…x_t\right\}]$即到达集合中任意一个点就停止的期望步数即可。
这时我们可以列出每个点的期望方程,令$f[i]$表示第i个点的期望步数,那么有
若u点不为根且u点不为停止点,则$f[u]=\frac{\sum_{v}(f[v]+1)}{deg[u]}+\frac{f[fa[u]]+1}{deg[u]}$;
若u点为根,则$f[u]=\frac{\sum_{v}(f[v]+1)}{deg[u]}$;
若u点为停止点,则$f[u]=0$。
那么我们可以用$O(n^3)$的高斯消元来做,但我们有更好的办法。
对于树上高斯消元,我们有一种类似与树型DP的做法,即用fa[u]来表示u。
我们发现u的儿子可以被u表示,那么在上面的式子中,未知数即为$f[u]$和$f[fa[u]]$,那么我们便可以用$f[u]=a[u]*f[fa[u]]+b[u]$来表示$f[u]$。
从上面的式子我们可以推得
$$f[u]=\frac{\sum_{v}(a[v]*f[u]+b[v]+1)}{deg[u]}+\frac{f[fa[u]]+1}{deg[u]}$$
$$(deg[u]-\sum_{v}a[v])f[u]=\sum_{v}(b[v]+1)+f[fa[u]]+1$$
$$f[u]=\frac{1}{deg[u]-\sum_{v}a[v]}*f[fa[u]]+\frac{\sum_{v}(b[v]+1)+1}{deg[u]-\sum_{v}a[v]}$$
所以我们把$f[u]$化成了$f[u]=a[u]*f[fa[u]]+b[u]$的形式。
最终我们要求的即为$f[root]=\frac{\sum_{v}(b[v]+1)}{deg[root]-\sum_{v}a[v]}$,那么用上面的方法计算即为$b[root]$。
这样我们就解决了这道题,时间复杂度$O(n*2^n+Q*n)$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
#include<bits/stdc++.h> #define mo 998244353 #define ll long long using namespace std; const int N=20; int n,Q,X,tot,Next[N<<1],head[N],tree[N<<1],deg[N],num[1<<N],F[1<<N],a[N],b[N]; void add(int x,int y) { tot++; Next[tot]=head[x]; head[x]=tot; tree[tot]=y; } ll mi(ll x,int y) { ll ans=1; while (y) { if (y&1) ans=ans*x%mo; x=x*x%mo; y>>=1; } return ans; } void dfs(int u,int fa,int S) { if (S&(1<<u-1)) { a[u]=b[u]=0;return;} a[u]=deg[u];b[u]=0; for (int i=head[u];i;i=Next[i]) { int v=tree[i]; if (v!=fa) { dfs(v,u,S); a[u]=(a[u]-a[v]+mo)%mo; b[u]=(b[u]+b[v])%mo; } } a[u]=mi(a[u],mo-2)%mo; b[u]=(ll)a[u]*(b[u]+deg[u])%mo; } int main() { scanf("%d%d%d",&n,&Q,&X); for (int i=1;i<(1<<n);i++) num[i]=num[i>>1]+(i&1); for (int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); add(x,y);add(y,x); deg[x]++;deg[y]++; } for (int i=0;i<(1<<n);i++) { dfs(X,0,i); F[i]=b[X]; if (!(num[i]&1)) F[i]=mo-F[i]; } for (int i=1;i<=n;i++) for (int j=0;j<(1<<n);j++) if (j&(1<<i-1)) F[j]=(F[j]+F[j^(1<<i-1)])%mo; for (int i=1;i<=Q;i++) { int K,sta=0,x; scanf("%d",&K); for (int j=1;j<=K;j++) { scanf("%d",&x); sta=sta|(1<<x-1); } printf("%d\n",F[sta]); } return 0; } |
太强了,我好害怕啊
怎么都是我听不懂的东西
前排膜大佬