P9838 Challenge NPC IV

If only everything were as easy as an NPC problem.

Little A wants to write a love poem for Little B. He has come up with $n$ sentences, and the elegance of each sentence is $1, 2 \dots n$, respectively. Little A needs to combine them in some order to form a complete poem. In other words, Little A needs to reorder these $n$ sentences to form a permutation $p_1, p_2\dots p_n$ of $1 \sim n$; the elegance of the $i$-th line is the elegance of the original $p_i$-th sentence, that is, $p_i$. However, since Little A is an OIer, his writing quality is not very stable. In fact, he will greatly overestimate how elegant his sentences are. If a sentence has elegance $x$ in Little A's eyes, then Little B thinks its elegance is **the position of the lowest $1$ bit in the binary representation of $x$**. Here, Little B considers the lowest bit position to be $1$, the next lowest to be $2$, and so on. That is, the elegance in Little B's eyes is $f(x) = 1 + \log_2 \operatorname{lowbit}(x)$. Little A knows that after Little B gets the poem, she will only choose a segment of it to read, and the elegance she feels is the sum of the lines she reads. Specifically, if the poem has $n$ lines, then Little B will pick an interval $[l, r]$ among all intervals in $[1, n]$ with length $> 0$, and feel an elegance of $\displaystyle\sum_{l \leq i \leq r}f(p_i)$. To measure a poem's elegance, Little A defines the poem's total elegance as **the sum of the elegance Little B feels in all cases**. In principle, the arrangement with the maximum total elegance must be the best. Unfortunately, after Little A's precise calculations, he found that only when he chooses the love poem whose total elegance is exactly the **$k$-th smallest** will he be most likely to end up with Little B. So Little A wants to know: among the $n!$ essentially different poems, what is the possible total elegance of the $k$-th smallest one. Two poems are essentially the same if and only if the original permutation $p_1 \dots p_n$ is the same. Little A discovered that this is an NPC problem, so he had to ask you for help. Since the total elegance is too large, you only need to output the answer modulo $998244353$. In particular, Little A wrote $q$ groups of sentences, so you need to answer his $q$ queries separately.

Read from standard input. The first line contains a positive integer $q$, representing the number of groups of sentences. For each group of testdata, there is only one line containing two positive integers $n, k$ describing Little A's query.

Write to standard output. For each group of sentences, output one integer per line, representing the total elegance of the $k$-th smallest poem modulo $998244353$.

#### Sample 1 Explanation For example, when $p = [1, 3, 2]$, the elegance of each line in Little B's eyes is $[1, 1, 2]$. Then: - When $l = 1$, $r = 1$, the sum is $1$. - When $l = 2$, $r = 2$, the sum is $1$. - When $l = 3$, $r = 3$, the sum is $2$. - When $l = 1$, $r = 2$, the sum is $1 + 1 = 2$. - When $l = 2$, $r = 3$, the sum is $1 + 2 = 3$. - When $l = 1$, $r = 3$, the sum is $1 + 1 + 2 = 4$. So the total elegance of $p = [1, 3, 2]$ is $1 + 1 + 2 + 2 + 3 + 4 = 13$. For all $3! = 6$ permutations $p$, sorting their total elegance from small to large gives $13, 13, 13, 13, 14, 14$. Therefore, when $k = 2$ and $k = 6$, the answers are $13$ and $14$, respectively. --- #### Sample 2 See the attached $\verb!npc/npc2.in!$ and $\verb!npc/npc2.ans!$. --- #### Sample 3 See the attached $\verb!npc/npc3.in!$ and $\verb!npc/npc3.ans!$. --- #### Constraints **The time limit is different for different test points. Specifically, the time limit for each point is $\max(q\times 0.5, 2)\ \rm{s}$.** | Test Point ID | $n$ | $k \leq$ | $q = $ | | :--------: | :-: | :------: | :----: | | $1 \sim 3$ | $\leq 10$ | $n!$ | $2$ | | $4 \sim 8$ | $\leq 10^3$ | $2$ | $7$ | | $9 \sim 13$ | $\in [10^5, 10^6]$ | $\min(10^{18}, n!)$ | $7$ | | $14 \sim 17$ | $\leq 10^6$ | $\min(10^{18}, n!)$ | $7$ | | $18 \sim 25$ | $\leq 10^{18}$ | $\min(10^{18}, n!)$ | $10$ | For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 10^{18}$, $1 \leq k \leq \min(10^{18}, n!)$, and $1 \leq q\le 10$. Translated by ChatGPT 5