XLK CSP-S 2023 A
给定一个 \(01\) 矩阵 \(a\)。
\(a_{x,y}=1\) 则 \((x, y)\) 有点。
求有多少个大小为 \(4\) 的点集，满足点集中的点刚好为一个正方形的四个顶点。
\(n \le 500\)
发现 \(O(n^3)\) 不好做，直接 bitset 压位，
\(O(\frac{n^4}{w})\) 可以通过。
const int N = 5e2 + 5;
int n, t, a[N][N];
bitset<N> b[N], c[N], d[N], e[N];
int vis[N];
string s;
void solve() {
cin >> n >> t;
if(t == 5) {
cout << 0 << endl;
return;
}
FOR(i, 1, n) {
cin >> s; s = ' ' + s;
FOR(j, 1, n) {
a[i][j] = (s[j] == '1');
b[i][j] = a[i][j];
}
}
ll ans = 0;
FOR(j, 1, n - 1) {
FOR(k, 1, n) {
d[k] = b[k] >> j;
}
FOR(i, 0, n - 1) {
FOR(k, 1, n) {
int u = k - i;
vis[k] = 1;
if(u > 0) c[k] = b[k] & d[u];
else vis[k] = 0;
}
FOR(k, 1, n) {
int u = k - j;
if(u > 0 && vis[u]) ans += (c[k] & (c[u] << i)).count();
}
}
}
cout << ans << endl;
}