JYPnation

Due to the success of TWICE, JYP Entertainment has earned countless money and emerged as the biggest entertainment firm by market capitalization. Therefore, the boss, JYP, has decided to create a new nation and has appointed you to provide a design diagram.

The new nation consists of $n$ cities and some roads between them. JYP has given some restrictions:

• To guarantee efficiency while avoiding chaos, for any $2$ different cities $A$ and $B$, there is exactly one road between them, and it is one-directional. There are no roads connecting a city to itself.
• The logo of rivaling companies should not appear in the plan, that is, there does not exist $4$ distinct cities $A$,$B$,$C$,$D$ , such that the following configuration occurs.

JYP has given criteria for your diagram. For two cities $A$,$B$, let $dis(A,B)$ be the smallest number of roads you have to go through to get from $A$ to $B$. If it is not possible to walk from $A$ to $B$, $dis(A,B) = 614n$. Then, the efficiency value is defined to be the sum of $dis(A,B)$ for all ordered pairs of distinct cities $(A,B)$.

Note that $dis(A,B)$ doesn’t have to be equal to $dis(B,A)$.

You have drawn a design diagram that satisfies JYP’s restrictions. Find the sum of $dis(A,B)$ over all ordered pairs of cities $(A,B)$ with $A\neq B$.

Note that the input is given in compressed form. But even though it is compressed, you’d better use fast input.Input

The first line contains a single integer $n$ ($4 \le n \le 8000$, $n \equiv 0 \pmod{4}$) — the number of cities.

A binary matrix is encrypted in the following format. Each of $n$ next lines contains $\frac{n}{4}$ one-digit hexadecimal numbers (that is, these numbers can be represented either as digits from $0$ to $9$ or as uppercase Latin letters from $A$ to $F$). Binary representation of each of these numbers denotes next $4$ elements of the matrix in the corresponding row. For example, if the number $B$ is given, then the corresponding elements are $1011$, and if the number is $5$, then the corresponding elements are $0101$.

After you obtain the decrypted binary matrix, the $j$-th character of the $i$-th row is $1$ if the one-directional road between cities $i$ and $j$ is directed from $i$ to $j$, and $0$ otherwise. It is guaranteed that the graph satisfies the restrictions mentioned above.Output

Output one integer, representing the sum of $dis(A,B)$ over all ordered pairs of cities $(A,B)$ with $A\neq B$.Examplesinput

4
7
2
1
4

output

7380

input

8
7F
3F
1F
0C
06
03
11
18

output

88464

Note

The first example corresponds to the matrix:

$\begin{matrix} 0111 \\ 0010 \\ 0001 \\ 0100 \\ \end{matrix}$

Which corresponds to this graph:

$dis(1,2)=dis(1,3)=dis(1,4)=dis(2,3)=dis(3,4)=dis(4,2)=1$

$dis(2,4)=dis(4,3)=dis(3,2)=2$

$dis(2,1)=dis(3,1)=dis(4,1)=2456$

Therefore the answer for the diagram is $7380$.

Solution:

#include <bits/stdc++.h>

using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
return '"' + s + '"';
}

string to_string(const char* s) {
return to_string((string) s);
}

string to_string(bool b) {
return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
bool first = true;
string res = "{";
for (int i = 0; i < static_cast<int>(v.size()); i++) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(v[i]);
}
res += "}";
return res;
}

template <size_t N>
string to_string(bitset<N> v) {
string res = "";
for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
}
return res;
}

template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
vector<vector<bool>> g(n, vector<bool>(n, false));
vector<int> din(n, 0);
vector<int> dout(n, 0);
for (int i = 0; i < n; i++) {
    string foo;
    cin >> foo;
for (int j = 0; j < (n >> 2); j++) {
char c = foo[j];
int d = (c <= '9' ? (int) (c - '0') : (int) (c - 'A' + 10));
      for (int k = 0; k < 4; k++) {
        if (d & (1 << (3 - k))) {
          int x = (j << 2) | k;
          g[i][x] = true;
          dout[i] += 1;
          din[x] += 1;
        }
      }
    }
  }
  const long long none = 614LL * n;
  long long ans = 0;
  vector<bool> alive(n, true);
for (int rm = n; rm >= 1; rm--) {
bool found = false;
for (int i = 0; i < n; i++) {
      if (alive[i] && dout[i] == rm - 1) {
        alive[i] = false;
        ans += (1 + none) * (rm - 1);
        found = true;
        break;
      }
    }
    if (!found) {
      vector<int> all;
for (int i = 0; i < n; i++) {
        if (alive[i]) {
          all.push_back(i);
        }
      }
      debug(all);
      assert((int) all.size() == rm);
      vector<int> used(n, 0);
vector<int> seq(1, all[0]);
used[seq[0]] += 1;
vector<int> add;
vector<bool> in_seq(n, false);
in_seq[seq[0]] = true;
for (int it = 0; it < rm; it++) {
        assert(it < (int) seq.size());
        int v = seq[it];
        in_seq[v] = false;
        add.clear();
        for (int j = 0; j < n; j++) {
          if (v != j && !in_seq[j] && alive[j] && !g[v][j]) {
            assert(used[j] < 2);
            used[j] += 1;
            add.push_back(j);
          }
        }
        sort(add.begin(), add.end(), [&](int i, int j) {
          return g[j][i];
        });
        for (int u : add) {
          seq.push_back(u);
          in_seq[u] = true;
        }
      }
      seq.resize(rm);
      reverse(seq.begin(), seq.end());
      for (int i = 0; i < rm; i++) {
        int cc = 0;
        while (cc < rm - 1) {
          ans += rm - 1 - cc;
          cc += dout[seq[(i + cc) % rm]];
        }
      }
      break;
    }
  }
  cout << ans << '\n';
  return 0;
}