例1 洛谷P1850 [NOIP2016 提高组] 换教室

题意

有 $n$ 个时间段,每个时间段有 $2$ 节课程。其中在时间段 $i$ 的两节课,分别在教室 $c_i, d_i$ 上。

对于所有的时间段 $i$,牛牛预先被安排在 $c_i$ 上课。

对于一个时间段 $i$,牛牛可以申请转到教室 $d_i$ 上课。但这个申请只有 $k_i$ 的概率被批准。

牛牛最多可以申请 $m$ 个时间段,但是所有申请必须一次性提交

同时,校园可以看作是一个图,教室为节点(共 $v$ 个教室),教室之间有双向边(共 $e$ 个边),边有长度。

每当一节课结束后,牛牛会沿着最短路径走到下一节课所在的教室。

现在牛牛想知道,怎么申请时间段,使得他在教室间移动的路程长度期望值最小,求出这个最小期望。

其中,$1 \leq n \leq 2000, 0 \leq m \leq 2000, 1 \leq v \leq 300, 0 \leq e \leq 90000$。

题解

首先用 floyd $O(n^3)$ 求出每两个节点之间的最短路长度。

然后一个很明显的 DP 思路:

设 $dp[i][j][k]$ 为:当前考虑第 $i$ 个时间段,还剩下 $j$ 次申请机会,$k=0/1$ 代表当前在哪个教室。

这个思路看起来很有道理,但是不正确。因为题目提到 所有申请必须一次性提交

而 $k=0/1$ 如果代表当前在哪个教室,就说明我们已经知道了当前的申请结果,来考虑后面的时间段是否申请。这会导致我们的决策更加的精明,从而使得答案小于正确答案。


正确的状态为:$dp[i][j][k]$:当前考虑第 $i$ 个时间段,还剩下 $j$ 次申请机会,$k=0/1$ 代表当前 是否申请过,$dp$ 数组的值代表路径长度期望值。

然后转移的时候,就要分类讨论 是否申请下一个时间段,得到两个结果,取 $\min$ 就得到了当前状态的答案。

代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2002;

int n,m,v,e, c[maxn], d[maxn];
double k[maxn];
int adj[302][302], dis[302][302];
double dp[maxn][maxn][2];

// K = 1: 已申请, K = 0: 未申请
double dfs(int i, int j, int K) {
    if (i >= n) return 0.0;
    if (dp[i][j][K] >= 0.0) return dp[i][j][K];
    double r1 = 1e18, r2 = 1e18;

    // next: 申请/不申请
    if (K) {
        r1 = k[i] * (dfs(i+1, j, 0) + dis[d[i]][c[i+1]]) + (1.0 - k[i]) * (dfs(i+1, j, 0) + dis[c[i]][c[i+1]]);
        if (j > 0)
            r2 = k[i] * (k[i+1] * (dfs(i+1, j-1, 1) + dis[d[i]][d[i+1]]) + (1.0 - k[i+1]) * (dfs(i+1, j-1, 1) + dis[d[i]][c[i+1]])) 
            + (1.0 - k[i]) * (k[i+1] * (dfs(i+1, j-1, 1) + dis[c[i]][d[i+1]]) + (1.0 - k[i+1]) * (dfs(i+1, j-1, 1) + dis[c[i]][c[i+1]]));
    } else {
        r1 = 1.0 * (dfs(i+1, j, 0) + dis[c[i]][c[i+1]]);
        if (j > 0) r2 = k[i+1] * (dfs(i+1, j-1, 1) + dis[c[i]][d[i+1]]) + (1.0 - k[i+1]) * (dfs(i+1, j-1, 1) + dis[c[i]][c[i+1]]);
    }

    return dp[i][j][K] = min(r1, r2);
}

