差点就场切了。
按 \(f\) 的值分类。令 \(n'=n\)，对于 \(i=1,2,\dots\)，\(cnt_i=\lfloor\frac{n'+1}{2}\rfloor\)，\(n'\leftarrow \lfloor\frac{n'}{2}\rfloor\)。
注意到数值相同的可以随意交换，这就是说在无标号情况下的一种本质不同方案对应有标号情况下的 \(\prod cnt_i!\) 种方案。
由于 \(k\le 10^{18}\)，可以得到 \(n\ge 30\) 时只需考虑最优解。模拟最优解过程即可。
此时把情况转化为无标号情况，即令 \(\displaystyle k\leftarrow \lfloor\frac{k-1}{\prod cnt_i}\rfloor+1\)。
当 \(n=29\) 时 \(cnt\) 数组上界为 \(\{15,7,4,2,1\}\)，设 \(f_{a,b,c,d,e,v}\) 表示现在放置了 \(a\) 个 \(1\)，\(b\) 个 \(2\)，以此类推，总和为 \(v\) 的方案数，可以 \(O(1)\) 转移。
然后就做完了。\(V\) 要开到 \(10^4\) 左右。
只开了 \(5400\)。难受。
#include<bits/stdc++.h>
#define ll long long
#define N 64
#define P 998244353
using namespace std;
ll read(){
ll x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
//计算 f 数组。每次 cnt_i <- (n+1)/2,n <- n/2。
//注意到 20! > 10^{18}，当 n>=30 时直接输出最优解。
//除此之外答案的上界是 O(n^3) 的。
ll cnt[N];int tot;
ll n,k,fac[20];
ll s1(ll x){
ll r1=x,r2=x+1;
(r1%2==0)?(r1/=2):(r2/=2);
r1%=P,r2%=P;
return r1*r2%P;
}
ll s2(ll x){
ll r1=x,r2=x+1,r3=2*x+1;
(r1%2==0)?(r1/=2):(r2/=2);
(r1%3==0)?(r1/=3):(r2%3==0?r2/=3:r3/=3);
r1%=P,r2%=P,r3%=P;
return r1*r2%P*r3%P;
}
ll calc(ll n,ll l,ll r){
n=(n+1)%P;
return ((s1(r)-s1(l-1)+P)%P*n-s2(r)+s2(l-1)+P)%P;
}
void solvecase(ll n){
ll L=0,R=0,ans=0;
for(int i=tot;i;i--){
ll cur=0;
if(cnt[i]%2==0){
cur=(calc(n,L+1,L+cnt[i]/2)+calc(n,R+1,R+cnt[i]/2))%P;
L+=cnt[i]/2,R+=cnt[i]/2;
}
else{
if(L>R){
cur=(calc(n,L+1,L+cnt[i]/2)+calc(n,R+1,R+cnt[i]/2+1))%P;
L+=cnt[i]/2,R=L;
}
else{
cur=(calc(n,L+1,L+cnt[i]/2+1)+calc(n,R+1,R+cnt[i]/2))%P;
R+=cnt[i]/2,L=R+1;
}
}
ans=(ans+1ll*i*cur)%P;
}
printf("%lld\n",ans);
}
int getval(int x){
return x*(n-x+1);
}
ll f[16][8][5][3][2][10000];
void solve(){
n=read(),k=read();
ll tp=n;tot=0;
while(tp)cnt[++tot]=(tp+1)/2,tp/=2;
bool gocase=false;
ll cur=1;
if(n>29)gocase=true;
else{
for(int i=1;i<=tot;i++){
if(cur>k/fac[cnt[i]]){gocase=true;break;}
cur*=fac[cnt[i]];
}
gocase|=(cur>=k);
}
if(gocase){solvecase(n);return;}
for(int i=tot+1;i<=5;i++)cnt[i]=0;
k=(k-1)/cur+1;
int V=9999,val;
memset(f,0,sizeof(f)),f[0][0][0][0][0][0]=1;
for(int a=0;a<=cnt[1];a++)for(int b=0;b<=cnt[2];b++)for(int c=0;c<=cnt[3];c++)for(int d=0;d<=cnt[4];d++)for(int e=0;e<=cnt[5];e++)for(int v=0;v<=V;v++){
if(!f[a][b][c][d][e][v])continue;
val=getval(a+b+c+d+e+1);
if(a!=cnt[1]&&v+val<=V)f[a+1][b][c][d][e][v+val]+=f[a][b][c][d][e][v];
if(b!=cnt[2]&&v+val*2<=V)f[a][b+1][c][d][e][v+val*2]+=f[a][b][c][d][e][v];
if(c!=cnt[3]&&v+val*3<=V)f[a][b][c+1][d][e][v+val*3]+=f[a][b][c][d][e][v];
if(d!=cnt[4]&&v+val*4<=V)f[a][b][c][d+1][e][v+val*4]+=f[a][b][c][d][e][v];
if(e!=cnt[5]&&v+val*5<=V)f[a][b][c][d][e+1][v+val*5]+=f[a][b][c][d][e][v];
}
for(int i=1;i<=V;i++){
k-=f[cnt[1]][cnt[2]][cnt[3]][cnt[4]][cnt[5]][i];
if(k<=0){
printf("%d\n",i);
return;
}
}
puts("-1");
}
int main(){
fac[0]=1;
for(int i=1;i<20;i++)fac[i]=fac[i-1]*i;
int T=read();
while(T--)solve();
return 0;
}