par = parity of the number of kth bits which are on f = if we have offed any kth bit
| 29 | // par = parity of the number of kth bits which are on |
| 30 | // f = if we have offed any kth bit |
| 31 | int yo(int i, int par, int f) { |
| 32 | if (i == -1) { |
| 33 | return par == Z and f; |
| 34 | } |
| 35 | int &ret = dp[i][par][f]; |
| 36 | if (ret != -1) return ret; |
| 37 | ret = 0; |
| 38 | if (A[i] >> k & 1) { |
| 39 | ret += 1LL * yo(i - 1, par ^ 1, f) * ((A[i] - (1LL << k) + 1) % mod) % mod; // keep it on |
| 40 | ret %= mod; |
| 41 | // make it off |
| 42 | if (f) { |
| 43 | ret += 1LL * yo(i - 1, par, 1) * ((1LL << k) % mod) % mod; |
| 44 | ret %= mod; |
| 45 | } |
| 46 | else { |
| 47 | ret += yo(i - 1, par, 1); |
| 48 | ret %= mod; |
| 49 | } |
| 50 | } |
| 51 | else { |
| 52 | ret += 1LL * yo(i - 1, par, f) * ((A[i] + 1) % mod) % mod; |
| 53 | ret %= mod; |
| 54 | } |
| 55 | return ret; |
| 56 | } |
| 57 | |
| 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)) |