int main() {
    scanf("%d%d%d%d",&n,&m,&v,&e);
    for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &d[i]);
    for (int i = 1; i <= n; i++) scanf("%lf", &k[i]);

    for (int i = 1; i <= e; i++) {
        int u,v,w; scanf("%d%d%d",&u,&v,&w);
        if (adj[u][v]) {
            if (adj[u][v] > w) adj[u][v] = adj[v][u] = w;
        } else adj[u][v] = adj[v][u] = w;
    }
    memset(dis, 0x3f3f3f3f, sizeof(dis));
    for (int i = 1; i <= v; i++) {
        for (int j = 1; j <= v; j++) {
            if (adj[i][j])
                dis[i][j] = dis[j][i] = adj[i][j];
        }
    }
    for (int i = 1; i <= v; i++) dis[i][i] = 0;
    for (int k = 1; k <= v; k++) {
        for (int i = 1; i <= v; i++) {
            for (int j = 1; j <= v; j++) {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }



    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            dp[i][j][0] = dp[i][j][1] = -1;
        }
    }

    double ans1 = 1.0 * dfs(1, m, 0), ans2 = 1e18;
    if (m > 0) {
        ans2 = 1.0 * dfs(1, m-1, 1);
    }
    
    double ans = min(ans1, ans2);
    printf("%.2lf\n", ans);
    
}

例2 洛谷P3830 [SHOI2012]随机树

题意

给定一棵二叉树,初始状态下只有根节点。每次操作会在所有叶子节点中,等概率选择一个,给它添加左右两个child。

给定正整数 $n$,求:对于由此生成的含有 $n$ 个叶子节点的二叉树,输出 叶子结点深度 的期望值,和 树深度 的期望值。

其中,$n \leq 100$,根节点的深度为 $0$。

题解

先考虑一下 叶子结点深度 的期望值。

每次扩展一个叶子,设其原深度为 $x$,相当于总深度增加了 $2(x+1) - x = x+2$。

所以设,对于 $n$ 个叶子的树,平均叶子深度若为 $f_n$,则总深度为 $f_n * n$。

所以在这个树中选择一个叶子展开,平均叶子增加深度为 $f_n + 2$。

所以 $f_{n+1} = \frac{(f_n * n + f_n + 2)}{n+1} = f_n + \frac{2}{n+1}$。


然后看第二问,树深度 的期望值。

在做到这里的时候我的想法出现了一些偏差:我一直在考虑如何将 叶子数为 $(n-1)$ 的状态转移到 叶子数为 $n$ 的状态。

但是实际做法是一个很神奇的想法:

使用 左,右子树 进行转移。

设 $dp[i][j]$ 为:有 $i$ 个叶子节点,深度 $\geq j$ 的概率,枚举 左子树 叶子节点数量 $k$,有以下转移:

$$dp[i][j] = \frac{\sum\limits_{k=1}^{i-1}dp[k][j-1] + dp[i-k][j-1] - dp[k][j-1] * dp[i-k][j-1]}{i-1}$$

什么意思呢?我们先看分子:

显然对于根节点来说,它左右子树必然不为空,所以转移的时候 $k=1$ 开始,到 $(i-1)$,能转移的状态是深度为 $j-1$ 的,所以都加上。

但是因为两边深度均为 $j-1$ 算重了,所以用容斥减去重复的部分 $dp[k][j-1] * dp[i-k][j-1]$。

分子 $(i-1)$ 是哪里来的呢?因为考虑到期望的定义是 值 乘上 概率 之和。对于 $k$ 不同的情况,有不同的概率。

但是我们可以得出结论,每一种概率都是相同的。

意思就是:对于一棵 $n$ 个叶子节点的树,左子树拥有的叶子节点数量为 $1,2,…,n-1$,发生的概率均相同。


证明:用数学归纳法即可。

首先可以得到对于 $n=2$ 是相同的。

我们设 $p[i][j]$ 为:叶子节点数为 $i$ 的树中,左子树有 $j$ 个叶子节点的概率。

