luogu P3600 随机数生成器

https://www.luogu.com.cn/problem/P3600

每一步转换都不难，但许多步连在一起就不简单了

考虑怎么计算最大值为$x$的概率

这个也不好算，考虑算$\le x$的概率
也就是说对于每个区间，至少有一个数是$\le x$的概率

概率不好算，考虑算方案数

总的方案数显然是$m^n$,考虑$dp$
设$f[i][j]$表示已经填了前$i$,填了$j$个$\le x$的，钦定第$i$个是$\le x$的方案数

不难发现对于每个$x$,可以把$\le x$的数看成$0$,$>x$的数看成$1$,相当于是每个区间里至少有一个$0$

即转换后填了$j$个$0$合法的方案数为$s[j]$
显然$s[j]={\sum }_i[i之后全部填1都没关系]f[i][j]$

然后对于一个$x$,$\le x$方案数就是$g[i]={\sum }_{j}s[j]\times x^j\times (m?x{)}^{n?j}$

$p[i]=\frac{g[i]?g[i?1]}{m^n}$

再用期望的定义式计算即可

code:

#include<bits/stdc++.h>
#define N 2005
#define ll long long
#define mod 666623333
using namespace std;
ll qpow(ll x, ll y) {
    ll ret = 1;for(; y; y >>= 1, x = x * x % mod) if(y & 1) ret = ret * x % mod;return ret;
}
int n, m, q, R[N];
ll f[N][N], g[N], s[N];
int main() {
    scanf("%d%d%d", &n, &m, &q);for(int i = 1; i <= n + 1; i ++) R[i] = n + 1;for(int i = 1; i <= q; i ++) {
    int l, r;scanf("%d%d", &l, &r);R[l] = min(R[l], r);}for(int i = n - 1; i >= 1; i --) R[i] = min(R[i], R[i + 1]);f[0][0] = 1;for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= i; j ++) {
    for(int k = i - 1; k >= 0; k --) {
    f[i][j] = (f[i][j] + f[k][j - 1]) % mod;if(R[k] < i) break;}}}// for(int i = 1; i <= n; i ++) {
    // for(int j = 1; j <= n; j ++) printf(" %d ", f[i][j]); printf("\n");// }for(int i = 1; i <= n; i ++) for(int j = 0; j <= n; j ++) if(R[j + 1] == n + 1) s[i] = (s[i] + f[j][i]) % mod;// for(int i = 1; i <= n; i ++) printf("%lld ", R[i]); printf("\n"); // for(int i = 1; i <= n; i ++) printf("%lld ", s[i]); printf("\n");for(int i = 1; i <= m; i ++)for(int j = 1; j <= n; j ++) g[i] = (g[i] + qpow(i, j) * qpow(m - i, n - j) % mod * s[j] % mod) % mod;ll inv = qpow(qpow(m, n), mod - 2);for(int i = m; i >= 1; i --) g[i] = (g[i] - g[i - 1] + mod) % mod * inv % mod;ll ans = 0;for(int i = 1; i <= m; i ++) ans = (ans + g[i] * i % mod) % mod;printf("%lld", ans);return 0;
}