Token generation
题解
由于某些原因就采用英文名了
看到这道题，我们很快就发现使得
F
(
Q
)
F(Q)
F(Q)增加的值，存在这样的构造
1...10...0
1...10...0
1...10...0，即开头是一段连续的
1
1
1，之后全是
0
0
0。
基于此，我们可以通过二分的方法找到对于当前的
N
N
N，它的的总位数与后面
0
0
0的数量。
之后，我们思考如何找到第
k
k
k个满足
F
(
Q
)
=
N
F(Q)=N
F(Q)=N的
Q
Q
Q。
由于它的第一关键字是
1
1
1的个数，我们可以通过组合数的枚举来计算出它包含的
1
1
1的个数。
因为
k
≤
1
0
18
k\leq 10^{18}
k≤1018，这里枚举的次数不会太多，大概是
l
o
g
k
log\,k
logk的级别，实际上还要小些。
当知道
1
1
1的个数后，我们只需要一位一位往下去枚举哪些位置需要取
1
1
1，判断也可以用组合数来执行。
由于可能枚举的位置有点多，也需要通过二分来进行。
当有了上面的思路，我们就可以去做了。
但我们发现，如果我们直接去预处理组合数大小时，会
T
T
T得只有
30
30
30pts，即使通过阶乘去求，也需要一个很大的模数，还是只有
50
p
t
s
50pts
50pts。
由于后面
n
,
k
n,k
n,k都已经达到了
1
0
18
10^{18}
1018的级别，而组合数的递增又是极其快的，我们可以知道
1
1
1的个数一定是非常少的。
于是，我们可以对于较小的组合数预处理出来，较大的现场计算。
但因为要与
k
k
k进行比较，我们还得保证最后得到的组合数是真实值。我们需要一个大于
1
0
18
10^{18}
1018的质数模数，并且对于大于
1
0
18
10^{18}
1018的结果及时处理。
我们可以处理出对于每个数量的
1
1
1，当对于多少个位置的组合时会超过
1
0
18
10^{18}
1018次方，当超过这个值时，就直接返回
1
0
18
+
1
10^{18}+1
1018+1。
我们只需要处理出到
6
6
6的时候就可以了，因为此时就已经达到了
3000
3000
3000，下面的我们可以预处理。
由于模数太大，我们乘法的时候都只能采用龟速乘，你会发现你因此达到了3个
l
o
g
log
log，会被最后一个点卡掉。
这时，我们就只能采用**__int128**了，轻松过题。
源码
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN 100005
#define lowbit(x) (x&-x)
#define reg register
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int INF=0x7f7f7f7f;
const LL mo=998244353LL;
const LL mod=4000000000000000037LL;
const LL inv2=2000000000000000019LL;
const LL dd=1000000000000000001LL;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){
_T f=1;x=0;char s=getchar();
while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
x*=f;
}
int t;LL n,k,fac[MAXN],inv[MAXN],C[3005][3005];
LL gr[10]={0,dd,1414213563LL,1817122LL,69995LL,10371LL,3000LL,1265LL,675LL};
LL add(const LL x,const LL y){return x+y<mod?x+y:x+y-mod;}
LL qkpow(LL a,LL s){LL t=1LL;while(s){if(s&1LL)t=1ll*a*t%mo;a=1ll*a*a%mo;s>>=1LL;}return t;}
LL qkmul(LL a,LL s){__int128 t=(__int128)a*(__int128)s%mod;return (LL)t;}
LL qpow(LL a,LL s){LL t=1LL;while(s){if(s&1LL)t=qkmul(a,t);a=qkmul(a,a);s>>=1LL;}return t;}
void init(){
for(reg int i=0;i<=3000;++i)C[i][0]=C[i][i]=1;
for(reg int i=1;i<=3000;++i)
for(reg int j=1;j<i;++j)
if(C[i-1][j-1]+C[i-1][j]<dd)
C[i][j]=C[i-1][j-1]+C[i-1][j];
else C[i][j]=dd;
inv[0]=fac[0]=1;
for(reg int i=1;i<=10;++i)fac[i]=qkmul(1ll*i,fac[i-1]);
inv[10]=qpow(fac[10],mod-2LL);
for(reg int i=9;i>0;--i)inv[i]=qkmul(1ll*(i+1),inv[i+1]);
}
inline LL Cd(const LL x,const LL y){
if(x<y)return 0;if(y==x||y==0)return 1LL;if(y==1||y==x-1)return x;
if(x<=3000&&y<=3000)return C[x][y];if(x>gr[y])return dd;
LL ans=1LL;for(reg LL i=x;i>x-y;--i)ans=qkmul(ans,i);ans=qkmul(ans,inv[y]);
return ans;
}
signed main(){
read(t);init();
while(t--){
read(n);read(k);LL l=0,r=2e9;
while(l<r){LL mid=l+r>>1LL;if(mid*(mid+1LL)/2LL>=n)r=mid;else l=mid+1;}
const LL x=l,y=l-n+l*(l-1LL)/2LL;
if(y-1LL<60&&(1LL<<y-1LL)<k)puts("-1");
else{
LL num=0,ans=(qkpow(2LL,x)-qkpow(2LL,y)+mo)%mo,tmp;
while((tmp=Cd(y-1LL,num))<k)k-=tmp,num++;LL las=y-1LL;
while(num){
l=num-1LL,r=las-1LL;if(r>gr[min(8LL,num)])r=gr[min(8LL,num)];
while(l<r){LL mid=(l+r+1LL)>>1LL;if(Cd(mid,num)<k)l=mid;else r=mid-1LL;}
k-=Cd(l,num);num--;ans=(ans+qkpow(2LL,l))%mo;las=l;
}
printf("%lld\n",ans);
}
}
return 0;
}