Vim War


Problem Statement :


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 1 to N). Each soldier has some subset of skills out of M different skills (numbered from 1 to M). 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 10^9+7.

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 N and M, the number of soldiers to choose from and the number of different skills possible respectively.
The next N lines contain M boolean characters each. If the  character of the  line is , then the  soldier possess the jth skill and if it is 0, then not.
The last line contains M boolean characters denoting the requirement skill-set of Vim where the  jth character being 1 signifies that Vim wants the jth skill to be present in his final army and not, otherwise.

Constraints

1 <= N <= 10^5
1<= M <= 20
Output Format

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


Solution :



title-img 


                            Solution in C :

In C++ :





/*
*/
 
//#pragma comment(linker, "/STACK:16777216")
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>
#include <memory.h>
#include <ctime> 

#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash

#define eps 1e-9
#define M_PI 3.141592653589793
#define bs 1000000007
#define bsize 512

using namespace std;

int pw[1<<20];

int cbits(int x)
{
	return x==0?0:cbits(x/2)+x%2;
}

int n,m,ans[1<<20];
string st;
int sub[1<<20];
int cnt[1<<20];
int nmask;

int main(){
//freopen("enigmatic.in","r",stdin);
//freopen("enigmatic.out","w",stdout);
//freopen("F:/in.txt","r",stdin);
//freopen("F:/output.txt","w",stdout);
ios_base::sync_with_stdio(0);
//cin.tie(0)

pw[0]=1;
for (int i=1;i<(1<<20);i++)
	pw[i]=pw[i-1]*2%bs;

cin>>m>>n;
for (int i=0;i<m;i++)
{
	cin>>st;
	int mask=0;
	for (int j=0;j<n;j++)
		mask=mask*2+st[j]-48;
	cnt[mask]++;
}

string st;
cin>>st;
for (int i=0;i<n;i++)
	nmask=nmask*2+st[i]-48;
	
for (int i=0;i<(1<<n);i++)
	sub[i]=cnt[i];
	
for (int ps=0;ps<n;ps++)
	for (int mask=0;mask<(1<<n);mask++)
		if (mask&(1<<ps))
			sub[mask]+=sub[mask-(1<<ps)];

ans[nmask]=pw[sub[nmask]];

for (int mask=nmask-1;mask>=0;--mask)
{
	int tmask=(mask|nmask);
	if (tmask!=nmask)continue;
	int dif=cbits(mask^nmask);
	
	if (dif%2==1)
		ans[nmask]-=pw[sub[mask]]%bs;
	else
		ans[nmask]+=pw[sub[mask]]%bs;
	
	ans[nmask]%=bs;
}

if (nmask==0)
	ans[nmask]-=1;

cout<<(ans[nmask]%bs+bs)%bs<<endl;

//cin.get();cin.get();
return 0;}








In Java :





import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    private static final int MAX_N= 100000;
    private static final int MAX_M= 20;
    private static final int MODULO= 1000000007; 
    
    public static void main(String[] args) throws Exception {
        Scanner in = new Scanner(System.in); 
        String str;
        int [] skills = new int[MAX_N];
        int [][] f = new int [1<< MAX_M][MAX_M + 1];
        int n = in.nextInt();
        int m = in.nextInt();
        in.nextLine();
        
        
       for (int i = 0; i < n; i++) {
       boolean ok = true;
        str = "";
        while (ok) {
            str = in.nextLine();
            ok = !(str != "");
        }
        int value = 0;
        for (int j = 0; j < m; j++)
            value = value * 2 + (str.charAt(j) - '0');
        skills[i] = value;
        
        }
            
        int target = 0;
        int nuevo_m = 0;
        str = "";
        str = in.nextLine();
        for (int i = 0; i < m; i++) {
        if (str.charAt(i) == '1') {
            target = target * 2 + 1;
            nuevo_m++;
            }
       
        }

        for (int i = 0; i < n; i++) {
        int value = 0;
        boolean flag = true;
        for (int j = m - 1; j >= 0; j--) {
            if (str.charAt(m - j - 1) == '1') {
                if ( (skills[i] & (1 << j)) != 0) value = value * 2 + 1;
                else value *= 2;
            }
            else {
                if ( (skills[i] & (1 << j) ) != 0 ) {
                    flag = false;
                    break;
                }
            }
        }
        if (flag) f[value][nuevo_m]++;
    }
    
    for (int j = nuevo_m; j > 0; j--) {
        for (int i = 0; i < (1 << nuevo_m); i++) {
            f[i][j - 1] += f[i][j];
            int value = (i & (1 << (j - 1)));
            if (value == 0) {
                f[i | (1 << (j - 1))][j - 1] += f[i][j];
            }
        }
    }

    int respuesta = 0;
    for (int i = 0; i < (1 << nuevo_m); i++) {
        int cnt = 0;
        for (int j = 0; j < nuevo_m; j++) {
            if ( (i & (1 << j)) != 0) 
                cnt++;
        }
        int value = getMod(2, f[i][0]);
        if (cnt % 2 == nuevo_m % 2) respuesta = (respuesta + value) % MODULO;
        else respuesta = (respuesta - value + MODULO) % MODULO;
    }
    if (target == 0)
        System.out.println( (respuesta - 1 + MODULO) % MODULO);
    else
        System.out.println(respuesta);
    }
    
        private static int getMod(int x, int y) {
        long res = 1 % MODULO;
        long value = x % MODULO;
        while (y>0) {
        if ( (y & 1) != 0 )
            res = (res * value) % MODULO;
        value = (value * value) % MODULO;
        y >>= 1;
    }
    return (int)res;
    }
       
    }

    







