p448.ans1
======================
1

=================
p448.ans10
======================
78

=================
p448.ans11
======================
1

=================
p448.ans12
======================
6

=================
p448.ans13
======================
495725

=================
p448.ans14
======================
3683673

=================
p448.ans2
======================
0

=================
p448.ans3
======================
0

=================
p448.ans4
======================
3

=================
p448.ans5
======================
0

=================
p448.ans6
======================
1

=================
p448.ans7
======================
0

=================
p448.ans8
======================
11

=================
p448.ans9
======================
139

=================
p448.cpp
======================
#include <bits/stdc++.h>

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("tree-vectorize")

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, m;
vector<vector<int>> R;

void multiply_add(
    vector<uint64_t>& result, const vector<uint64_t>& a,
    const vector<uint64_t>& b
) {
    const size_t size = a.size();
    const size_t chunk_size = 4;
    const size_t chunk_end = size - (size % chunk_size);

    for(size_t i = 0; i < chunk_end; i += chunk_size) {
        result[i] += a[i] * b[i];
        result[i + 1] += a[i + 1] * b[i + 1];
        result[i + 2] += a[i + 2] * b[i + 2];
        result[i + 3] += a[i + 3] * b[i + 3];
    }

    for(size_t i = chunk_end; i < size; i++) {
        result[i] += a[i] * b[i];
    }
}

void read() {
    cin >> n >> m;
    m--;
    R.resize(n, vector<int>(n));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> R[i][j];
        }
    }
}

void xor_transform(vector<uint64_t>& a, bool reverse = false) {
    int n = a.size();
    for(int i = 1; i < n; i <<= 1) {
        for(int j = 0; j < n; j += (i << 1)) {
            for(int k = 0; k < i; k++) {
                uint64_t x = a[j + k];
                uint64_t y = a[j + k + i];
                a[j + k] = x + y;
                a[j + k + i] = x - y;
            }
        }
    }

    if(reverse) {
        for(int i = 0; i < n; i++) {
            a[i] /= n;
        }
    }
}

