Submission #3977728

Source Code Expand

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

using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

#define MAXN 2097153
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define se second 
#define FAIL0 {printf("0\n"); return 0;}
#define FAIL_1 {printf("-1\n"); return 0;}

int N;
int A[22][22];
LL dp[MAXN];

void add(LL &a, LL b) {
    a = (a+b) % MOD;
}

int nbit(int n) {
    int r = 0;
    while(n) {
        r += n%2;
        n /= 2;
    }

    return r;
}

int main(int argc, char **argv)
{
#ifdef OJ
    freopen("input.txt", "rt", stdin);
    //freopen("output.txt", "wt", stdout);
#endif

    scanf("%d", &N);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            scanf("%d", &A[i][j]);

    LL ans = 0;
    for (int i = 1; i < (1<<N); i++) {
        int nb = nbit(i)-1;
        if (!nb) {
            for (int b = 0; b < N; b++)
                if (A[0][b] && (i & (1<<b))) {
                    dp[i] = 1;
                }
        } else {
            for (int b = 0; b < N; b++) {
                if (i & (1<<b) && A[nb][b]) {
                    add(dp[i], dp[i^(1<<b)]);
                }
            }

            if (nb+1 == N) 
                add(ans, dp[i]);
        }

        //printf("%d %lld\n", i, dp[i]);
    }

    printf("%lld\n", ans);
    return 0;
}

Submission Info

Submission Time
Task O - Matching
User tuananh
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1408 Byte
Status
Exec Time 245 ms
Memory 16640 KB

Compile Error

./Main.cpp: In function ‘int main(int, char**)’:
./Main.cpp:41:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
                    ^
./Main.cpp:44:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &A[i][j]);
                                  ^

Test Cases

Set Name Score / Max Score Test Cases
All 0 / 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 1 ms 256 KB
0_01 1 ms 256 KB
0_02 1 ms 256 KB
0_03 219 ms 16640 KB
1_00 1 ms 256 KB
1_01 1 ms 256 KB
1_02 176 ms 256 KB
1_03 185 ms 16640 KB
1_04 190 ms 16640 KB
1_05 197 ms 16640 KB
1_06 213 ms 16640 KB
1_07 210 ms 16640 KB
1_08 236 ms 16640 KB
1_09 238 ms 16640 KB
1_10 243 ms 16640 KB
1_11 240 ms 16640 KB
1_12 245 ms 16640 KB