则 $p[i][j] = p[i-1][j-1] * \frac{j-1}{i-1} + p[i-1][j] * \frac{(i-1)-j}{i-1}$

由数学归纳法,设对于 $(i-1)$ 而言,$\forall j \in [1,i-2], p[i-1][j] = \frac{1}{i-2}$。

则 $p[i][j] = \frac{1}{i-2} * \frac{j-1}{i-1} + \frac{1}{i-2} * \frac{(i-1)-j}{i-1} = \frac{1}{i-1}$,与 $j$ 无关。

代码
#include <bits/stdc++.h>
using namespace std;
int q,n;
double dp[102][102];  // dp[i][j]: 对于第i步,深度为j的期望叶子节点期望个数

int main() {
    scanf("%d%d",&q,&n);
    double ans = 0.0;
    if (q == 1) {
        
        dp[1][0] = 1.0;

        // 第 i 步有 2i-1 个节点, 有 i 个叶子节点
        for (int i = 1; i <= n-1; i++) {
            for (int j = 0; j <= i-1; j++) {
                double p = dp[i][j] / (i);
                dp[i+1][j+1] += p * 2.0;
                dp[i+1][j] -= p * 1.0;
            }
            for (int j = 0; j <= i-1; j++) dp[i+1][j] += dp[i][j];
        }
        for (int j = 0; j <= n; j++) ans += dp[n][j] * j;
        printf("%.6f\n", ans/(n));
    } else {
        for (int i = 0; i <= n; i++) dp[i][0] = 1.0;
        dp[0][0] = 1.0;
        dp[1][0] = 1.0;
        dp[2][0] = dp[2][1] = 1.0;
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                for (int k = 1; k <= i-1; k++) {
                    dp[i][j] += dp[k][j-1] + dp[i-k][j-1] - dp[k][j-1] * dp[i-k][j-1];
                }
                dp[i][j] /= (i-1);
            }
        }
        for (int j = n-1; j >= 0; j--) {
            double p = - dp[n][j+1] + dp[n][j];
            ans += (p * j);
        }
        printf("%.6f\n", ans);
    }
}

例3 洛谷 P2221 [HAOI2012]高速公路

题意

一条线上有 $n$ 个收费站,从第 $i$ 个到第 $(i+1)$ 个收费站之间有一条路,通过一条路需要交费。初始状态下,每条路的费用为 $0$。

给定 $m$ 个询问,每个询问为两种之一:

$C ~ l ~ r ~ v$:将第 $l$ 到第 $r$ 个收费站之间的所有道路费用增加 $v$。

$Q ~ l ~ r$:回答在第 $l$ 到第 $r$ 个收费站之间,等概率选择两个不同的收费站 $a,b$,从 $a$ 行驶到 $b$ 的期望费用?

其中,$1 \leq n,m \leq 10^5, -10^4 \leq v \leq 10^4$,在任何时间段,任何一条道路的费用绝对值不超过 $10^4$。

题解

线段树。首先把收费站转成道路,就对于所有的 $l,r$,都改成 $l,r-1$。对于线段树,从 $1$ 和 $n-1$ 之间build。

计算期望的时候,可以知道分母是 $C_{r-l}^2$。分子是从 $l,r$ 之间所有的选择之和。

现在问题是:如何求出一个区间内,所有可能的 $l,r$ 组合的区间和的和?

数学表达:对于区间 $[L,R]$,求

$$\sum\limits_{i=L}^R\sum\limits_{j=i}^R sum(arr[i…j])$$


直接从线段树的角度来考虑:一个区间的 $\sum\limits_{i=l}^r\sum\limits_{j=i}^r sum(arr[i…j])$,能否用左右区间的这个信息来维护?

可以的,注意到:对于一个区间 $[L,R]$ 来说,所有 $l,r$ 的组合可以分为三种:

  1. $l,r \in [L, mid]$
  2. $l,r \in [mid+1, R]$
  3. $l \in [L, mid], r \in [mid+1, R]$

