P3600 随机数生成器
所有询问的最大值，考虑 Min-Max 反演，那么求所有询问集合的最小值，对于每个集合，即求这些区间并的最小值，对于所有赋值情况的期望。注意到这只与区间并的长度有关，考虑 DP $f _ {i, j}$ 表示当前考虑区间 $[l _ i, r _ i]$ ，区间并的长度为 $j$ 的方案数。考虑和当前区间是否有交的两种情况，那么有：
$$
f _ {i, j} = \sum _ {k = 1} ^ {l _ i - 1} f _ {k, j - (r _ i - l _ i + 1)} + \sum _ {k = l _ i} ^ {r _ i - 1} f _ {k, j - (r _ i - k) }
$$
这样可以在 $O(n ^ 2 m)$ 的时间内得到答案，考虑前缀和优化。考虑计算完 $f _ {i, j}$ 对于前面的式子，可以直接前缀和优化，向 $j$ 贡献。对于后面的式子，注意到 $i - j$ 为定值，向 $i - j$ 贡献。
对于每个区间并的长度 $n$ ，考虑每一个数成为最小值的方案数，对于一个数 $i$ ，如果在 $[i, m]$ 中任意选择，方案数为 $(m -i + 1) ^ n$ ，注意到可能会没有选择到 $i$ ，这些方案数为 $[i + 1, m]$ 的任意选择的方案数，即 $(m - i) ^ n$ ，那么方案数为 $(m - i + 1) ^ n - (m - i) ^ n$ ，对于所有的最小值的答案和为
$$
\begin {aligned}
& \sum _ {i = 1} ^ m i ((m - i + 1) ^ n - (m - i) ^ n) \\
= & (m ^ n - (m -1) ^ n) + 2((m - 1) ^ n - (m - 2) ^ n ) \cdots + m(1 ^ n - 0 ^ n) \\
= & \sum _ {i = 1} ^ m i ^ n
\end {aligned}
$$
就是自然数幂和，有无数种方法可以快速算并且复杂度可以与 $m$ 无关。
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
| #include <cstdio>
#include <vector>
#include <algorithm>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
template <class Type>
void read (Type &x)
{
char c;
bool flag = false;
while ((c = getchar()) < '0' || c > '9')
flag |= c == '-';
x = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
x = (x << 3) + (x << 1) + c - '0';
if (flag) x = ~x + 1;
}
template <class Type, class ...Rest>
void read (Type &x, Rest &...y) { read(x); read(y...); }
template <class Type>
void write (Type x)
{
if (x < 0) putchar('-'), x = ~x + 1;
if (x > 9) write(x / 10);
putchar('0' + x % 10);
}
typedef long long LL;
typedef pair <int, int> PII;
const int N = 2e3 + 10, mod = 666623333;
int n, m, q, f[N][N], g[N][N], h[N][N];
vector <PII> w;
int binpow (int b, int k = mod - 2)
{
int res = 1;
for (; k; k >>= 1, b = (LL)b * b % mod)
if (k & 1) res = (LL)res * b % mod;
return res;
}
int main ()
{
read(n, m, q);
for (int l, r; q; --q)
{
read(l, r);
for (auto i = w.begin(); i != w.end(); )
i = i->fi <= l && i->se >= r ? w.erase(i) : ++i;
bool flag = true;
for (PII i : w) if (l <= i.fi && r >= i.se)
{ flag = false; break; }
if (flag) w.pb(mp(l, r));
}
q = w.size();
sort(w.begin(), w.end(), [&](PII a, PII b){ return a.se == b.se ? a. fi < b.fi : a.se < b.se; });
f[0][0] = g[0][0] = h[0][0] = -1;
for (int r = 1, t = 0; r <= n; ++r)
{
for (; t < q && w[t].se <= r; ++t)
{
int l = w[t].fi;
for (int k = r - l + 1; k <= r; ++k)
f[r][k] = -(g[l - 1][k - (r - l + 1)] + ((LL)h[r - 1][r - k] - h[l - 1][r - k])) % mod;
}
for (int k = 0; k <= r; ++k)
{
g[r][k] = (g[r - 1][k] + f[r][k]) % mod;
h[r][r - k] = (h[r - 1][r - k] + f[r][k]) % mod;
}
}
int res = 0;
for (int i = 1; i <= n; ++i)
{
int tot = 0;
for (int j = 1; j <= n; ++j)
(tot += f[j][i]) %= mod;
tot = (LL)tot * binpow(binpow(m, i)) % mod;
for (int j = 1; j <= m; ++j)
(res += (LL)binpow(j, i) * tot % mod) %= mod;
}
write((res + mod) % mod);
return 0;
}
|