题目描述(题目难度：中等）
解题报告
输出解读
输入： 3 1 2 3 输出： 4
1,2,3总共有6个子集:
[1]----->1的异或和是1，
[2]---->2的异或和是2,
[3]---->3的异或和是3,
[1,2]---->1和2的异或和是3,
[1,3]---->1和3的异或和是2,
[2,3]---->2和3的异或和是1,
[1,2,3]---->1和2和3的异或和是0
其中, 2, 3是质数，所以有4个子集
分别是：[2]、[3]、[1,2]、[1,3]
背景抽象
读到题目中说：“给出 n nn 个互不相同的正整数。”那么每一个要么被选1次，要么一次都选不到。因此就可以向咱们可爱的额01背包方向考虑。
DP分析
注意事项
一、范围的选取
数据范围最大的数是5000, 而212 = 4096，不够5000。因此考虑异或和最大的数是 213 - 1
二、滚动数组优化
倘若不使用滚动数组，直接开空间的话，f [ n ] [ m ] f[n][m]f[n][m]中第一维至少是5000，第二维至少是213。那么所用空间 = 5000 * 213 个int 。
1MB=1024KB=1048576字节
一个int有4个字节，也就是1MB有262144个int。就大致算作250000个int吧。
那么所用的空间大致是156MB以上了。远远大于了题目所给的64MB。
因此考虑使用滚动数组进行优化。所用空间大致是 2 * 213个int。
参考代码
#include <iostream> #include <algorithm> #include <cmath> using namespace std; const int N = 1e4 + 10, M = 8192, MOD = 1e9 + 7; int f[2][M];//使用滚动数组优化 int n; int a[N]; //试除法判断x是否是质数 bool check(int x) { 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]; //背包DP 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]; 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 (check(i)) res = (res + f[n & 1][i]) % MOD; } cout << res << endl; return 0; }
