CDOJ 1825 柱爷搞搞搞搞搞xxxxoooorrrrr

题面传送门

类似数位DP的思想,
考虑对于这$n$个数的前$i$位,我们对每个数的前$i$位选的都是它的上界(最大值),那么这前$i$位的异或和结果只有一种,然后我们考虑它们的第$i + 1$位存在一些数选的不是上界,假设第一个没有选上界的数为第$j$个,那么存在其它数随便选后,第$j$个数最后总能选择一个数使得最后的异或和为给定值.(因为第$j$个数能选择的数的范围是一个全集)
我们可以$O(n)$的DP出前$i$位都选上界,第$i + 1$位存在一些数选的不是上界的情况下产生的方案数.
按位枚举,总复杂度就是$nlog_{2}1e9$
整体思想类似DP套DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
void add(int &x, int y) {
x += y;
if(x >= mod) x -= mod;
}
int mul(int x, int y) {
LL z = 1LL * x * y;
return z - z / mod * mod;
}
int f[maxn][2][2], a[maxn];
int solve(int n, int k, int e) {
int i, j, res = (1 << k) - 1;
memset(f, 0, sizeof(f));
f[0][0][0] = 1;
for(i = 0; i < n; i++) {
j = (a[i] & res) + 1;
if((a[i] >> k) & 1) {
add(f[i + 1][0][1], f[i][0][0]);
add(f[i + 1][1][1], f[i][1][0]);
add(f[i + 1][0][1], mul(f[i][0][1], 1 << k));
add(f[i + 1][1][1], mul(f[i][1][1], 1 << k));
add(f[i + 1][1][0], mul(f[i][0][0], j));
add(f[i + 1][0][0], mul(f[i][1][0], j));
add(f[i + 1][1][1], mul(f[i][0][1], j));
add(f[i + 1][0][1], mul(f[i][1][1], j));
} else {
f[i + 1][0][0] = mul(f[i][0][0], j);
f[i + 1][0][1] = mul(f[i][0][1], j);
f[i + 1][1][0] = mul(f[i][1][0], j);
f[i + 1][1][1] = mul(f[i][1][1], j);
}
}
return f[n][e][1];
}
int main() {
#ifdef CX_TEST
freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
int n, i, k, sum = 0, ans = 0;
scanf("%d%d", &n, &k);
for(i = 0; i < n; i++) {
scanf("%d", &a[i]);
sum ^= a[i];
}
for(i = 30; i >= 0; i--) {
add(ans, solve(n, i, (k >> i) & 1));
if((sum >> i) != (k >> i)) break;
}
if(sum == k) add(ans, 1);
printf("%d\n", ans);
return 0;
}