AcWing 1454. 异或和是质数的子集数-Java
原题链接
中等
作者:
三玖天下第一
,
2021-02-02 16:19:01
,
所有人可见
,
阅读 414
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(reader.readLine());
int[][] f = new int[2][8192];
int[] a = new int[n];
int mod = (int) (1e9+7);
String[] temp = reader.readLine().split(" ");
for (int i = 0; i < n; i++) {
a[i] = Integer.parseInt(temp[i]);
}
f[0][0] = 1;
for (int i = 1; i <=n; i++) {
for (int j = 0; j < 8192; j++) {
f[i&1][j] = f[(i-1)&1][j];
if ((j^a[i-1]) < 8192){
f[i&1][j] = ((f[i&1][j]) + f[(i-1)&1][j^a[i-1]]) % mod;
}
}
}
int res = 0;
for (int i = 2; i < 8192; i++) {
if (is_prime(i)){
res = (res+f[n&1][i])%mod;
}
}
System.out.println(res);
}
public static boolean is_prime(int a){
for (int i = 2; i*i <= a; i++) {
if (a%i == 0) return false;
}
return true;
}
}