void solve() {
    // We count minimal-height knockout tournaments in which player m wins. A
    // tournament is built by merging two disjoint sub-brackets: the winners of
    // two sub-tournaments over disjoint sets of players play, and the match
    // result R decides who advances. The bracket height must be minimal, which
    // means a sub-bracket over s players needs exactly ceil(log2(s)) rounds;
    // best_size[s-1] is that minimum number of merge rounds.
    //
    // The DP state is dp[step][winner][size][mask]: the number of ways to form
    // a sub-bracket of the given size and round count whose champion is
    // `winner` and whose participant set is `mask`. Merging two sub-brackets
    // requires their masks to be disjoint and their union to be tracked, which
    // is an XOR (subset) convolution over the participant bitmask.
    //
    // To make the convolution cheap we keep every dp[...] array in the
    // Walsh-Hadamard transformed domain over the n-bit mask space. There,
    // combining two sub-brackets is just pointwise multiplication
    // (multiply_add accumulates a[i] * b[i] for the winner determined by R).
    // Leaves dp[0][i][1] start as a single-player bracket for player i (the
    // indicator of mask {i}), transformed once. We iterate sub-bracket size
    // pairs in increasing max-size order so all inputs are ready, only allowing
    // round counts that keep the final tree at minimal height. Finally we
    // inverse-transform dp[steps-1][m][n] and read off the coefficient for the
    // full participant set (1 << n) - 1.

    vector<int> best_size(n + 1, 0);
    for(int i = 1; i <= n; i++) {
        best_size[i] = best_size[i >> 1] + 1;
    }

    int steps = best_size[n - 1] + 1;
    vector<vector<vector<vector<uint64_t>>>> dp(
        steps, vector<vector<vector<uint64_t>>>(
                   n, vector<vector<uint64_t>>(n + 1, vector<uint64_t>())
               )
    );

    for(int i = 0; i < n; i++) {
        dp[0][i][1].assign(1 << n, 0);
        dp[0][i][1][1 << i] = 1;
        xor_transform(dp[0][i][1]);
    }

    vector<pair<int, int>> sz_a_b;
    for(int sz_a = 1; sz_a <= n; sz_a++) {
        for(int sz_b = 1; sz_b <= n; sz_b++) {
            if(sz_a + sz_b > n) {
                continue;
            }
            sz_a_b.emplace_back(sz_a, sz_b);
        }
    }

    sort(sz_a_b.begin(), sz_a_b.end(), [](const auto& a, const auto& b) {
        return max(a.first, a.second) < max(b.first, b.second);
    });

    for(auto [sz_a, sz_b]: sz_a_b) {
        for(int step_a = 0; step_a + 1 < steps; step_a++) {
            if(step_a < best_size[sz_a - 1]) {
                continue;
            }
            for(int step_b = 0; step_b + 1 < steps; step_b++) {
                if(step_b < best_size[sz_b - 1]) {
                    continue;
                }
                for(int x = 0; x < n; x++) {
                    for(int y = x + 1; y < n; y++) {
                        int winner = R[x][y] ? x : y;
                        int new_step = max(step_a, step_b) + 1;
                        auto& dp_a = dp[step_a][x][sz_a];
                        auto& dp_b = dp[step_b][y][sz_b];
                        auto& dp_winner = dp[new_step][winner][sz_a + sz_b];

                        if(dp_a.empty() || dp_b.empty()) {
                            continue;
                        }

                        int left = n - sz_a - sz_b;
                        int left_steps = steps - new_step - 1;
                        if(left != 0 && left_steps == 0) {
                            continue;
                        }

                        if(dp_winner.empty()) {
                            dp_winner.assign(1 << n, 0);
                        }

                        multiply_add(
                            dp[new_step][winner][sz_a + sz_b],
                            dp[step_a][x][sz_a], dp[step_b][y][sz_b]
                        );
                    }
                }
            }
        }
    }

    if(dp[steps - 1][m][n].empty()) {
        cout << 0 << '\n';
        return;
    }
    xor_transform(dp[steps - 1][m][n], true);
    cout << dp[steps - 1][m][n][(1 << n) - 1] << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p448.in1
======================
2 1
0 1
0 0

=================
p448.in10
======================
8 6
0 0 0 0 1 0 0 0
1 0 1 1 0 0 0 0
1 0 0 0 1 0 0 0
1 0 1 0 0 1 0 1
0 1 0 1 0 0 1 0
1 1 1 0 1 0 0 1
1 1 1 1 0 1 0 0
1 1 1 0 1 0 1 0

=================
p448.in11
======================
1 1
0

=================
p448.in12
======================
5 3
0 0 1 0 1
1 0 1 0 1
0 0 0 1 1
1 1 0 0 1
0 0 0 0 0

=================
p448.in13
======================
13 8
0 0 1 1 1 0 0 1 1 0 1 0 1
1 0 0 1 0 0 0 0 1 0 0 1 0
0 1 0 1 1 1 0 1 0 1 1 0 1
0 0 0 0 1 1 1 0 0 1 1 0 0
0 1 0 0 0 0 0 1 0 0 1 0 0
1 1 0 0 1 0 1 0 1 0 0 0 0
1 1 1 0 1 0 0 0 1 0 1 0 0
0 1 0 1 0 1 1 0 0 0 0 0 1
0 0 1 1 1 0 0 1 0 1 1 1 1
1 1 0 0 1 1 1 1 0 0 1 0 1
0 1 0 0 0 1 0 1 0 0 0 0 1
1 0 1 1 1 1 1 1 0 1 1 0 1
0 1 0 1 1 1 1 0 0 0 0 0 0

=================
p448.in14
======================
12 4
0 1 1 1 0 1 1 0 0 1 0 0
0 0 1 0 0 1 0 1 1 1 0 1
0 0 0 0 1 0 1 0 1 0 1 1
0 1 1 0 1 1 1 1 0 0 1 0
1 1 0 0 0 0 1 1 0 1 1 1
0 0 1 0 1 0 0 1 0 0 1 1
0 1 0 0 0 1 0 1 1 1 0 1
1 0 1 0 0 0 0 0 0 0 0 0
1 0 0 1 1 1 0 1 0 0 1 1
0 0 1 1 0 1 0 1 1 0 0 1
1 1 0 0 0 0 1 1 0 1 0 0
1 0 0 1 0 0 0 1 0 0 1 0

=================
p448.in2
======================
2 1
0 0
1 0

=================
p448.in3
======================
3 3
0 1 1
0 0 1
0 0 0

=================
p448.in4
======================
3 3
0 1 0
0 0 0
1 1 0

=================
p448.in5
======================
3 1
0 1 0
0 0 0
1 1 0

=================
p448.in6
======================
3 3
0 1 0
0 0 1
1 0 0

=================
p448.in7
======================
4 1
0 0 0 1
1 0 0 1
1 1 0 0
0 0 1 0

=================
p448.in8
======================
6 4
0 0 0 0 0 1
1 0 1 0 1 0
1 0 0 1 1 0
1 1 0 0 1 0
1 0 0 0 0 0
0 1 1 1 1 0

=================
p448.in9
======================
7 2
0 1 0 0 0 1 0
0 0 1 0 1 1 1
1 0 0 1 1 0 0
1 1 0 0 0 1 0
1 0 0 1 0 0 1
0 0 1 0 1 0 0
1 0 1 1 0 1 0

=================
statement.txt
======================
448. Controlled Tournament
Time limit per test: 1 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

National Association of Tennis is planning to hold a tennis competition among professional players. The competition is going to be a knockout tournament, and you are assigned the task to make the arrangement of players in the tournament. You are given the detailed report about all participants of the competition. The report contains the results of recent matches between all pairs of the participants. Examining the data, you've noticed that it is only up to the opponent whether one player wins or not. Since one of your special friends are attending the competition, you want him to get the best prize. So you want to know the possibility where he wins the gold medal. However it is not so easy to figure out because there are many participants. You have decided to write a program which calculates the number of possible arrangements of tournament in which your friend wins the gold medal. In order to make your trick hidden from everyone, you need to avoid making a factitive tournament tree. So you have to consider only such tournaments that the height of your tournament tree is minimal possible.
Input
The input has the format as described below.
N M
R11 R12... R1N
R21 R22... R2N
...
RN1 RN2... RNN
N is the number of players (1 ≤ N ≤ 16), and M is your friend's ID (numbered from 1). Rij is the result of a match between the i-th player and the j-th player. When i-th player always wins, Rij = 1. Otherwise, Rij = 0. It is guaranteed that the matrix is consistent: for all i != j, Rij = 0 if and only if Rji = 1. The diagonal elements Rii are just given for convenience and are always 0.
Output
Your program should output in a line the number of possible tournaments in which your friend wins the first prize.
Example(s)
sample input
sample output
2 1
0 1
0 0
1

sample input
sample output
2 1
0 0
1 0
0

sample input
sample output
3 3
0 1 1
0 0 1
0 0 0
0

sample input
sample output
3 3
0 1 0
0 0 0
1 1 0
3

sample input
sample output
3 1
0 1 0
0 0 0
1 1 0
0

sample input
sample output
3 3
0 1 0
0 0 1
1 0 0
1

sample input
sample output
4 1
0 0 0 1
1 0 0 1
1 1 0 0
0 0 1 0
0

sample input
sample output
6 4
0 0 0 0 0 1
1 0 1 0 1 0
1 0 0 1 1 0
1 1 0 0 1 0
1 0 0 0 0 0
0 1 1 1 1 0
11

sample input
sample output
7 2
0 1 0 0 0 1 0
0 0 1 0 1 1 1
1 0 0 1 1 0 0
1 1 0 0 0 1 0
1 0 0 1 0 0 1
0 0 1 0 1 0 0
1 0 1 1 0 1 0
139

sample input
sample output
8 6
0 0 0 0 1 0 0 0
1 0 1 1 0 0 0 0
1 0 0 0 1 0 0 0
1 0 1 0 0 1 0 1
0 1 0 1 0 0 1 0
1 1 1 0 1 0 0 1
1 1 1 1 0 1 0 0
1 1 1 0 1 0 1 0
78

=================
