Submission #3981461


Source Code Expand

Copy
#include <bits/stdc++.h>

using namespace std;

const int N = 22, M = (1<<22), MOD = 1e9 + 7;
int dp[N][M], n, a[N][N];

inline int add(int a, int b){
	a += b;
	if(a >= MOD)a -= MOD;
	return a;
}

inline int sub(int a, int b){
	a -= b;
	if(a < 0)a += MOD;
	return a;
}

int find(int id, int mask){
	if(id < 0)return mask == 0;
	if(dp[id][mask] != -1)return dp[id][mask];

	dp[id][mask] = 0;
	for(int i=0;i<n;++i)if((mask & (1<<i)) && a[id][i])
		dp[id][mask] = add(dp[id][mask], find(id - 1, mask ^ (1<<i)));

	return dp[id][mask];
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin>>n;
	for(int i=0;i<n;++i)
		for(int j=0;j<n;++j)cin>>a[i][j];

	for(int i=0;i<n;++i)
		for(int mask=0;mask < (1<<n); ++mask)
			dp[i][mask] = -1;

	cout<<find(n - 1, (1<<n) - 1)<<"\n";
	return 0;
}

Submission Info

Submission Time
Task O - Matching
User revivedDevil
Language C++14 (GCC 5.4.1)
Score 100
Code Size 851 Byte
Status
Exec Time 357 ms
Memory 213248 KB

Test Cases

Set Name Score / Max Score Test Cases
All 100 / 100 0_00, 0_01, 0_02, 0_03, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12
Case Name Status Exec Time Memory
0_00 2 ms 4352 KB
0_01 2 ms 6400 KB
0_02 1 ms 256 KB
0_03 339 ms 213248 KB
1_00 1 ms 256 KB
1_01 1 ms 256 KB
1_02 60 ms 213248 KB
1_03 60 ms 213248 KB
1_04 76 ms 213248 KB
1_05 239 ms 213248 KB
1_06 252 ms 213248 KB
1_07 308 ms 213248 KB
1_08 316 ms 213248 KB
1_09 336 ms 213248 KB
1_10 325 ms 213248 KB
1_11 338 ms 213248 KB
1_12 357 ms 213248 KB