Problem:


Score : 100 points

Problem Statement

There are N men and N women, both numbered 1, 2, \ldots, N.

For each i, j (1 \leq i, j \leq N), the compatibility of Man i and Woman j is given as an integer a_{i, j}.
If a_{i, j} = 1, Man i and Woman j are compatible; if a_{i, j} = 0, they are not.

Taro is trying to make N pairs, each consisting of a man and a woman who are compatible.
Here, each man and each woman must belong to exactly one pair.

Find the number of ways in which Taro can make N pairs, modulo 10^9 + 7.

Constraints

All values in input are integers.

1 \leq N \leq 21

a_{i, j} is 0 or 1.

Input

Input is given from Standard Input in the following format:

N
a_{1, 1} \ldots a_{1, N}
:
a_{N, 1} \ldots a_{N, N}

Output

Print the number of ways in which Taro can make N pairs, modulo 10^9 + 7.

Sample Input 1

3
0 1 1
1 0 1
1 1 1

Sample Output 1

3

There are three ways to make pairs, as follows ((i, j) denotes a pair of Man i and Woman j):

(1, 2), (2, 1), (3, 3)

(1, 2), (2, 3), (3, 1)

(1, 3), (2, 1), (3, 2)

Sample Input 2

4
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0

Sample Output 2

1

There is one way to make pairs, as follows:

(1, 2), (2, 4), (3, 1), (4, 3)

Sample Input 3

1
0

Sample Output 3

0

Sample Input 4

21
0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1
1 1 1 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 1 0
0 0 1 1 1 1 0 1 1 0 0 1 0 0 1 1 0 0 0 1 1
0 1 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 0 1 1 0
1 1 0 0 1 0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 1 1 0 1 1 1 0 1 1 1 0 0 0 1 1 1 1 0 0 1
0 1 0 0 0 1 0 1 0 0 0 1 1 1 0 0 1 1 0 1 0
0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1
0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 1 1
0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 1 1 0 0 0 1
0 1 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 1 1 0
0 0 1 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 0 0 1
0 1 1 0 0 1 1 1 1 0 0 0 1 0 1 1 0 1 0 1 1
1 1 1 1 1 0 0 0 0 1 0 0 1 1 0 1 1 1 0 0 1
0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1
1 0 1 1 0 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1
0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1
0 0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0 1 1 0
1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1 0
1 0 0 1 1 0 1 1 1 1 1 0 1 0 1 1 0 0 0 0 0

Sample Output 4

102515160

Be sure to print the number modulo 10^9 + 7.



Sample input:
3
0 1 1
1 0 1
1 1 1


Sample output:
3

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <queue>
#include <cmath>
#include <map>

using namespace std;
long long po(int n) {
	long long ans = 1;
	for (int i = 0;i < n;i++) {
		ans *= 2;
	}
	return ans;
}

long long bac(vector<bool> ju) {
	long long ans = 0;
	long long di = 1;
	for (int i = 0;i < ju.size();i++) {
		if (ju[i]) {
			ans += di;
		}
		di *= 2;
	}
	return ans;
}

void ch(long long n, vector<bool> &ju) {
	for (int i = 0;i < ju.size();i++) {
		ju[i] = n % 2;
		n /= 2;
	}
}

void deb(vector<long long> ar) {
	for (int i = 0;i < ar.size();i++) {
		cout << i << ' ' << ar[i] << endl;
	}
}

int main() {
	int n;
	cin >> n;
	vector<vector<int> > da(n, vector<int>(n));
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			cin >> da[i][j];
		}
	}
	vector<long long> mo(n);
	mo[0] = 1;
	for (int i = 0;i < n - 1;i++) {
		mo[i + 1] = mo[i] * 2;
	}
	int x = po(n);
	vector<long long> dp(x, 0);
	dp[0] = 1;
	for (long long i = 1;i < x;i++) {
		vector<bool> ju(n);
		ch(i, ju);
		int co = -1;
		long long me = 0, gg = 0;
		for (int j = 0;j < n;j++) {
			if (ju[j]) {
				gg += mo[j];
				co++;
			}
		}
		for (int j = 0;j < n;j++) {
			if (ju[j] & da[co][j]) {
				me += dp[gg-mo[j]];
			}
		}
		dp[i] = me % 1000000007;
	}
	cout << dp[x - 1] << endl;
	//deb(dp);
}

Submission status: Runtime Error

Solution code:
range = xrange
input = raw_input
MOD = 10**9+7
 
n = int(input())
 
dp = [0] * (1 << n)
for i in [i for i, x in enumerate(input().split()) if x == '1']:
    dp[1 << i] = 1
 
npow = 1 << n
 
for i in range(n - 1):
    _dp = [0] * npow
    for j in [i for i, x in enumerate(input().split()) if x == '1']:
        jpow = 1 << j
        mask = (npow - 1) ^ jpow
        x = npow
        while x:
          	x -= 1
            x &= mask
            _dp[x + jpow] += dp[x]
    for mask in range(npow):
        _dp[mask] %= MOD
    dp = _dp
 
print(sum(dp) % MOD)

Submission status: Runtime Error

Solution code:
range = xrange
input = raw_input
MOD = 10**9+7
 
n = int(input())
 
dp = [0] * (1 << n)
for i in [i for i, x in enumerate(input().split()) if x == '1']:
    dp[1 << i] = 1
 
npow = 1 << n
 
for i in range(n - 1):
    _dp = [0] * npow
    for j in [i for i, x in enumerate(input().split()) if x == '1']:
        jpow = 1 << j
        mask = (npow - 1) ^ jpow
        x = npow
        while x:
            x = (x-1)&m
            _dp[x + jpow] += dp[x]
    for mask in range(npow):
        _dp[mask] %= MOD
    dp = _dp
 
print(sum(dp) % MOD)

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())

    dp = [0] * (1 << n)
    for i in [i >> 1 for i, x in enumerate(input()) if x == '1']:
        dp[1 << i] = 1

    npow = 1 << n

    for i in range(n - 1):
        _dp = [0] * npow
        for j in [i >> 1 for i, x in enumerate(input()) if x == '1']:
            jpow = 1 << j
            for mask,val in enumerate(dp):
                if not mask & jpow:
                    _dp[mask + jpow] += val
        for mask in range(npow):
            _dp[mask] %= MOD
        dp = _dp

    print(sum(dp) % MOD)

main()

Submission status: Runtime Error

Solution code:
def main():
  MOD = 1000000007
  n = int(input())
  match = [list(map(int, input().split())) for _ in range(n)]
  
  dic = {}
  def dp(stat, index):
    if index == n:return 1
    if stat in dic:
      return dic[stat]
  
    ret = 0
    mask = 1
    match_index = match[index]
    for i in range(n):
      if mask & stat or not match_inedx[i]:
        mask <<= 1
        continue
      ret += dp(stat | mask, index + 1)
      mask <<= 1
    ret %= MOD
    dic[stat] = ret
    return ret
  
  print(dp(0, 0))
  
main()