【CF1436C】Binary Search 題解
- 2020 年 10 月 25 日
- 筆記
- Codeforces, 題解
題意簡介
要求有多少種 n 的排列，能夠通過二分法正確地找到放在 pos 處的數字 x。
答案對 1e9+7 取模。n<=1000。
採用的二分法如下圖：
思路分析
首先，這個排列中有一個位置是固定的，就是 a[pos] = x 。
我們知道，二分查找的過程是不斷縮小區間的過程，想要找到一個已經確定放在 pos 位置上的 x ，需要判斷的 mid 的位置，需要的大於 x 的數的個數 c1 和小於 x 的數的個數 c0 也是固定的。
也就是說，我們只需要模擬這個二分過程，求解出 c0 和 c1，然後利用排列組合的公式去計算就行了。
\(Ans = A^{c0}_{x-1} \times A^{c1}_{n-x} \times (n-1-c0-c1)!\)
由於本題的 n 的範圍較小，可以不寫逆元，直接暴力求階乘。
順帶一提，本題有一個坑點在於不一定有解。顯然的，當小於 x 的數不夠 c0 個或大於 x 的數不夠 c1 個時無解。
代碼庫
#include <cstdio>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define Rep(i,a,b) for(int i=a;i>=b;i--)
typedef long long ll;
const int MOD=1e9+7,N=1002;
inline ll _pow(ll x,ll p){
ll ans=1;
while(p){
if(p&1) ans=ans*x%MOD;
p>>=1; x=x*x%MOD;
}
return ans;
}
int n,x,pos,c0,c1;
ll fact[N];
int main(){
scanf("%d%d%d",&n,&x,&pos);
int l=0,r=n,mid;
while(l<r){
mid=(l+r)>>1;
if(mid<pos) c0++,l=mid+1;
else if(mid==pos) l=mid+1;
else c1++,r=mid;
}
fact[0]=1;
rep(i,1,n) fact[i]=(fact[i-1]*i)%MOD;
if(x-1-c0<0||n-x-c1<0||n-1-c0-c1<0) printf("0\n");
else printf("%lld\n",fact[x-1]*_pow(fact[x-1-c0],MOD-2)%MOD*fact[n-x]%MOD*_pow(fact[n-x-c1],MOD-2)%MOD*fact[n-1-c0-c1]%MOD);
return 0;
}
