\(~~~~\) 怎么当天写好的东西又忘了发了/fn
一言
让死亡觊觎我
让恐惧亲吻我
来摧毁我深爱的一切
可仍夺不走我的选择
弹指间湮灭我
但命运打不败活着
让生命如剧烈的烟火
璀璨熄灭前也将点亮
孩童的双眸
——————《人是_》
今日复习内容:概率期望
「PKUWC2018」 随机游走
题意
\(~~~~\) 从 \(n\) 个点的树上给定的 \(x\) 点开始随机游走，每次询问至少走到 \(S\) 集合内所有的点一次的期望步数。
\(~~~~\) \(1\leq n\leq 18,1\leq Q\leq 5000\).
题解
\(~~~~\) 虽然这个转化过的题意看起来就很min-max容斥，但我们不用。
\(~~~~\) 套路性地设 \(dp_{S,i}\) 为 \(S\) 集合内已经被遍历过，当前在 \(x\) 点的答案，但注意到有环转移。
\(~~~~\) 为此我们把转移分为两部分，集合内和集合外的，在做dp的时候记录下 \(u\) 的父结点 \(fa\)，那么就维护 \(A_u,B_u\) 使得：
\[dp_u=A_u \times dp_{fa}+B_u \]\(~~~~\) ( \(dp\) 都是在 \(S\) 意义下的，所以省略掉了 \(S\) 维，下文非 \(S\) 维)
\(~~~~\) 对于叶子结点，都有 \(A_u=B_u=1\).
\(~~~~\) 否则对于 \(\pmb{u \not \in S}\)，有：
\[dp_u=\frac{1}{deg_u}\sum_{v \text{~near~} u}(f_{v}+1)\\ =\frac{1}{deg_u}dp_{fa_u}+\frac{1}{deg_u}\sum_{u=fa_v}(A_v\times dp_u+B_v+1)\\ =\frac{1}{deg_u-\sum_{u=fa_v}A_v}dp_{fa_u}+\frac{\sum_{u=fa_v}(B_v+1)+1}{deg_u-\sum_{u=fa_v}A_v} \]\(~~~~\) 由此可以推出 \(A_u\) 和 \(B_u\)：
\[A_u=\frac{1}{deg_u-\sum_{u=fa_v}A_v}\\B_u=\frac{\sum_{u=fa_v}(B_v+1)+1}{deg_u-\sum_{u=fa_v}A_v} \]\(~~~~\) 直接推出来就好了
\(~~~~\) 而对于 \(\pmb{u \in S}\):
\(~~~~\) 若 \(\{u\}=S\) ，直接取 \(A_u=B_u=0\).
\(~~~~\) 否则：\(A_u=0,B_u=\frac{1}{deg_u}\sum_{v~\text{near}~u}(f_{S+\{u\},v}+1)\)
\(~~~~\) 总之就是不存在环状更新所以随便推推就好了.
\(~~~~\) 最后把每个 \(dp\) 直接用 \(A,B\) 还原就好了，答案就每次直接得到集合后直接查dp数组就好了。
代码
查看代码
#include <bits/stdc++.h>
using namespace std;
template<typename T>void read(T &x)
{
T f=1;x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
x*=f;
}
int deg[20];
vector <int> G[20];
const int MOD=998244353;
inline int Add(int x,int y){int z=x+y;return z>=MOD?z-MOD:z;}
inline int Dec(int x,int y){int z=x-y;return z<0?z+MOD:z;}
inline int Mul(int x,int y){return 1ll*x*y%MOD;}
inline int qpow(int a,int b)
{
int ret=1;
while(b)
{
if(b&1) ret=Mul(ret,a);
b>>=1;a=Mul(a,a);
}
return ret;
}
int A[20],B[20];
int dp[262145][20];
void dfs1(int S,int u,int fa)
{
int SA=0,SB=0;A[u]=B[u]=0;
for(int i=0;i<(int)G[u].size();i++)
{
int v=G[u][i];
if(v==fa) continue;
dfs1(S,v,u);
if(!(S&(1<<(v-1)))) B[u]=Add(B[u],dp[S|(1<<(v-1))][v]);
else SA=Add(SA,A[v]),SB=Add(SB,B[v]);
}
A[u]=qpow(Dec(deg[u],SA),MOD-2);
B[u]=Mul(A[u],Add(deg[u],Add(B[u],SB)));
if(!fa) {A[u]=0;return;}
if(!(S&(1<<(fa-1)))) B[u]=Add(B[u],Mul(A[u],dp[S|(1<<(fa-1))][fa])),A[u]=0;
}
void dfs2(int S,int u,int fa)
{
dp[S][u]=Add(Mul(A[u],dp[S][fa]),B[u]);
for(int i=0;i<(int)G[u].size();i++) if(G[u][i]!=fa) dfs2(S,G[u][i],u);
}
int main() {
int n,Q,x;read(n);read(Q);read(x);
for(int i=1,u,v;i<n;i++)
{
read(u),read(v);
deg[u]++; deg[v]++;
G[u].push_back(v); G[v].push_back(u);
}
for(int S=(1<<n)-2;S>=1;S--) dfs1(S,1,0),dfs2(S,1,0);
while(Q--)
{
int k,p,S=(1<<n)-1;
read(k);
for(int i=1;i<=k;i++) read(p),S^=(1<<(p-1));
S|=(1<<(x-1));
printf("%d\n",dp[S][x]);
}
return 0;
}
「ZJOI2015」地震后的幻想乡
题意
\(~~~~\) 给出 \(n\) 个点的无向图 \(G\)，边权等概率为 \([0,1]\) 间的实数，求这个图的最小生成树的最大边权期望。
\(~~~~\) 对于 \(n\) 个取值 \([0,1]\) 的随机变量，其第 \(k\) 小值的期望为 \(\frac{k}{n+1}\).
\(~~~~\) \(1\leq n\leq 10,1\leq m\leq \frac{n(n-1)}{2}\).
题解
\(~~~~\) 不想细写这道题，所以随便写写。
\(~~~~\) 根据提示我们不难想用了 \(i\) 条边联通原图的方案数，自然我们就可以 \(dp\) 来考虑这个值。
\(~~~~\) 设 \(f_{S,i}\) 表示 \(S\) 集合内有 \(i\) 条边，不联通的方案数，\(g_{S,i}\) 表示 \(S\) 集合内有 \(i\) 条边，联通的方案数。同时记 \(S\) 集合内部有 \(E_S\) 条边。
\(~~~~\) 显然有 \(f_{S,i}+g_{S,i}=\binom{E_S}{i}\)，同时：
\[f_{S,i}=\sum_{T\subset S}\sum_{j=0}^{E_T}g_{T,j}\binom{E_{S-T}}{i-j}~~~~k\in T \]\(~~~~\) 其中 \(k\) 是一个在 \(S\) 中的固定的点。
\(~~~~\) 那么就随便推推就可以求出这两个数组。然后恰好在第 \(i\) 条边联通可以用 \(i\) 和 \(i-1\) 条边不联通的情况的差来表示 \(i\) 条边恰好联通。
\(~~~~\) 然后我们就可以写出答案：
\[\frac{1}{m+1}\sum_{k=1}^{m}\frac{f_{U,k}}{\binom{m}{k}} \]代码
查看代码
#include <bits/stdc++.h>
using namespace std;
template<typename T>void read(T &x)
{
T sig=1;x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')sig=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
x*=sig;
}
int Edge[1025];
double C[51][51];
double f[1025][51],g[1025][51];// 不联通/联通 的 选 i 条边的方案数
vector <int> G[15];
int main() {
int n,m;read(n);read(m);
for(int i=0;i<=m;i++)
{
C[i][0]=C[i][i]=1;
for(int j=1;j<i;j++) C[i][j]=C[i-1][j-1]+C[i-1][j];
}
for(int i=1,u,v;i<=m;i++)
{
read(u);read(v);
for(int j=0;j<(1<<n);j++)
if(((j>>(u-1))&1)&&((j>>(v-1))&1)) Edge[j]++;
}
g[0][0]=1;
for(int i=1;i<(1<<n);i++)
{
for(int j=0;j<=Edge[i];j++)
{
for(int k=(i-1)&i;k;k=(k-1)&i)
{
if(k&(i&(-i)))
{
for(int l=0;l<=Edge[k];l++)
f[i][j]+=g[k][l]*C[Edge[i^k]][j-l];//强制钦定某个点作为基准
}
}
g[i][j]=C[Edge[i]][j]-f[i][j];
}
}
double Ans=0;int U=(1<<n)-1;
for(int i=0;i<=m;i++) Ans+=f[U][i]/C[m][i];
printf("%.6f",Ans/(m+1));
return 0;
}
/*
让死亡觊觎我 让恐惧亲吻我
来摧毁我深爱的一切 可仍夺不走我的选择
弹指间湮灭我 但命运打不败活着
让生命如剧烈的烟火 璀璨熄灭前也将点亮
孩童的双眸
*/
按位或
题意
\(~~~~\) 每个时刻有 \(p_i\) 的概率将当前的数字或 \(i\in[0,2^n-1]\)，那么期望多少时刻可以将 \(0\) 变为 \(2^n-1\) 或
INF.
\(~~~~\) \(1\leq n\leq 20\).
题解
\(~~~~\) 一道挺nb的题。
\(~~~~\) 根据题意，记答案为 \(n\) 位中每一位第一次被选的最大值的期望，那就不难想到 \(\text{Min-Max}\) 容斥，对应地定义 \(\min(S)\) 为 \(S\) 中每一位第一次被选的最小值，那么：
\[E(\max(U))=\sum_{S\subset U}(-1)^{|T|} E(\min(S)) \]\(~~~~\) 那么现在的问题就是求：\(E(\min(S))\)，我们记 \(P(\min(S)=i)\) 表示 \(S\) 中的元素第一次出现的最小值为 \(i\) 的概率，显然：\(E(\min(S))=\sum_{i=0}^{n-1}P(\min(S=i))i\) .
\(~~~~\) 那么我们就需要求这个概率，强制前 \(i-1\) 次不取得 \(S\) 内，第 \(i\) 次取得 \(S\) 内，当然这两个概率加起来肯定是 \(1\) ，所以我们发现前一个单次的概率就是：
\[\sum_{T\cap S=\empty}P(T) \]\(~~~~\) 我们不管怎么求，不妨把这个值先记作 \(q\)。那么 \(E(\min(S))=\sum_{i=0}^{n-1}i\times q^{i-1}\times (1-q)\)
\(~~~~\) 运用错位相减和等差数列求和可以求到：\(E(\min(S))=\frac{1}{1-q}\)，那我们现在要做的就是求得 \(q\)。
\(~~~~\) 当然，我们发现求的 \(q\) 实际就是求 \(S\) 的补集的子集和，或者说 \(P\) 的超集和，也就是求每个集合的子集和。那怎么做最快？毕竟 \(3^n\) 一脸过不了的样子。
\(~~~~\) 这个时候就来深入发掘一些以前没有注意的性质，比如说 \(\text{FWT}\) 的或卷积。
\(~~~~\) 令 \(C'_{i}=\sum_{j \subset i} C_j\),若 \(C_{i}=\sum_{j~\text{or}~k}A_jB_k\)，那么 \(C'_{i}=\sum_{j\subset i,k\subset i} A_jB_k\)，因此 \(C'_{i}=A'_{i}B'_{i}\) ，看出来了吗？这就是 \(\text{FWT}\) 的或卷积。
\(~~~~\) 所以就变成 \(\mathcal{O(2^nn)}\) 求了！。
代码
查看代码
#include <bits/stdc++.h>
using namespace std;
template<typename T>void read(T &x)
{
T f=1;x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
x*=f;
}
int n,arr[1048580],PC[1048580];
double p[1048580];
void FWT(double *S)
{
for(int i=1;i<n;i<<=1)
for(int j=0;j<n;j+=i<<1)
for(int k=0;k<i;k++) S[i+j+k]+=S[j+k];
}
int main() {
read(n);n=1<<n;
for(int i=0;i<n;i++) scanf("%lf",&p[i]);
FWT(p);
for(int i=1;i<n;i++) PC[i]=PC[i>>1]+(i&1);
double Ans=0;
for(int i=1;i<n;i++)
{
if(1-p[(n-1)^i]<1e-8) return puts("INF")&0;
Ans+=1/(1-p[(n-1)^i])*(PC[i]&1?1:-1);
}
printf("%.9f",Ans);
return 0;
}
随机算法
\(~~~~\) 以前写的，不想写了。
鲜花
\(~~~~\) 今天是集中发现宝藏歌曲ヾ(@▽@)ノ
\(~~~~\) 《人是_》（词真的很难记，歌真的很难唱，简单来说就是我不配），但周深nb！！！！！
\(~~~~\) 《给你一瓶魔法药水》 很通俗易懂好吧，词我觉得也没啥问题，以前的词重复的多的是，而且压上韵了才好记好吧，下里巴人不好吗？
\(~~~~\) 《带我去找夜生活》 曲不是很抓耳，但觉得还是可以听。
标签：ch,frac,17,int,sum,fa,2023.1,dp From： https://www.cnblogs.com/Azazel/p/17060608.html