17725. Bad XOR

You are given an array A of n elements. Also you are given another array B of m elements. Any subset (i₁, i₂, i₃, …., i_p) is bad IFF ( A_i1 ⊕ A _i2 ⊕ …. ⊕ A_ip) equals any value of B. ⊕ means Bitwise XOR, which can be found with ^ syntax in popular programming languages. Now your job is to find the number of good subsets. Empty Subset has XOR value of 0.

Input. The first line of input denotes the number of test cases t (1 ≤ t ≤ 20). The first line of each test case contains two integers n and m (0 ≤ n, m ≤ 1000). The next line contains n integers of the array A (0 ≤ A_i ≤ 1000). The next line contains m integers of the array B (0 ≤ B_i ≤ 1000). You can assume that each element of array B will be unique.

Output. For each case, print the case number and the total numbers of good subsets in a line. As the result can be very big, output it modulo 100000007.

Sample Input

2

2 3

1 2

0 1 2

1 3

1

0 1 2

Sample Output

Case 1: 1

Case 2: 0

РЕШЕНИЕ

динамическое программирование

Анализ алгоритма

Пусть dp[i][j] равно количеству способов получить значение j в результате операции xor из произвольного подмножества первых i элементов массива A.

Изначально положим dp[0][0] = 1. Значение dp[i][j] равно:

· количеству способов получить значение j из первых i – 1 элементов (если число a_i не используем), их количество равно dp[i – 1][j];

· если число a_i используется в xor сумме, то dp[i][j] равно количеству способов получить xor сумму S из подмножества первых i – 1 элементов, где S ^ a_i = j. Однако в таком случае S = j ^ a_i. То есть количество таких способов равно dp[i – 1][j ^ a_i];

То есть для всякого j (0 ≤ j ≤ 1000) и i = 1, …, n следует пересчитать

dp[i][j] = (dp[i – 1][j] + dp[i – 1][j ^ a_i]) % 100000007

Для решения задачи остается просуммировать значения dp[n][j], где 0 ≤ j ≤ 1000 и j не входит в массив В.

Реализация алгоритма

#include <stdio.h>

#include <string.h>

#define MOD 100000007

int dp[1025][1025];

int a[1025], b[1025], inB[1025];

int t, n, m, i, j, c;

int main(void)

{

scanf("%d",&t);

for(c = 1; c <= t; c++)

{

scanf("%d %d",&n,&m);

for(i = 1; i <= n; i++)

scanf("%d",&a[i]);

memset(inB,0,sizeof(inB));

for(j = 1; j <= m; j++)

{

scanf("%d",&b[j]);

inB[b[j]] = 1;

}

memset(dp,0,sizeof(dp));

dp[0][0] = 1;

for(i = 1; i <= n; i++)

{

int val = a[i];

for(j = 0; j < 1024; j++)

dp[i][j] = (dp[i-1][j] + dp[i-1][j^val]) % MOD;

}

int ans = 0;

for(j = 0; j < 1024; j++)

if(!inB[j]) ans = (ans + dp[n][j]) % MOD;

printf("Case %d: %d\n",c,ans);

}

return 0;

}