cf1338e

https://codeforces.com/contest/1338/problem/E

https://codeforces.com/blog/entry/75913

https://yhx-12243.github.io/OI-transit/records/cf1338E.html

官方题解最后的观察没有看懂，前面的lemma看懂了。

后来发现其实看鱼大题解就好了。

最后再来复述一下一般竞赛图的性质吧：

$1.$竞赛图可以缩点成一条长的单向链，$v_1,v_2..v_n$，其中$v_i$里的点向$v_j$里的点右边当且仅当$i<j$。

$2.$如果一个 $n$ 阶竞赛图 $G$ 是强连通的，则对于任意$3≤k≤n$，$G$ 中存在大小为 $k$ 的圈。

$3.$强连通竞赛图中任意两点的距离不超过$3$。

这些观察都好神仙！！！

#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 1e9 + 7;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const int N = 8005;
int n;
char s[N];
int low[N], belong[N], dfn[N], sz[N], f[N], scc, cnt;
bool g[N][N], inst[N];
vector<int> st;
//
void tarjan(int x) {
  dfn[x] = low[x] = ++cnt; inst[x] = true;
  st.emplace_back(x);
  rep(y, n) if (g[x][y]) {
    if (!dfn[y]) tarjan(y), low[x] = min(low[x], low[y]);
    else if (inst[y]) low[x] = min(low[x], dfn[y]);
  }
  if (low[x] == dfn[x]) {
    ++scc;
    while (st.back() != x) {
      belong[st.back()] = scc; ++sz[scc]; 
      inst[st.back()] = false;
      st.pop_back();
    }
    belong[x] = scc; ++sz[scc];
    inst[st.back()] = false;
    st.pop_back();
  }
}
int main() {
  n = getint(); int inf = 614 * n;
  rep(i, n) {
    scanf("%s", s);
    for (int j = 0, p = 0; j < n; j += 4, ++p) {
      int x = isdigit(s[p]) ? s[p] - '0' : s[p] - 'A' + 10;
      rep(y, 4) g[i][j + 3 - y] = (x >> y & 1);
    }
  }
  rep(i, n) if (!dfn[i]) tarjan(i);
  int tot = sz[1];
  ll res = 1ll * (n - tot) * (n + tot - 1) / 2 * (inf + 1);
  vector<int> a;
  rep(i, n) if (belong[i] == 1) a.emplace_back(i);
  for (int &x : a) {
    f[x] = -1;
    rep(j, n) if (g[x][j] && (f[x] == -1 || g[f[x]][j])) {
      f[x] = j;
    }
  }
  int k1 = tot * (tot - 1) / 2, k2 = 0, k3 = 0;
  for (int &x : a) for (int &y : a) if (x != y) {
    k2 += g[y][x] && f[x] >= 0 && g[f[x]][y];
  }
  k3 = k1 - k2;
  printf("%lld\n", res + k1 + 2ll * k2 + 3ll * k3);
  return 0;
}