2020-2021:teams:farmer_john:2sozx:codeforces_round_654_div._2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:farmer_john:2sozx:codeforces_round_654_div._2 [2020/07/02 21:38] 2sozx [E2] |
2020-2021:teams:farmer_john:2sozx:codeforces_round_654_div._2 [2020/07/02 21:39] (当前版本) 2sozx |
||
|---|---|---|---|
| 行 14: | 行 14: | ||
| * 题意：数据范围改成 $2 \le p \le n \le 10^5,a_i \le 10^9$ | * 题意：数据范围改成 $2 \le p \le n \le 10^5,a_i \le 10^9$ | ||
| * 题解：显而易见的是 $x \ge \max\{a_i\}$ 时方案数 $mod p$ 一定为零，而且由于每个位置 $x$ 至多加一，因此 $x \ge \max\{a_i\} - n + 1$,并且我们可以二分出可以使得结果为 $x + n$ 的最小 $x$ 值。由上一题知 $x \ge a_p$ 时一定不会被记入答案。再由上一题知当 $x < a_i$ 并且 $i - a_i + x = p$ 时不会被计入答案，因此改变一下第二个式子的顺序，即 $x = p - i + a_i$ 并且满足第一个条件时的 $x$ 不会被记入答案，因此扫一遍 $x$ 即可。效率为排序和二分的效率。 | * 题解：显而易见的是 $x \ge \max\{a_i\}$ 时方案数 $mod p$ 一定为零，而且由于每个位置 $x$ 至多加一，因此 $x \ge \max\{a_i\} - n + 1$,并且我们可以二分出可以使得结果为 $x + n$ 的最小 $x$ 值。由上一题知 $x \ge a_p$ 时一定不会被记入答案。再由上一题知当 $x < a_i$ 并且 $i - a_i + x = p$ 时不会被计入答案，因此改变一下第二个式子的顺序，即 $x = p - i + a_i$ 并且满足第一个条件时的 $x$ 不会被记入答案，因此扫一遍 $x$ 即可。效率为排序和二分的效率。 | ||
| + | =====F===== | ||
2020-2021/teams/farmer_john/2sozx/codeforces_round_654_div._2.1593697120.txt.gz · 最后更改: 2020/07/02 21:38 由 2sozx
