acwing1454. 异或和是质数的子集数（dp01背包）

给出 nn 个互不相同的正整数。
问存在多少个子集，使得子集中所有数的异或和是质数。
由于答案可能很大，请你输出对 109+7109+7 取模后的结果。

输入格式

第一行包含整数 nn。
第二行包含 nn 个正整数。

输出格式

输出一个整数，表示满足条件的子集数量对 109+7109+7 取模后的结果。

数据范围

1≤n≤50001≤n≤5000,
1≤1≤ 给定正整数 ≤5000≤5000。

输入样例：

3 1 2 3

输出样例：

4

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5010, M = 8192, mod = 1e9 + 7;
int a[N];
int f[N][M];
int n;
bool is_prime(int x)  // 判定质数
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
            return false;
    return true;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    //f[i][j] 表示只考虑前i个数,异或结果是j的集合
    //f[i][j] = f[i-1][j] + f[i-1][j ^ a[i]];
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) 
        for (int j = 0; j <= M; ++j) {
            f[i][j] = f[i-1][j];
            //异或值小于mod再加
            if ((a[i] ^ j) < M) f[i][j] = (f[i][j] + f[i-1][a[i] ^ j]) % mod;
        }
    int res = 0;
    for (int i = 2; i < M; ++i) {
        if (is_prime(i)) res = (res + f[n][i]) % mod;
    }
    cout << res << endl;
    return 0;
}

滚动数组优化

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5010, M = 8192, mod = 1e9 + 7;
int a[N];
int f[2][M];
int n;
bool is_prime(int x)  // 判定质数
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
            return false;
    return true;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    //f[i][j] 表示只考虑前i个数,异或结果是j的集合
    //f[i][j] = f[i-1][j] + f[i-1][j ^ 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] % mod;
            //异或值小于mod再加
            if ((j ^ a[i]) < M) f[i & 1][j] = (f[i & 1][j] + f[i - 1 & 1][j ^ a[i]]) % mod;
        }
    int res = 0;
    for (int i = 2; i < M; ++i) {
        if (is_prime(i)) res = (res + f[n & 1][i]) % mod;
    }
    cout << res << endl;
    return 0;
}