挑战NPCIV-洛谷数据点分治诈骗好题先考虑\(k=1\)怎么做？可以发现\(f(i)\)值相同的数量我们可以轻易算出。怎么贪心？大的对小的一一匹配即可开始诈骗：考虑\(n\in[29,10^6]\)。发现\(f(i)\)相同的值有很多，例如\(f(i)=1\)的大约有\(\frac{n}{2}\)个，\(f(i)=2\)

传送门description一个长度为\(n\)的排列的权值定义为其每个子区间内所有数\(\text{lowbit}+1\)之和（注意此处的\(\text{lowbit}\)表示二进制下最小的1在第几位，例如\(\text{lowbit}(5)+1=1\)）。求所有长度为\(n\)的排列中权值第\(k\)小的排列的权值。\(n\leq10^{

P9838挑战NPCIV定义\(f(x)=1+\log_2\operatorname{lowbit}(x)\)。定义一个\(1\simn\)的排列\(p\)的权值是\(\sum_{l=1}^n\sum_{r=l}^n\sum_{i\in[l,r]}f(p_i)。\)求所有\(1\simn\)的排列中权值第\(k\)小的排列的权值，对\(998244353\)取模。

差点就场切了。按\(f\)的值分类。令\(n'=n\)，对于\(i=1,2,\dots\)，\(cnt_i=\lfloor\frac{n'+1}{2}\rfloor\)，\(n'\leftarrow\lfloor\frac{n'}{2}\rfloor\)。注意到数值相同的可以随意交换，这就是说在无标号情况下的一种本质不同方案对应有标号情况下的\(\prodcnt_i!\)种方