小象涂色 (elephant)

题目描述

小象喜欢为箱子涂色. 小象现在有 c 种颜色, 编号为 0c-1; 还有 n 个箱子, 编号为 1n, 最开始每个箱子的颜色为 1. 小象涂色时喜欢遵循灵感: 它将箱子按编号排成一排, 每次涂色时, 它随机选择 [L, R] 这个区间里的一些箱子 (不选看做选 0 个), 为之涂上随机一种颜色. 若一个颜色为 a 的箱子被涂上 b 色, 那么这个箱子的颜色会变成 (a*b) mod c. 请问在 k 次涂色后, 所有箱子颜色的编号和期望为多少?

输入描述

第一行为 T, 表示有 T 组测试数据.

对于每组数据, 第一行为三个整数 n, c, k.

接下来 k 行, 每行两个整数 Li, Ri, 表示第 i 个操作的 L 和 R.

输出描述

对于每组测试数据, 输出所有箱子颜色编号和的期望值, 结果保留 9 位小数.

样例输入

3
3 2 2
2 2
1 3
1 3 1
1 1
5 2 2
3 4
2 4

样例输出

2.062500000
1.000000000
3.875000000

数据范围

40% 的数据 \(1 \leq T \leq 5, 1 \leq n, k \leq 15, 2 \leq c \leq 20\)

100% 的数据满足 \(1 \leq T \leq 10, 1 \leq n, k \leq 50, 2 \leq c \leq 100, 1 \leq L_i \leq R_i \leq n\)

Explanation

懒得写题解了, 直接粘官方题解:

一道有关期望的 dp. 首先可知每个操作中, 一个物品会被染色的概率为\(\frac{1}{2}\), 用某 种颜色染色的概率为\(\frac{1}{c}\).

40 分的方程是用 \(f[i][j][k]\) 表示第 \(i\) 个物品在 \(j\) 次操作次数后颜色变为 \(k\) 的概率, 时间复杂度大概是 \(O(T \cdot N \cdot K \cdot c^2)\).

60 分要考虑到所有物品具有相似性, 即 \(n\) 个物品本质是相同的, 所以不用枚举物品 \(f[i][j]\) 表示一个物品操作 \(i\) 次颜色变为 \(j\) 的概率. 满足:

\[f[i + 1][j] += f[i][j] \cdot \frac{1}{2}\]

\[f[i + 1][(j \cdot b)\ mod\ c] += f[i][j] \cdot \frac{1}{2} \cdot \frac{1}{c}\]

初始值 \(f[0][1] = 1\), 答案就是:

\[\sum_{0 \leq j \lt c} f[i][j] \cdot j\]

\(i\) 表示该箱子的操作次数.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;
typedef long long lli;
typedef long double llf;
const int maxn = 60, maxc = 150;

int T, n, c, K;
llf dp[maxn][maxc];
int cnt[maxn];

int main(int argc, char** argv)
{
    scanf("%d", &T);
    for (int idx = 1; idx <= T; idx++) {
        memset(dp, 0, sizeof(dp));
        memset(cnt, 0, sizeof(cnt));
        scanf("%d%d%d", &n, &c, &K);
        // Different colours are similar.
        // Never mind the initial colours.
        dp[0][1] = 1.0;
        for (int i = 1; i <= K; i++)
            // Iterate through all initial colours
            for (int j = 0; j < c; j++) {
                // Not choosing a colour
                dp[i][j] += dp[i - 1][j] / 2.0;
                // Choose to paint colour #j with colour #k
                for (int k = 0; k < c; k++)
                    dp[i][(j * k) % c] += dp[i - 1][j] / (2.0 * (llf)c);
            }
        // Statistic on how many times it could hold
        for (int i = 1; i <= K; i++) {
            int l = 0, r = 0;
            scanf("%d%d", &l, &r);
            for (int j = l; j <= r; j++)
                cnt[j]++;
        }
        // Getting result
        llf res = 0.0;
        for (int i = 1; i <= n; i++)
            for (int j = 0; j < c; j++)
                res += dp[cnt[i]][j] * j;
        // res /= c;
        // Output result
        printf("%.9Lf\n", res);
    }
    return 0;
}