P3600 随机数生成器
题目描述
sol 研发了一个神奇的随机数系统,可以自动按照环境噪音生成真·随机数。
现在 sol 打算生成 $n$ 个 $[1,x]$ 的整数 $a_1, ..., a_n$,然后进行一些询问。
$q$ 次询问,每次询问 $i$ 有两个参数 $l_i$ 和 $r_i$,sol 会计算 $\min_{l_i \leq j \leq r_i} a_j$($a$ 数组中下标在 $l_i, r_i$ 之间的数的最小值)。
最后测试结果会是这些询问得到的结果的最大值。
sol 进行了很多次实验,现在他想问问你测试结果的期望大小是多少,对 $666623333$ 取模。
输入格式
无
输出格式
无
说明/提示
提示:一个分数 $\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$。