定义 \(f(x) = 1 + \log_2 \operatorname{lowbit}(x)\)。
定义一个 \(1 \sim n\) 的排列 \(p\) 的权值是 \(\sum_{l = 1}^n \sum_{r = l}^n \sum_{i \in [l, r]} f(p_i)。\)
求所有 \(1 \sim n\) 的排列中权值第 \(k\) 小的排列的权值，对 \(998244353\) 取模。
\(n \le 10^{18}, k \le \min(n!, 10^{18})\)。
首先可以发现，权值最小的排列数量其实是很多的，大概有 \(\prod_{i = 0}^{\left\lfloor \log_2 n \right\rfloor} \left(\lfloor \frac{n}{2^i} \rfloor - \lfloor \frac{n}{2^{i + 1}} \rfloor\right)!\) 个。这个数在 \(n = 29\) 时就超过了 \(10^{18}\)，所以当 \(n > 28\) 时，只需考虑求最小的权值；当 \(n \le 28\) 时，可以直接暴力 dp。
Part1 \(n > 28\)
不难发现，权值实际上就是 \(\sum_{i = 1}^n f(p_i) \cdot i \cdot (n - i + 1)\)。
这里有一个贪心就是 \(f(p_i)\) 大的数尽量往两边放，小的尽量往中间放，这个是显然的。
然后去优化这个贪心。考虑先求出每种 \(f(x)\) 的数量，然后一种一种的放。数量是好求的，然后需要求的就是：
由于本质不同的 \(f(x)\) 的数量是 \(O(\log n)\) 的，所以这部分时间复杂度是 \(O(\log n)\) 的。
Part2 \(n \le 28\)
这部分大体的思路就是由于最大的权值是 \(6000\) 左右的，所以可以对每种权值求出它对应的排列的个数。
由于本质不同的 \(f(x)\) 至多有 5 个，所以可以设计 dp 为 \(f_{now_1, now_2, now_3, now_4, now_5, val}\) 表示 \(f(x) = i\) 的选了 \(now_i\) 个，权值为 \(val\) 时的方案数，转移就是枚举哪个数多选了一个向后转移。
状态数大概是 \(15 \times 8 \times 5 \times 3 \times 2 \times 5983 = 21538800\)。
constexpr int MAXLG = 60, inv2 = 499122177, inv6 = 166374059;
ll n, k;
namespace Solve1 {
ll lim[MAXLG];
int calc(ll L, ll R) {
if (L > R) return 0;
auto s1 = [&](int n) { return mul(mul(n, n + 1), inv2); };
auto s2 = [&](int n) { return mul(mul(mul(n, n + 1), 2 * n + 1), inv6); };
auto sum1 = [&](int l, int r) { return del(s1(r), s1(l - 1)); };
auto sum2 = [&](int l, int r) { return del(s2(r), s2(l - 1)); };
int N = (n + 1) % MOD, l = L % MOD, r = R % MOD;
int ans = del(mul((int)((n + 1) % MOD), sum1(l, r)), sum2(l, r));
return add(ans, ans);
}
int Main() {
for (int i = 0; i <= __lg(n); i ++) lim[i] = (n >> i) - (n >> i + 1);
int ans = 0; ll pos = 1; bool lst = false;
for (int i = __lg(n); ~i; i --) {
int ret = 0; ll cnt = lim[i];
if (lst) {
cadd(ret, (int)mul(pos % MOD, (n - pos + 1) % MOD));
cnt --, pos ++, lst = false;
}
if (cnt > 1) {
cadd(ret, calc(pos, pos + (cnt >> 1) - 1));
pos += cnt >> 1, cnt &= 1;
}
if (cnt) cadd(ret, (int)mul(pos % MOD, (n - pos + 1) % MOD)), lst = true;
cadd(ans, mul(ret, i + 1));
}
Write(ans, '\n');
return 0;
}
}
namespace Solve2 {
int cnt[6], val[30];
ll f[15][8][5][3][2][5983];
int Main() {
for (int i = 1; i <= n; i ++)
cnt[__lg(i & -i) + 1] ++;
ll ret = 1;
for (int i = 1; i <= __lg(n) + 1; i ++)
for (int j = 1; j <= cnt[i]; j ++) ret *= j;
for (int i = 1; i <= n; i ++)
val[i] = i * (n - i + 1);
sort(val + 1, val + n + 1);
{
int now[6];
f[0][0][0][0][0][0] = 1;
for (now[1] = 0; now[1] <= cnt[1]; now[1] ++) for (now[2] = 0; now[2] <= cnt[2]; now[2] ++)
for (now[3] = 0; now[3] <= cnt[3]; now[3] ++) for (now[4] = 0; now[4] <= cnt[4]; now[4] ++)
for (now[5] = 0; now[5] <= cnt[5]; now[5] ++) {
int sum = 1;
for (int i = 1; i <= 5; i ++) sum += now[i];
for (int u = 0; u <= 5982; u ++) {
for (int i = 1; i <= 5; i ++) if (now[i] < cnt[i]) {
ll pre = f[now[1]][now[2]][now[3]][now[4]][now[5]][u];
now[i] ++; int v = u + i * val[sum];
if (v > 5982) { now[i] --; continue; }
f[now[1]][now[2]][now[3]][now[4]][now[5]][v] += pre;
now[i] --;
}
}
}
}
for (int i = 0; i <= 5982; i ++) {
k -= f[cnt[1]][cnt[2]][cnt[3]][cnt[4]][cnt[5]][i] * ret;
if (k <= 0) { Write(i, '\n'); break; }
}
{
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 i = 0; i <= 5982; i ++)
f[a][b][c][d][e][i] = 0;
for (int i = 1; i <= __lg(n) + 1; i ++) cnt[i] = 0;
}
return 0;
}
}
void slv() {
n = Read<ll>(), k = Read<ll>();
if (n > 28) return Solve1::Main(), void();
else return Solve2::Main(), void();
}