前两种已经被子区间用到了,只要考虑第三种情况即可。

所以问题就转化成:

对于一个区间 $[L,R]$,求

$$\sum\limits_{i=L}^{mid}\sum\limits_{j=mid+1}^R sum(arr[i…j])$$


对于这个问题,我们可以固定 $l,r$ 其中之一。

比如我们固定 $l=mid$,那么 $r$ 会从 $mid+1$ 一直iterate到 $R$,得到的 sum 就是:

$$sum(arr[mid…mid+1]) + sum(arr[mid…mid+2]) + … + sum(arr[mid…R])$$

把它从 $mid$ 的位置拆开来,就等于:

$$(R-mid) * arr[mid] + sum(arr[mid+1…mid+1]) + sum(arr[mid+1…mid+2]) + sum(arr[mid+1…R])$$

$$=(R-mid) * arr[mid] + \sum\limits_{l=mid+1}^R sum(arr[l…R])$$

发现:$\sum\limits_{l=mid+1}^R sum(arr[l…R])$ 是可以用线段树来维护的。


所以最后,我们维护几个值:

  1. 一个区间的 $sum$
  2. 一个区间的 $lsum$:指 $\sum\limits_{r=L}^R sum(arr[L…r])$
  3. 一个区间的 $rsum$:指 $\sum\limits_{l=R}^L sum(arr[l…R])$
  4. 一个区间的 $allsum$:指所求,即 $\sum\limits_{i=L}^{mid}\sum\limits_{j=mid+1}^R sum(arr[i…j])$

转移方程见代码。


• 注意到在线段树 $query$ 的过程中,合并的时候仍然要用转移方程,而不能直接用左右的 $allsum$ 的和。

代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;

ll gcd(ll a, ll b) {
    if (!b) return a;
    return gcd(b, a%b);
}

ll cnt[maxn];
ll n,m; char op;

struct node {
    ll lsum, rsum, sum, allsum;
    ll lazy = 0;
} tr[maxn<<2];

ll C(ll a) {
    return a * (a+1) / 2LL;
}

void push_down(ll cur, ll L, ll R) {
    if (!tr[cur].lazy) return;
    ll lazy = tr[cur].lazy;
    tr[cur].lazy = 0;
    ll mid = (L+R) >> 1;
    ll l = cur<<1, r = l+1;
    tr[l].lazy += lazy, tr[r].lazy += lazy;

    ll llen = (mid - L + 1), rlen = (R - mid);

    tr[l].sum += llen * lazy;
    tr[r].sum += rlen * lazy;

    tr[l].lsum += C(llen) * lazy;
    tr[r].lsum += C(rlen) * lazy;

    tr[l].rsum += C(llen) * lazy;
    tr[r].rsum += C(rlen) * lazy;

    tr[l].allsum += cnt[llen] * lazy;
    tr[r].allsum += cnt[rlen] * lazy;
}

void push_up(ll cur, ll L, ll R) {
    ll l = cur<<1, r = l+1;
    ll mid = (L+R) >> 1;
    ll llen = (mid - L + 1), rlen = (R - mid);
    tr[cur].sum = tr[l].sum + tr[r].sum;
    tr[cur].lsum = tr[l].lsum + tr[r].lsum + rlen * tr[l].sum;
    tr[cur].rsum = tr[l].rsum + tr[r].rsum + llen * tr[r].sum;
    tr[cur].allsum = tr[l].rsum * rlen + tr[r].lsum * llen + tr[l].allsum + tr[r].allsum;
}

