Codeforces Round 678 - C - Binary Search

题目

https://codeforces.com/contest/1436/problem/C

思路

考虑二分搜索的过程中$left$和$right$的变化情况，当$a[middle]\leq x$时，$left$会变化；否则$right$会变化。令$lt$，$gt$分别代表$a[middle]\lt x$、$a[middle]\gt x$的次数。由组合数学知识得：

$$C_{n-x}^{gt}A_{gt}^{gt}C_{x-1}^{lt}A_{lt}^{lt}A_{n-1-lt-gt}^{n-1-lt-gt}$$

其中$n-x$为大于$x$的个数，$x-1$为小于$x$的个数，注意对$10^9+7$取模。
由于组合数取模需要用到乘法逆元，附上oi-wiki关于乘法逆元的介绍：https://oi-wiki.org/math/inverse/

AC代码

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
struct _IO { _IO() { ios::sync_with_stdio(0); cin.tie(0); } }_io;
typedef long long ll; typedef long double db;

ll exgcd(ll a, ll b, ll &x, ll &y) { if (!b) { x = 1; y = 0; return a; }ll d = exgcd(b, a % b, x, y); ll t = x; x = y; y = t - (a / b) * y; return d; }
ll getInv(ll a, ll mod) { ll x, y; return exgcd(a, mod, x, y) == 1 ? (x % mod + mod) % mod : -1; }

const ll maxn = 2005, mod = 1e9 + 7;
ll fact[maxn];
void make_fact()
{
	fact[0] = 1;
	for (ll i = 1; i < 2005; ++i)
		fact[i] = (fact[i - 1] * i) % mod;
}

ll comb(ll n, ll r)
{
	return (fact[n] * getInv((fact[r] * fact[n - r]) % mod, mod)) % mod;
}

int main()
{
	make_fact();
	ll n, x, pos, gt = 0, lt = 0;
	cin >> n >> x >> pos;

	ll l = 0, r = n, mid;
	while (l < r)
	{
		mid = (l + r) >> 1;
		if (mid <= pos)
		{
			if (mid != pos) ++lt;
			l = mid + 1;
		}
		else ++gt, r = mid;
	}

	ll ans = 0;
	if (n - x < gt || x - 1 < lt);
	else ans = (((((((comb(n - x, gt) * fact[gt]) % mod) * comb(x - 1, lt)) % mod) * fact[lt]) % mod) * fact[n - lt - gt - 1]) % mod;
	cout << ans << endl;
	return 0;
}