P9838
P9838
数据点分治。 考虑这个式子事实上是什么，其实它是 \(\sum i(n+1-i) f(p_i)\)。 感性看，有相当多种排列的值相同。\(f(x)=i\) 有 \(\frac{n}{2^i}\) 组解，所以，本质不同但值相同的 \(p\) 非常多，至少是 \(\prod (\frac{n}{2^i} ......
P9838 挑战 NPC IV
挑战 NPC IV - 洛谷 数据点分治诈骗好题 先考虑 \(k=1\) 怎么做？可以发现 \(f(i)\) 值相同的数量我们可以轻易算出。怎么贪心？大的对小的一一匹配即可 开始诈骗：考虑 \(n\in [29,10^6]\)。发现 \(f(i)\) 相同的值有很多，例如 \(f(i)=1\) 的大 ......
P9838 挑战 NPC IV
传送门 description 一个长度为 \(n\) 的排列的权值定义为其每个子区间内所有数 \(\text{lowbit}+1\) 之和（注意此处的 \(\text{lowbit}\) 表示二进制下最小的 1 在第几位，例如 \(\text{lowbit}(5)+1=1\)）。求所有长度为 \( ......
[题解] P9838 挑战 NPC IV
P9838 挑战 NPC IV 定义 \(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] ......
P9838 挑战 NPC IV
差点就场切了。 按 \(f\) 的值分类。令 \(n'=n\)，对于 \(i=1,2,\dots\)，\(cnt_i=\lfloor\frac{n'+1}{2}\rfloor\)，\(n'\leftarrow \lfloor\frac{n'}{2}\rfloor\)。 注意到数值相同的可以随意交换， ......