力 大 砖 飞 2

· · 个人记录

前置阅读：https://www.luogu.com.cn/blog/250637/li-da-zhuan-fei。

很显然那个文里我们使用了取模，这是很不牛的，因为 WRM 并不认为随便取模是常数时间。于是 ut 又重新考虑了一次问题并意识到自己傻掉了，这里是一个另外的算法，不需要取模。

我们记 r 为满足 2^r-1\ge k 的最小正整数。我们建立一个 r\times\omega 位的大二进制数，对于原数第 i 位为第 j 个 1，在新数的 i\times r 位起的 r 位存储二进制形式下的 j。十分显然我们查一个前缀数 1 本质上只需要找到最高位的 1 然后把对应位的答案提取出来就可以了，这是平凡的。

原神，卸载！