luogu3600 随机数生成器

题目描述

sol研发了一个神奇的随机数系统,可以自动按照环境噪音生成真·随机数。

现在sol打算生成n个[1,x]的整数$a_1...a_n$,然后进行一些询问。

q次询问,每次询问i有两个参数li和ri,sol会计算$min_{li \leq j \leq ri} a_j$(a数组中下标在li、ri之间的数的最小值)。

最后测试结果会是这些询问得到的结果的最大值。 sol进行了很多次实验,现在他想问问你测试结果的期望大小是多少,对666623333取模。

输入格式

第一行三个数n、x、q。

下面q行,第i行两个数表示li和ri。

输出格式

一行一个数,表示答案。

样例输入

2 2 1
1 2

样例输出

499967501

说明

提示:一个分数$\frac{a}{b}$对666623333取模的结果为$a\times b^{666623331}~mod~666623333$。

对于10%的数据,$n,x,q \leq 6$。

对于另外20%的数据,$q=1$。

对于50%的数据,$n,x,q \leq 300$。

对于70%的数据,$n,x,q \leq 800$。

对于100%的数据,$1 \leq n,x,q \leq 2000$,对于每个i,$1 \leq l_i \leq r_i \leq n$。


分析

首先有一个非负整数的期望公式:对于一个随机整数变量 $x \geq 0$ ,它的期望 $E(x)=\sum_{整数s\geq 1} P(x \geq s)$ 。

因为根据定义$E(x)=\sum_{整数s\ge 0}s\cdot P(x=s)$,拆开可以发现两式等价。

那么我们可以枚举$s$,求询问答案最大值$\ge s$的概率,最后累加即为答案。

最大值$\ge s$等价于存在一个询问的答案$\ge s$,而存在性问题不好求,我们可以求它的补集,转化为任意性问题:每个询问的答案都$\le s-1$。

而询问的答案是区间的最小值,又可以转化成:每个询问区间中都存在$\le s-1$的数。

一个数$\le s-1$的概率为$p=\frac{s-1}{x}$,则问题转化成:有$n$个点和若干个询问区间,每个点有$p$的概率选,求选中的点覆盖所有询问区间(即每个询问区间中都有点选到)的概率。

这个问题可以利用dp解决。设$f(i)$表示【覆盖了所有右端点$\le i$的区间,且点$i$被选】的概率。设右端点$<i$的区间的最大左端点为$l$。枚举上一个选的点$j$,则:

$$f(i)=p\cdot \sum_{l\le j<i}f(j)\cdot (1-p)^{i-j-1}$$

$j\ge l$的原因是:若$j<l$,则左端点为$l$的那个区间覆盖不到。

根据定义,$l$是单调不减的,所以$\sum$里面那坨东西可以直接维护。单次dp复杂度$O(n)$,总复杂度$O(nx)$。

还有另一种dp思路:先把所有相互包含的区间较大的那个去掉(由题意显然),然后按左端点排序并编号,那么这些区间左右端点都不降。考虑每个点可以覆盖的区间,这些区间的编号肯定是连续的,也就是说编号是一段区间。

预处理求出每个点的编号区间,而我们想覆盖所有询问。所以问题转化成:有若干个区间要覆盖$[1,m]$的所有整点,每个区间选的概率为$p$,求覆盖的概率。这也可以用dp解决。

当然下面代码用的是第一种方法,代码较简单。不过第二种也是一种不错的思路。

代码

#include <bits/stdc++.h>
typedef long long ll;

const int N = 2050;
const int P = 666623333;

int n, m;
int lmx[N];
int f[N];

int qPow(int a, int k) {
    int rtn = 1;
    for (; k; k >>= 1, a = (ll)a * a % P)
        if (k & 1) rtn = (ll)rtn * a % P;
    return rtn;
}

int inv(int a) {
    return qPow(a, P-2);
}

int dp(int x) {
    int p = (ll)x * inv(m) % P, q = (1 - p + P) % P;
    int l = 0, sum = 1;
    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        f[i] = (ll)p * sum % P;
        for (; l < lmx[i]; l++)
            sum = (sum - (ll)f[l] * qPow(q, i-l-1) % P + P) % P;
        sum = ((ll)sum * q % P + f[i]) % P;
    }
    return (1 - sum + P) % P;
}

int main() {
    int q;
    scanf("%d%d%d", &n, &m, &q);
    for (int l, r; q--; ) {
        scanf("%d%d", &l, &r);
        lmx[r] = std::max(lmx[r], l);
    }

    int ans = 0;
    for (int i = 1; i <= m; i++)
        ans = (ans + dp(i-1)) % P;
    printf("%d\n", ans);
    return 0;
}


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论