In C :





#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define MAX 1048576
#define MOD 1000000007
#define clr(ar) memset(ar, 0, sizeof(ar))
#define read() freopen("lol.txt", "r", stdin)

int n, m, r, pos[25], ar[MAX], temp[MAX], P[MAX], dp[MAX][2];

int Solve(){
    int i, j, k, x, y, u, v, bitmask;

    clr(dp);
    for (i = 0; i < n; i++) dp[ar[i]][0]++;

    for (j = 1; j < 21; j++){
        u = j & 1;
        v = (j - 1) & 1;

        for (i = 0; i < MAX; i++){
            if (i & (1 << (j - 1))) dp[i][u] = dp[i][v];
            else dp[i][u] = (dp[i][v] + dp[i + (1 << (j - 1))][v]);
        }
    }

    int res = P[n];
    for (bitmask = 1; bitmask < MAX; bitmask++){
        x = dp[bitmask][0];
        if (x){
            if (__builtin_popcount(bitmask) & 1) res = (res - P[x] + MOD) % MOD;
            else res = (res + P[x]) % MOD;
        }
    }

    return res;
}

int main(){
    char str[25];
    int i, j, k, x, lim;

    P[0] = 1;
    for (i = 1; i < MAX; i++) P[i] = (P[i - 1] << 1) % MOD;
    for (i = 0; i < MAX; i++) P[i] = (P[i] - 1 + MOD) % MOD;

    while (scanf("%d %d", &n, &m) != EOF){
        for (i = 0; i <= n; i++){
            x = 0;
            scanf("%s", str);

            for (j = 0; str[j]; j++) x = (x << 1) + (str[j] - 48);
            temp[i] = x;
        }

        r = n;
        n = 0, k = 0;
        memset(pos, -1, sizeof(pos));

        for (j = 0; j < m; j++){
            if (temp[r] & (1 << j)) pos[j] = k++;
        }

        lim = (1 << k) - 1;
        for (i = 0; i < r; i++){
            x = 0, k = 0;
            for (j = 0; j < m; j++){
                if (temp[i] & (1 << j)){
                    if (pos[j] == -1){
                        k = 1;
                        break;
                    }
                    x |= (1 << pos[j]);
                }
            }
            if (!k) ar[n++] = x ^ lim;
        }

        printf("%d\n", Solve());
    }
    return 0;
}








In Python3 :





[n,m] = list(map(int,input().strip().split()))
alll=[]
p=int(1e9+7)
for _ in range(n):
    s = input().strip()
    alll.append(s)
target = input().strip()
req = []
no = []
for i in range(m):
    if target[i]=='1':
        req.append(i)
    else:
        no.append(i)
filtered = []
for st in alll:
    bo = 1
    for i in no:
        if st[i]=='1':
            bo = 0
            break
    if bo==1:
        filtered.append(st)
new = []
for i in req:
    for st in filtered:
        if st[i]=='0':
            new.append(i)
            break
w = len(new)
#print(req,filtered,new)
count = {i:0 for i in range(1,w+1)}
setcnt = {}
def subst(L):
    ans = [()]
    k = 1
    for itm in L:
        for j in range(k):
            ans.append(ans[j]+(itm,))
        k*=2
    return(ans[1:])


for st in filtered:
    temp = []
    for i in new:
        if st[i]=='0':
            temp.append(i)
    for sett in subst(temp):
        if sett in setcnt:
            setcnt[sett]+=1
        else:
            setcnt[sett]=1
            
#print(setcnt)

#-------------------------------------
for moo in subst(new):
    if moo in setcnt:
        count[len(moo)]+=pow(2,setcnt[moo],p)-1
        count[len(moo)]%=p
#for yt in range(100000000000000000000000000000000):
#    ko =0
#----------------------------
final = pow(2,len(filtered),p)-1
#print(count,final)
for i in range(1,w+1):
    final+=count[i]*pow(-1,i)
    final%=p

print(final)








View More Similar Problems

Tree: Postorder Traversal

Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the

View Solution →

Tree: Inorder Traversal

In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func

View Solution →

Tree: Height of a Binary Tree

The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary

View Solution →

Tree : Top View

Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.

View Solution →

Tree: Level Order Traversal

Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F

View Solution →

Binary Search Tree : Insertion

You are given a pointer to the root of a binary search tree and values to be inserted into the tree. Insert the values into their appropriate position in the binary search tree and return the root of the updated binary tree. You just have to complete the function. Input Format You are given a function, Node * insert (Node * root ,int data) { } Constraints No. of nodes in the tree <

View Solution →