【题解】HackerRank - Prime XOR

Posted on Edited on In Disqus:

题目

https://www.hackerrank.com/challenges/prime-xor

题意

给 n 个介于 3500 和 4500 之间的数，求不同子集（可以包含重复元素）的总数，使得子集异或和是质数。

题解

异或和的范围在 0～8191 之间，虽然 n 很大，但是每一个数的范围很小，因此可以依次处理 3500～4500 之间的每一个数。

dp[i][k] = dp[i - 1][k] * (a[i] / 2 + 1) + dp[i - 1][k ^ v[i]] * ((a[i] + 1) / 2)

  • dp[i][k]表示前 i 个数异或和为 k 的方案数
  • a[i]记录 n 个数中 i 出现的次数，(a[i] / 2 + 1) 表示取偶数个，((a[i] + 1) / 2) 表示取奇数个
  • v[i]表示第 i 个数的值
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
#include <bits/stdc++.h>
#define FOR(i, x, y) for (__typeof(y) i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (__typeof(x) i = (x), _##i = (y); i > _##i; --i)
using namespace std;
typedef long long LL;
const int MOD = 1E9 + 7;
const int maxn = 8192 + 10;
bool p[maxn];
int t, a[5000], T, n, u;
LL dp[2][maxn];

int main() {
    for (int i = 2; i < maxn; ++i)
        if (!p[i])
            for (int j = i + i; j < maxn; j += i)
                p[j] = 1;
    scanf("%d", &T);
    while (T--) {
        memset(dp, 0, sizeof dp); u = 0; dp[0][0] = 1;
        memset(a, 0, sizeof a);
        scanf("%d", &n);
        FOR(i, 0, n) {
            scanf("%d", &t);
            ++a[t];
        }
        FOR(i, 3500, 4501)
            if (a[i]) {
                u ^= 1;
                FOR(j, 0, 8192)
                    dp[u][j] = ((1 + a[i] / 2) * dp[u ^ 1][j] + (a[i] + 1) / 2 * dp[u ^ 1][j ^ i]) % MOD;
            }
        LL ans = 0;
        FOR(i, 2, 8192)
            if (!p[i]) ans += dp[u][i];
        printf("%lld\n", ans % MOD);
    }
}