A

  • 题意: n(n < 50)个数中取至少一个数,求其中异或和等于与和的情况有多少
    每个数范围在$0-2^{13}$

位压DP
首先想到若n个数异或和等于与和,考虑每一位上,要么都为0或者有有偶数个1和0,或者全为1且有奇数个
我们用三进制来表示状态,2表示这一位都为1,1表示这一位有奇数个1,其他情况用0表示,然后再记录这些数的奇偶性。
将三进制预处理成四进制,这样就可以$O(1)$转移了

复杂度 $O(n3^{13})$

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxd = 1594323; //3^13

LL d[2][maxd][2];
int n,cur,f[1<<13][2],p[maxd],s[1<<26];

void init()
{
for(int i=0;i<(1<<13);++i)
{
for(int j=0;j<13;++j)
f[i][0] |= ((i>>j)&1)<<(j<<1);
f[i][1] = f[i][0] << 1;
}
for(int i=0;i<maxd;++i)
{
int t = i;
for(int j=12;j>=0;--j)
{
p[i] |= (t%3)<<((12-j)<<1);
t/=3;
}
s[p[i]] = i;
}
}

void print(int x)
{
for(int i=12;i>=0;--i)
{
printf("%d",((x>>(i<<1))&3));
}
puts("");
}

int main()
{
freopen("test.txt","r",stdin);
init();
scanf("%d",&n);
LL ans = 0;
int fi = f[(1<<13)-1][0],se = f[(1<<13)-1][1];
for(int z=0;z<n;++z)
{
int x;
scanf("%d",&x);
cur^=1;
memcpy(d[cur],d[cur^1],sizeof (d[0]));
for(int i = 0;i<maxd;++i)
{
if(d[cur^1][i][0])
d[cur][s[ ((p[i]&fi)^f[x][0] & (((p[i]&se)>>1)^fi) ) | (p[i]&f[x][1]) ]][1] += d[cur^1][i][0];
if(d[cur^1][i][1])
d[cur][s[ ((p[i]&fi)^f[x][0] & (((p[i]&se)>>1)^fi) ) | (((p[i]&f[x][1])>>1)^((p[i]&se)>>1)) | (p[i]&f[x][1]) ]][0] += d[cur^1][i][1];
}
++d[cur][s[f[x][1]]][1];
}
for(int i = 0;i<maxd;++i)
{
for(int j=0;j<2;++j)
{
if(!d[cur][i][j]) continue;
bool flag = true;
int t = i;
while(t)
{
int tt = t%3;
if(tt == 1 || (tt == 2 && j == 0))
{
flag = false;
break;
}
t/=3;
}
if(flag)
{
// printf("%d %d %lld\n",i,j,d[cur][i][j]);
ans += d[cur][i][j];
}
}
}
printf("%lld\n",ans);
return 0;
}