题目
给出 个互不相同的正整数。
问存在多少个子集，使得子集中所有数的异或和是质数。
由于答案可能很大，请你输出对 取模后的结果。
输入格式
第一行包含整数 。
第二行包含 个正整数。
输出格式
输出一个整数，表示满足条件的子集数量对 取模后的结果。
数据范围
,
给定正整数 。
输入样例：
3
1 2 3
输出样例：
4
题解
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
| #include <iostream>
using namespace std;
const int N = 5010, M = 8192, MOD = 1e9 + 7;
int a[N];
int f[2][M];
bool is_primes(int x)
{
for (int i = 2; i <= x / i; ++ i)
if (x % i == 0) return false;
return true;
}
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
f[0][0] = 1;
for (int i = 1; i <= n; ++ i)
for (int j = 0; j < M; ++ j)
f[i & 1][j] = (f[i - 1 & 1][j] + f[i - 1 & 1][j ^ a[i]]) % MOD;
int ans = 0;
for (int j = 2; j < M; ++ j)
if (is_primes(j))
ans = (ans + f[n & 1][j]) % MOD;
cout << ans << endl;
}
|
存在两个疑惑
1.f[0][0] = 1
2.选i的状态计算 f[i - 1][j ^ a[i]]
