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;
}