当前位置: 代码迷 >> 综合 >> 51nod 1799 二分答案
  详细解决方案

51nod 1799 二分答案

热度:52   发布时间:2024-01-19 01:49:24.0

lyk最近在研究二分答案类的问题。
对于一个有n个互不相同的数且从小到大的正整数数列a(其中最大值不超过n),若要找一个在a中出现过的数字m,一个正确的二分程序是这样子的:
1
2
3
4
5
6
l = 1 ;  r = n ;  mid = ( l + r )/ 2 ;
while  ( l <= r )
{
if  ( a [ mid ] <= m )  l = mid +1 ;  else  r = mid -1 ;
mid = ( l + r )/ 2 ;
}

最终a[r]一定等于m。
但是这个和谐的程序被熊孩子打乱了。
熊孩子在一开始就将a数组打乱顺序。(共有n!种可能)
lyk想知道最终r=k的期望。
由于小数点非常麻烦,所以你只需输出将答案乘以n!后对1000000007取模就可以了。

在样例中,共有2个数,被熊孩子打乱后的数列共有两种可能(1,2)或者(2,1),其中(1,2)经过上述操作后r=1,(2,1)经过上述操作后r=0。r=k的期望为0.5,0.5*2!=1,所以输出1。
Input
3个整数n,m,k(1<=m<=n<=10^9,0<=k<=n)。
Output
一行表示答案
Input示例
2 1 1
Output示例
1
~~~~~~~~~~~~~~~~~~~~~~~~~~~

打表+思路~

显然只有二分到k的路径上的点的与m的大小关系会对二分的答案产生影响,约为logn个。所以我们二分一下,计算出确定与m的大小关系的数中<=m和>m的数的个数,然后用阶乘求出这些数的排列方式即可。

但是n<=1e9,显然我们不能直接阶乘,所以可以分段打表,分别打出1e7,2*1e7,...,1e9的表,再在此基础上计算即可~

全要取模!!!


(花了10块买了第四个数据点,好心疼啊QAQ,放在这里,仅供参考:输入:52 15 17 输出:996033146)

(另外,代码里面的表看不到了,在这里写一下:

682498929,491101308,76479948,723816384,67347853,27368307,625544428,199888908,888050723,927880474,281863274,661224977,623534362,970055531,261384175,195888993,66404266,547665832,109838563,933245637,724691727,368925948,268838846,136026497,112390913,135498044,217544623,419363534,500780548,668123525,128487469,30977140,522049725,309058615,386027524,189239124,148528617,940567523,917084264,429277690,996164327,358655417,568392357,780072518,462639908,275105629,909210595,99199382,703397904,733333339,97830135,608823837,256141983,141827977,696628828,637939935,811575797,848924691,131772368,724464507,272814771,326159309,456152084,903466878,92255682,769795511,373745190,606241871,825871994,957939114,435887178,852304035,663307737,375297772,217598709,624148346,671734977,624500515,748510389,203191898,423951674,629786193,672850561,814362881,823845496,116667533,256473217,627655552,245795606,586445753,172114298,193781724,778983779,83868974,315103615,965785236,492741665,377329025,847549272,698611116)


#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define ll long longconst int mod=1e9+7;
const int N=1e7;
const int num[]={1,682498929,491101308,76479948,723816384,67347853,27368307,625544428,199888908,888050723,927880474,281863274,661224977,623534362,970055531,261384175,195888993,66404266,547665832,109838563,933245637,724691727,368925948,268838846,136026497,112390913,135498044,217544623,419363534,500780548,668123525,128487469,30977140,522049725,309058615,386027524,189239124,148528617,940567523,917084264,429277690,996164327,358655417,568392357,780072518,462639908,275105629,909210595,99199382,703397904,733333339,97830135,608823837,256141983,141827977,696628828,637939935,811575797,848924691,131772368,724464507,272814771,326159309,456152084,903466878,92255682,769795511,373745190,606241871,825871994,957939114,435887178,852304035,663307737,375297772,217598709,624148346,671734977,624500515,748510389,203191898,423951674,629786193,672850561,814362881,823845496,116667533,256473217,627655552,245795606,586445753,172114298,193781724,778983779,83868974,315103615,965785236,492741665,377329025,847549272,698611116};int n,m,k,l,r,mid,ltot,rtot,ans;int cal(int n)
{if(!n) return 1;int now=num[n/N];for(int i=n/N*N+1;i<=n;i++) now=(ll)now*i%mod;return now;
}int main()
{scanf("%d%d%d",&n,&m,&k);l=1;r=n;ans=1;while(l<=r){mid=l+r>>1;if(mid<=k) l=mid+1,ltot++;else r=mid-1,rtot++;}for(int i=m-ltot+1;i<=m;i++) ans=(ll)ans*i%mod;for(int i=n-m-rtot+1;i<=n-m;i++) ans=(ll)ans*i%mod;ans=(ll)ans*cal(n-ltot-rtot)%mod;printf("%d\n",ans);return 0;
}