DefectiveAddition

作者：王聿中

关键词：异或 乱搞

题目简述

给定一个序列$A$和一个整数$n$，要求构造一个长度与原序列相同的序列$B$，对于每个位置$i$，要求$0\leq {B}_{i}\leq {A}_{i}$，且序列$B$的异或和为$n$。求方案数（模${10}^{9}+7$）。

$0\leq n, {A}_{i}\leq {10}^{9}$ $len\leq 50$

分析

考虑一个简单的问题，如果$B$有一个位置（不妨假设是$k$）的数没有上界（可以大于${10}^{9}$），即${A}_{k}=+\infty$，那么答案为多少呢？

不难发现，无论$B$的其他位置如何取值、异或和为多少（假设这个异或和为$x$），只要这个没有上界的位置取$x\space xor\space n$即可满足要求，也就是说，这个位置可以用作最后的“修正”。因此，答案即为除去该位置，其他位置合法取值个数的乘积，即$\prod \left( {A}_{i}+1\right)$，其中$i\neq k$。

而对于原问题，我们发现，如果某一位上${A}_{i}$为1，而该位上${B}_{i}$取$0$，那么对于当前位右边的位而言，${B}_{i}$即可以看作是没有上界的，问题也就变简单了。

那么，我们针对每一位，只需要统计，对于其左边的位所有${B}_{i}$严格等于其上界，对于当前位有${B}_{i}$不等于其上界的情况种类数即可。

算法一

根据分析，我们从高到低枚举每一个二进制位。可以先假设，对于之后的位，已经有位置取值无上界，这样方便我们的计算。

我们可以维护两个变量$s0, s1$分别表示$B$在当前位异或和为$0$和$1$的方案数，然后我们枚举序列上的位置$j$。如果${A}_{j}$当前位为$0$，那么${B}_{j}$当前位也只能取$0$；否则当前位可以取到$0$或$1$，由于假设的存在，我们可以直接用下面这段代码来计算$s0, s1$（其中$bit$为当前位，$cards$为题面中的序列$A$。方便起见，$cards$中高于当前位的位已经都被置零）：

for (int j=0;j<cards.size();++j)if (cards[j]&bit){//calc s0&s1
    cnt^=bit;
    cards[j]^=bit;
    ll tmps0=s0;
    s0=(s0*bit+s1*(cards[j]+1))%P;
    s1=(s1*bit+tmps0*(cards[j]+1))%P;
}
else (s0*=cards[j]+1)%=P,(s1*=cards[j]+1)%=P;

根据$n$的当前位，我们可以确定$s0$和$s1$哪个是我们需要的，并记为我们的初步统计结果。然后，如果所有${A}_{i}$在当前位的异或和与$n$的当前位一致，那么所有${B}_{i}$在当前位取到上界的情况就会被误统计在内，需要将它减掉。再结合假设，我们需要找到一个没有取到上界的${B}_{i}$作“修正”用，因此有一个取值无上界的位置需要被除掉，将统计结果除以$bit$即可。

最后，如果所有${A}_{i}$在当前位的异或和与$n$的当前位不一致，那么对于接下来的位，其左边所有${B}_{i}$严格等于其上界的情况就不存在了，所以直接退出循环。

需要注意的是，如果所有${A}_{i}$的异或和等于$n$，那么所有${B}_{i}$都取到上界的情况会被遗漏，因此这种情况下答案需要加一。