L 简略题解

赛时想了个假做法，因为水平有限赛时写、调了2.5h（反正是打星，就死磕一道题），赛后才发现假了

假做法是：对某一位，直接统计[0, a_i]中有p个1，dp[i][0] = dp[i - 1][0] * (a_i - p) + dp[i - 1][1] * p（不知道为啥，+总不显示，干脆不latex了）这是错的，因为选中一个w_i，就必须选中w_i的所有位，不能拆开（有点像23年山东省赛的J，同样的假法，但这个不能用前缀来解决）

真做法大致思路是，假设k+1位以上w_i都和w_i取相同值。如果a_i的第k位是1，那么我们可以考虑让w_i为0或1

• 如果为1，仍然是相同值
• 如果为0，我们发现这个w_i后面的位就可以从0取到2^k-1，于是后面位所有的数都可以随便取，w_i就成了1到k-1位的调节数

调节数只需要1个，并且1个调节数就不重不漏了，我们就让第一个对w_i<a_i（对第k位）作为调节数，贡献算做1。后面所有w_i<a_i的贡献为2^k，w_i=a_i的贡献为s = (a_i & (2^k - 1)) + 1

设f[i][1/0][1/0]表示枚举到第i个数，这一位目前的奇偶性，是否已经选了调节数

所以我们只需要枚举调节数对应的位k，对每一位线性递推

f[i][0][1] = s * f[i - 1][1][1] + (2^k * f[i - 1][0][1] + f[i - 1][0][0]) * (a_i & 2^k)

类似地可以写出剩下3个式子

修改就套个动态dp就行了