A7156 | Wet Shark and Flowers
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
Wet Shark 有 $n$ 只种花的鲨鱼，它们都围坐在一张桌子旁。对于所有 $1 \leq i \leq n-1$，鲨鱼 $i$ 和鲨鱼 $i+1$ 是邻居。鲨鱼 $n$ 与鲨鱼 $1$ 也是邻居。
每只鲨鱼会种若干朵花，设为 $s_i$。对于第 $i$ 只鲨鱼，$s_i$ 是从 $l_i$ 到 $r_i$（含）之间均匀随机选取的一个整数。Wet Shark 有一个最喜欢的质数 $p$，它对这个质数非常喜爱！对于任意一对相邻的鲨鱼 $i$ 和 $j$，如果 $s_i \cdot s_j$ 能被 $p$ 整除，Wet Shark 就会对这两只鲨鱼各奖 $1000$ 美元。
一天结束后，所有鲨鱼会把 Wet Shark 奖励它们的奖金加起来。请你求出这些奖金的期望值。
每只鲨鱼会种若干朵花，设为 $s_i$。对于第 $i$ 只鲨鱼，$s_i$ 是从 $l_i$ 到 $r_i$（含）之间均匀随机选取的一个整数。Wet Shark 有一个最喜欢的质数 $p$，它对这个质数非常喜爱！对于任意一对相邻的鲨鱼 $i$ 和 $j$，如果 $s_i \cdot s_j$ 能被 $p$ 整除，Wet Shark 就会对这两只鲨鱼各奖 $1000$ 美元。
一天结束后，所有鲨鱼会把 Wet Shark 奖励它们的奖金加起来。请你求出这些奖金的期望值。
输入格式
输入的第一行包含两个用空格隔开的整数 $n$ 和 $p$（$3 \leq n \leq 100000, 2 \leq p \leq 10^9$）——鲨鱼的数量和 Wet Shark 喜欢的质数。保证 $p$ 是一个质数。
接下来的 $n$ 行，第 $i$ 行包含两个用空格隔开的整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq 10^9$），表示第 $i$ 只鲨鱼能种植的花的范围。注意，$s_i$ 在 $[l_i, r_i]$ 区间内等概率取整数值。
接下来的 $n$ 行，第 $i$ 行包含两个用空格隔开的整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq 10^9$），表示第 $i$ 只鲨鱼能种植的花的范围。注意，$s_i$ 在 $[l_i, r_i]$ 区间内等概率取整数值。
输出格式
输出一个实数，表示所有鲨鱼最终获得奖金的期望总和，结果保留 $6$ 位小数。
输入输出样例
输入 #1
3 2 1 2 420 421 420420 420421
输出 #1
4500.000000
输入 #2
3 5 1 4 2 3 11 14
输出 #2
0.000000
### 样例解释
质数是指仅能被 $1$ 和它自身整除的正整数。$1$ 不被视为质数。
考虑第一个样例。第一只鲨鱼能种植 $1$ 至 $2$ 朵花，第二只鲨鱼能种植 $420$ 至 $421$ 朵花，第三只鲨鱼能种植 $420420$ 至 $420421$ 朵花。三只鲨鱼能种植的花的数量共有 $8$ 种组合 $(s_0, s_1, s_2)$：
1. $(1,420,420420)$：注意 $s_0 \cdot s_1 = 420$，$s_1 \cdot s_2 = 176576400$，$s_2 \cdot s_0 = 420420$。每对相邻鲨鱼都能获得 $1000$ 美元，因此每只鲨鱼获得 $2000$ 美元，总奖金 $6000$。
2. $(1,420,420421)$：此时 $s_2 \cdot s_0$ 不能被 $2$ 整除，只有 $s_0, s_1$ 和 $s_1, s_2$ 这两对邻居各得 $1000$ 美元，即总奖金 $4000$。
3. $(1,421,420420)$：总奖金 $4000$。
4. $(1,421,420421)$：总奖金 $0$。
5. $(2,420,420420)$：总奖金 $6000$。
6. $(2,420,420421)$：总奖金 $6000$。
7. $(2,421,420420)$：总奖金 $6000$。
8. $(2,421,420421)$：总奖金 $4000$。
期望奖金为 $\frac{1}{8} (6000+4000+4000+0+6000+6000+6000+4000) = 4500$。
第二个样例中，任何花的组合都不能获得奖金。
质数是指仅能被 $1$ 和它自身整除的正整数。$1$ 不被视为质数。
考虑第一个样例。第一只鲨鱼能种植 $1$ 至 $2$ 朵花，第二只鲨鱼能种植 $420$ 至 $421$ 朵花，第三只鲨鱼能种植 $420420$ 至 $420421$ 朵花。三只鲨鱼能种植的花的数量共有 $8$ 种组合 $(s_0, s_1, s_2)$：
1. $(1,420,420420)$：注意 $s_0 \cdot s_1 = 420$，$s_1 \cdot s_2 = 176576400$，$s_2 \cdot s_0 = 420420$。每对相邻鲨鱼都能获得 $1000$ 美元，因此每只鲨鱼获得 $2000$ 美元，总奖金 $6000$。
2. $(1,420,420421)$：此时 $s_2 \cdot s_0$ 不能被 $2$ 整除，只有 $s_0, s_1$ 和 $s_1, s_2$ 这两对邻居各得 $1000$ 美元，即总奖金 $4000$。
3. $(1,421,420420)$：总奖金 $4000$。
4. $(1,421,420421)$：总奖金 $0$。
5. $(2,420,420420)$：总奖金 $6000$。
6. $(2,420,420421)$：总奖金 $6000$。
7. $(2,421,420420)$：总奖金 $6000$。
8. $(2,421,420421)$：总奖金 $4000$。
期望奖金为 $\frac{1}{8} (6000+4000+4000+0+6000+6000+6000+4000) = 4500$。
第二个样例中，任何花的组合都不能获得奖金。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？