Cerinta completa

A war has broken down between Vim and Emacs. Gedit, being Vim’s ally, is captured by Emacs as a prisoner of war and it is up to Vim to rescue him by defeating Emacs.

For this task, Vim has to assemble an army of appropriate skills. He can choose a non-empty subset of soldiers from a set of soldiers (numbered from to ). Each soldier has some subset of skills out of different skills (numbered from to ). The skill-set of an army is the union of skill-sets of its constituent soldiers. To win the war, Vim needs to know how many different subsets of soldiers satisfy his skill-set requirement. Since the answer can be huge, print it modulo .

Note : The chosen army’s skill-set must exactly match the skill-set requirement of Vim (i.e no extra skills must be present in the army’s skill-set than what is required).

Input Format

The first line contains and , the number of soldiers to choose from and the number of different skills possible respectively.
The next lines contain boolean characters each. If the character of the line is , then the soldier possess the skill and if it is , then not.
The last line contains boolean characters denoting the requirement skill-set of Vim where the character being signifies that Vim wants the skill to be present in his final army and not, otherwise.

Constraints


Output Format

Output in a single line the required answer, as explained above.

Sample Input

4 2  
00  
10  
01  
11  
11

Sample Output

10

Explanation

Vim wants both the skills to be present in his selected army. Hence, he can choose the following subsets of soldiers:

Limbajul de programare folosit: cpp14

Cod:

// vim-war.cpp
// Vim War
// Week of Code 16
// Author: derekhh
// Jul 9, 2015

#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 100000;
const int MAXM = 20;
const int MOD = 1000000007;

int originalSkill[MAXN];
int f[1 << MAXM][MAXM + 1];

int modexp(int a, int b) {
	long long res = 1 % MOD, val = a % MOD;
	while (b) {
		if (b & 1)
			res = (res * val) % MOD;
		val = (val * val) % MOD;
		b >>= 1;
	}
	return (int)res;
}

int main() {
	int n, m;
	char str[MAXM + 1];
	scanf("%d %d\n", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%s", str);
		int val = 0;
		for (int j = 0; j < m; j++)
			val = val * 2 + (str[j] - '0');
		originalSkill[i] = val;
	}
	int target = 0, newm = 0;
	scanf("%s", str);
	for (int i = 0; i < m; i++) {
		if (str[i] == '1') {
			target = target * 2 + 1;
			newm++;
		}
	}

	for (int i = 0; i < n; i++) {
		int val = 0;
		bool flag = true;
		for (int j = m - 1; j >= 0; j--) {
			if (str[m - j - 1] == '1') {
				if (originalSkill[i] & (1 << j)) val = val * 2 + 1;
				else val *= 2;
			}
			else {
				if (originalSkill[i] & (1 << j)) {
					flag = false;
					break;
				}
			}
		}
		if (flag) f[val][newm]++;
	}

	for (int j = newm; j > 0; j--) {
		for (int i = 0; i < (1 << newm); i++) {
			f[i][j - 1] += f[i][j];
			int val = (i & (1 << (j - 1)));
			if (val == 0) {
				f[i | (1 << (j - 1))][j - 1] += f[i][j];
			}
		}
	}

	/*
	for (int i = 0; i < (1 << newm); i++) {
		printf("f[%d][0] = %d\n", i, f[i][0]);
	}
	*/
	
	int ans = 0;
	for (int i = 0; i < (1 << newm); i++) {
		int cnt = 0;
		for (int j = 0; j < newm; j++) {
			if (i & (1 << j)) 
				cnt++;
		}
		int val = modexp(2, f[i][0]);
		if (cnt % 2 == newm % 2) ans = (ans + val) % MOD;
		else ans = (ans - val + MOD) % MOD;
	}
	if (target == 0)
		printf("%d\n", (ans - 1 + MOD) % MOD);
	else
		printf("%d\n", ans);
	return 0;
}

Scor obtinut: 1.0

Submission ID: 464605010

Link challenge: https://www.hackerrank.com/challenges/vim-war/problem

Vim War