0%

[CF1436C] Binary Search

题目

题目链接

题目大意:给出 $x, n, p$,求有多少种长度为 $n$ 的排列满足第 $p$ 个数为 $x$ 且能让二分查找正确运行,结果对 $10^9 + 7$ 取模。下标从 $0$ 开始。$1 \le x \le n \le 1000, 0 \le p \le n - 1$。

思路

由于二分每次会按照当前中间值与要寻找的数的大小关系来进行下一步的查找,所以我们只需要考虑每次中间值的取值就行了。

如果 $p$ 在二分中点的右边,就说明这个中点的值能取任何小于 $x$ 的值,反之亦然。

注意到上述过程每操作一次就会消耗一个可能用的数的值,要处理一下。

还需要特判一下中点正好为 $p$ 的情况,这时候中点只能取 $x$。

用简单的排列组合就能求出答案。

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}

typedef long long LL;

const LL mod = 1e9 + 7;

LL x, n, pos, ans = 1, a = 1, b;

int main() {
read(n), read(x), read(pos);
LL l = 0, r = n;
while (l < r) {
LL mid = (l + r) / 2;
if (pos >= mid) {
l = mid + 1;
if (mid != pos) {
ans = ((ans % mod) * ((x - a) % mod)) % mod;
++a;
}
} else {
r = mid;
ans = ((ans % mod) * ((n - x - b) % mod)) % mod;
++b;
}
}
for (LL i = 1; i <= n - a - b; ++i) ans = ((ans % mod) * (i % mod)) % mod;
printf("%lld\n", ans);
return 0;
}