number of solutions of the equation x0 xor x1 xor ... x(n - 1) = x s.t. 0 <= xi <= ai O(n * log(MAX))
| 58 | // number of solutions of the equation x0 xor x1 xor ... x(n - 1) = x s.t. 0 <= xi <= ai |
| 59 | // O(n * log(MAX)) |
| 60 | int solve(vector<long long> a, long long x, int K) { |
| 61 | int n = a.size(); |
| 62 | k = K; |
| 63 | bool allzero = true; |
| 64 | for (int i = 0; i < n; i++) { |
| 65 | allzero &= a[i] == 0; |
| 66 | } |
| 67 | if (allzero) return x == 0; |
| 68 | int cnt = 0; |
| 69 | for (int i = 0; i < n; i++) { |
| 70 | long long x = a[i]; |
| 71 | cnt += x >> k & 1; |
| 72 | } |
| 73 | memset(dp, -1, sizeof dp); |
| 74 | A = a; |
| 75 | Z = x >> k & 1; |
| 76 | int ans = yo(n - 1, 0, 0); |
| 77 | if (cnt % 2 == Z) { |
| 78 | for (int i = 0; i < n; i++) { |
| 79 | long long &x = a[i]; |
| 80 | if (x >> k & 1) x ^= 1 << k; |
| 81 | } |
| 82 | if (x >> k & 1) x ^= 1 << k; |
| 83 | ans += solve(a, x, k - 1); |
| 84 | ans %= mod; |
| 85 | } |
| 86 | return ans; |
| 87 | } |
| 88 | int main() { |
| 89 | ios_base::sync_with_stdio(0); |
| 90 | cin.tie(0); |