Gym 102136 A

/*
{
######################
#       Author       #
#        Gary        #
#        2021        #
######################
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
//inline int read(){
//    int x=0;
//    char ch=getchar();
//    while(ch<‘0‘||ch>‘9‘){
//        ch=getchar();
//    }
//    while(ch>=‘0‘&&ch<=‘9‘){
//        x=(x<<1)+(x<<3)+(ch^48);
//        ch=getchar();
//    }
//    return x;
//}
const int INF=0x3f3f3f3f;
const LL inf=1e18+233;
#define i128 __int128 
typedef pair<int,int> mp;
/*}
*/
const int MOD=1e9+7;
int quick(int A,int B){
	if(B==0) return 1;
	int tmp=quick(A,B>>1);
	tmp=1ll*tmp*tmp%MOD;
	if(B&1){
		tmp=1ll*tmp*A%MOD;
	}
	return tmp;
}
LL c[1001][1001];
LL bombi(int A,int B){
	if(A<B) return 0;
	B=min(B,A-B);
	if(A<=1000){
		return c[A][B];
	}
	if(B<=8){
		i128 now=1;
		rb(i,1,B){
			now=now*(A-i+1);
			now=now/i;
			if(now>inf) return inf;
		}
		return (LL)(now);
	}
	return inf;
}
void solve(){
	LL n,k;
	scanf("%lld%lld",&n,&k);
	LL l,r;
	l=0,r=1500000000;
	while(l<r-1){
		LL mid=(l+r)>>1;
		if(mid*(mid+1)/2<n) l=mid;
		else r=mid;
	}
	n-=l*(l+1)/2;
	LL z=l+1;
	if(n>=z-1){
		LL rest;
		if(k>1) rest=-1;
		else{
			rest=quick(2,n);
			(rest+=MOD-1)%=MOD;
			rest=rest*quick(2,z-n)%MOD;
		}
		printf("%lld\n",rest);
	}
	else{
		LL have=z-1-n;
		LL sum=0;
		int c=0;
		while(sum<k){
			LL tmp=bombi(have,c);
			if(c>have){
				puts("-1");
				return ;
			}
			sum+=tmp;
			c++;
			if(sum<k);
			else {
				--c;
				sum-=tmp;
				break;
			}
		}
		k-=sum;
		LL rest;
		rest=quick(2,n);
		(rest+=MOD-1)%=MOD;
		rest=rest*quick(2,z-n)%MOD;
		rb(i,1,c){
			LL l=c-i,r=have+1;
			while(l<r-1){
				LL mid=(l+r)>>1;
				if(bombi(mid,c-i+1)<k) l=mid;
				else r=mid;
			}
			k-=bombi(l,c-i+1);
			int put=l+1;
			rest=(rest+quick(2,put-1))%MOD;
		}
		printf("%lld\n",rest);
	}
}
int main(){
	rb(i,0,1000) c[i][0]=1;
	rb(i,1,1000)
		rb(j,1,1000) c[i][j]=(c[i-1][j]+c[i-1][j-1]),check_min(c[i][j],inf);
	int T;
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}
/*
1
1000000000000000000
1000000000000000000
*/
```cpp

Gym 102136 A

原文：https://www.cnblogs.com/gary-2005/p/14404765.html