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

Fibonacci Numbers Tree

Shashank loves trees and math. He has a rooted tree, T , consisting of N nodes uniquely labeled with integers in the inclusive range [1 , N ]. The node labeled as 1 is the root node of tree , and each node in is associated with some positive integer value (all values are initially ). Let's define Fk as the Kth Fibonacci number. Shashank wants to perform 22 types of operations over his tree, T

View Solution →

Pair Sums

Given an array, we define its value to be the value obtained by following these instructions: Write down all pairs of numbers from this array. Compute the product of each pair. Find the sum of all the products. For example, for a given array, for a given array [7,2 ,-1 ,2 ] Note that ( 7 , 2 ) is listed twice, one for each occurrence of 2. Given an array of integers, find the largest v

View Solution →

Lazy White Falcon

White Falcon just solved the data structure problem below using heavy-light decomposition. Can you help her find a new solution that doesn't require implementing any fancy techniques? There are 2 types of query operations that can be performed on a tree: 1 u x: Assign x as the value of node u. 2 u v: Print the sum of the node values in the unique path from node u to node v. Given a tree wi

View Solution →

Ticket to Ride

Simon received the board game Ticket to Ride as a birthday present. After playing it with his friends, he decides to come up with a strategy for the game. There are n cities on the map and n - 1 road plans. Each road plan consists of the following: Two cities which can be directly connected by a road. The length of the proposed road. The entire road plan is designed in such a way that if o

View Solution →

Heavy Light White Falcon

Our lazy white falcon finally decided to learn heavy-light decomposition. Her teacher gave an assignment for her to practice this new technique. Please help her by solving this problem. You are given a tree with N nodes and each node's value is initially 0. The problem asks you to operate the following two types of queries: "1 u x" assign x to the value of the node . "2 u v" print the maxim

View Solution →

Number Game on a Tree

Andy and Lily love playing games with numbers and trees. Today they have a tree consisting of n nodes and n -1 edges. Each edge i has an integer weight, wi. Before the game starts, Andy chooses an unordered pair of distinct nodes, ( u , v ), and uses all the edge weights present on the unique path from node u to node v to construct a list of numbers. For example, in the diagram below, Andy

View Solution →