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

Array Manipulation

Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array. Example: n=10 queries=[[1,5,3], [4,8,7], [6,9,1]] Queries are interpreted as follows: a b k 1 5 3 4 8 7 6 9 1 Add the valu

View Solution →

Print the Elements of a Linked List

This is an to practice traversing a linked list. Given a pointer to the head node of a linked list, print each node's data element, one per line. If the head pointer is null (indicating the list is empty), there is nothing to print. Function Description: Complete the printLinkedList function in the editor below. printLinkedList has the following parameter(s): 1.SinglyLinkedListNode

View Solution →

Insert a Node at the Tail of a Linked List

You are given the pointer to the head node of a linked list and an integer to add to the list. Create a new node with the given integer. Insert this node at the tail of the linked list and return the head node of the linked list formed after inserting this new node. The given head pointer may be null, meaning that the initial list is empty. Input Format: You have to complete the SinglyLink

View Solution →

Insert a Node at the head of a Linked List

Given a pointer to the head of a linked list, insert a new node before the head. The next value in the new node should point to head and the data value should be replaced with a given value. Return a reference to the new head of the list. The head pointer given may be null meaning that the initial list is empty. Function Description: Complete the function insertNodeAtHead in the editor below

View Solution →

Insert a node at a specific position in a linked list

Given the pointer to the head node of a linked list and an integer to insert at a certain position, create a new node with the given integer as its data attribute, insert this node at the desired position and return the head node. A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is e

View Solution →

Delete a Node

Delete the node at a given position in a linked list and return a reference to the head node. The head is at position 0. The list may be empty after you delete the node. In that case, return a null value. Example: list=0->1->2->3 position=2 After removing the node at position 2, list'= 0->1->-3. Function Description: Complete the deleteNode function in the editor below. deleteNo

View Solution →