void update(ll cur, ll l, ll r, ll L, ll R, ll val) {
    ll len = (r-l+1);
    if (L <= l && R >= r) {
        tr[cur].lazy += val;
        tr[cur].sum += len * val;
        tr[cur].lsum += C(len) * val;
        tr[cur].rsum += C(len) * val;
        tr[cur].allsum += cnt[len] * val;
        return;
    }
    ll mid = (l+r) >> 1;
    push_down(cur, l, r);
    if (L <= mid) update(cur<<1, l, mid, L, R, val);
    if (R > mid) update(cur<<1|1, mid+1, r, L, R, val);
    push_up(cur, l, r);
}

node query(ll cur, ll l, ll r, ll L, ll R) {
    if (L <= l && R >= r) {
        return tr[cur];
    }
    push_down(cur, l, r);
    ll mid = (l+r) >> 1;
    node lnode {}, rnode {}, curnode {};
    ll llen = max(mid - max(L, l) + 1, 0), rlen = max(min(R, r) - mid, 0);
    if (L <= mid) lnode = query(cur<<1, l, mid, L, R);
    if (R > mid) rnode = query(cur<<1|1, mid+1, r, L, R);
    curnode.sum = lnode.sum + rnode.sum;
    curnode.lsum = lnode.lsum + rnode.lsum + rlen * lnode.sum;
    curnode.rsum = lnode.rsum + rnode.rsum + llen * rnode.sum;
    curnode.allsum = lnode.allsum + rnode.allsum + lnode.rsum * rlen + rnode.lsum * llen;
    push_up(cur, l, r);
    return curnode;
}

void init() {
    cnt[1] = 1;
    cnt[2] = 4;
    for (ll i = 3; i <= maxn-5; i++) {
        ll mid = (1+i) >> 1;
        ll j = mid, k = i-mid;
        cnt[i] = cnt[j] + cnt[k] + C(j) * k + C(k) * j;
    }
}

int main() {
    fastio;
    cin >> n >> m;
    init();
    n--;
    while (m--) {
        cin >> op;
        if (op == 'C') {
            ll l,r,v; cin >> l >> r >> v;
            r--;
            update(1, 1, n, l, r, v);
        } else {
            ll l,r; cin >> l >> r;
            r--;
            ll res = query(1, 1, n, l, r).allsum;
            int flag = 1;
            if (res < 0) flag = -1;
            res = abs(res);
            ll d = C(r-l+1);
            ll g = gcd(res,d);
            res /= g;
            d /= g;
            if (flag < 0) cout << "-";
            cout << res << "/" << d << "\n";
        }
    }
}

例4 CF850F Rainbow Balls

题意

有一个袋子,袋子中有 $n$ 种颜色的球,第 $i$ 种颜色的球有 $a_i$ 个。

现在持续进行以下操作:

有顺序地随机取出两个球,把第二个球涂成第一个球的颜色,然后把两个球都放回袋子。

求操作次数的期望,使得所有球的颜色相同?

• 可以证明最终答案为 $\frac{P}{Q}$ 的形式,输出 $P \times Q^{-1}$ 在 $\mod (10^9+7)$ 下的值。

其中,$n \leq 2500, 1 \leq a_i \leq 10^5$。

题解

一个比较明显的想法是:先决定最终的颜色

在决定好最终颜色(比如红色)后,其他颜色都可以看作同一种颜色(非红色)。

在问题变成 红色/非红色 之后,可以发现使用 DP 可以表示递推状态。

并且 DP 的状态仅与 红色球 的数量有关。


令 $s = \sum\limits_{i=1}^na_i$ (表示总球数)。

令 $f_i$ 为:现在有 $i$ 个红色球,把所有球都变成 红色 的期望操作次数。

首先可以知道,$f_s = 0$,且 $f_0$ 不存在。


然后考虑转移方程:

对于 $f_i$ 来说,有 $i$ 个红色球,$(s-i)$ 个非红色球。

那么随机取两个球,能对状态产生影响的就两种情况:

  1. 红 + 非红 -> 红色球数 加 $1$
  2. 非红 + 红 -> 红色球数 减 $1$

