【Codeforces 1436 C】Binary Search，二分，构造排列，统计

problem

C. Binary Search
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Andrey thinks he is truly a successful developer, but in reality he didn’t know about the binary search algorithm until recently. After reading some literature Andrey understood that this algorithm allows to quickly find a certain number x in an array. For an array a indexed from zero, and an integer x the pseudocode of the algorithm is as follows:

Note that the elements of the array are indexed from zero, and the division is done in integers (rounding down).

Andrey read that the algorithm only works if the array is sorted. However, he found this statement untrue, because there certainly exist unsorted arrays for which the algorithm find x!

Andrey wants to write a letter to the book authors, but before doing that he must consider the permutations of size n such that the algorithm finds x in them. A permutation of size n is an array consisting of n distinct integers between 1 and n in arbitrary order.

Help Andrey and find the number of permutations of size n which contain x at position pos and for which the given implementation of the binary search algorithm finds x (returns true). As the result may be extremely large, print the remainder of its division by 109+7.

Input
The only line of input contains integers n, x and pos (1≤x≤n≤1000, 0≤pos≤n−1) — the required length of the permutation, the number to search, and the required position of that number, respectively.

Output
Print a single number — the remainder of the division of the number of valid permutations by 109+7.

Examples
inputCopy
4 1 2
outputCopy
6
inputCopy
123 42 24
outputCopy
824071958
Note
All possible permutations in the first test case: (2,3,1,4), (2,4,1,3), (3,2,1,4), (3,4,1,2), (4,2,1,3), (4,3,1,2).

solution

/*
题意：
+ 构造一个1~n的排列，其中x在pos位置，使得题给的二分查找程序能正确找到x。
+ 求有多少个这样的排列
思路：
+ 首先知道x在pos，所以二分的过程中，需要找几次，会经过哪些点就已经知道了（虽然排列不是单调的，但这个排列的下标是单调的）。
+ 直接对下标pos二分查找，在这个过程中记录比pos大的下标的个数以及比pos小的下标的个数，这实际上也就是在最终要构造出来的序列中二分转折点上比x大的数的个数以及比x小的数的个数。个数确定后就是排列组合问题了，对于这两部分先选再排，剩下的数求全排列，把这些乘起来即可。
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
LL inv(LL x){return x==1?1:(LL)(mod-mod/x)*inv(mod%x)%mod;}
LL C(LL n, LL m){
	if(n<0 || n<m)return 0;
	if(m>n-m)m=n-m;
	LL up = 1, down = 1;
	for(LL i = 0; i < m; i++){
		up = up*(n-i)%mod;
		down = down*(i+1)%mod;
	}
	return up*inv(down)%mod;
}
LL A(LL n, LL m){
	LL ans = 1;
	for(LL i = n; i >= n-m+1; i--)
		ans = ans*i%mod;
	return ans;
}
int main(){
	int n, x, pos;
	cin>>n>>x>>pos;
	int l = 0, r = n;
	LL small = 0, big = 0;
	while(l < r){
		int mid = l+r>>1;
		if(mid > pos){r = mid; big++;}
		else if(mid<pos){l=mid+1; small++;}
		else l = mid+1;
	}
	cout<<C(n-x,big)*A(big,big)%mod*C(x-1,small)%mod*A(small,small)%mod*A(1ll*n-big-small-1,1ll*n-big-small-1)%mod<<"\n";
	return 0;
}


  

 

  
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
  
44
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/113816358