这两种情况的样本大小均为 $i(s-i)$,而总样本空间的大小为 $s(s-1)$。

所以,令 $$p_i = \frac{i(s-i)}{s(s-1)}$$

则从 $f_i$ 转移到 $f_{i-1}, f_{i+1}$ 的概率均为 $p_i$,而什么都没发生(转移回 $f_i$)的概率为 $(1-2p_i)$。


如此,我们可以列出方程:

$$f_i = p_if_{i-1} + p_if_{i+1} + (1-2p_i)f_i + v$$

$v$ 是什么?

注意到转移时,也是会消耗 $1$ 次操作的。

• 但是注意,$v$ 不等于 $1$!

这是因为 $f_i$ 的意义是:最终颜色为红色 的情况下的操作期望值。

所以 $v$ 应该等于 这一次操作 被分到 最终颜色为红色 情况下的 贡献(对于期望值的贡献)。

相当于把 $1$ 次操作拆成很多份,每一份分别贡献给了每一种最终颜色对应的期望。


结论:$v = \frac{i}{s}$

证明:从字面上理解来看,$v$ 的值代表了在有 $i$ 个红色球的情况下,最终颜色为红色的概率。

所以我们求出这个概率即可。

设 $g_i$ 为:有 $i$ 个红色球的情况下,最终颜色为红色的概率。

易知 $g_0 = 0, g_s = 1$。

并且同上转移方程,可得方程:

$$g_i = p_ig_{i-1} + p_ig_{i+1} + (1-2p_i)g_i$$

即 $2g_i = g_{i-1} + g_{i+1}$,也就是 $g_{i+1} - g_i = g_i - g_{i-1}$,等差数列。

所以 $g_i = \frac{i}{s}$,证毕。


所以我们最终的方程就有了:

$$f_i = p_if_{i-1} + p_if_{i+1} + (1-2p_i)f_i + \frac{i}{s}$$

化简一下可得:

$$2f_i = f_{i-1} + f_{i+1} + \frac{s-1}{s-i}$$

其中,$f_s = 0, f_0$ 不存在。

处理不存在的值 $f_0$,我们不能把它当成 $\inf$,只能把其当成 $0$。

所以代入 $i=1$,有 $f_2 = 2f_1 - 1$。

$i$ 的有效值为 $i \in [1,s-1]$,未知量为 $f_1, f_2, …, f_{s-1}$,总共有 $(s-1)$ 个方程 和 $(s-1)$ 个未知量,发现是可以解出来的。

但是问题在于 $s$ 的范围高达 $2500 * 10^5$,不能直接用高斯消元来解。

所以只能手推式子了,联立 $(s-1)$ 个方程后,可以手推得出

$$f_1 = \frac{(s-1)^2}{s}$$

剩下的 $f_2, …, f_{s-1}$ 也可以得出了。

枚举所有最终颜色的情况,最终的答案就为 $ans = \sum\limits_i{f_{a_i}}$

代码
#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9+7;
const int maxn = 2505;
const int maxm = 1e5+5;

ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = (res * a) % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll a) {
    return qpow(a, mod-2);
}


int n;
ll arr[maxn], s = 0;
ll f[maxm];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i], s += arr[i];

    f[1] = (s-1) * (s-1) % mod * inv(s) % mod;  // f1 = (s-1)^2 / s
    f[2] = (2 * f[1] % mod - 1 + mod) % mod;  // f2 = 2f1 - 1

    for (int i = 3; i <= maxm-5; i++) {
        f[i] = (2 * f[i-1] % mod - f[i-2] - (s-1) * inv(s-(i-1)) % mod + 2LL * mod) % mod;
        // f_k = 2f_{k-1} - f_{k-2} - (s-1)/(s-k+1)
    }

    ll ans = 0;
    for (int i = 1; i <= n; i++) ans += f[arr[i]], ans %= mod;

    cout << ans << endl;
}