fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7.  
  8. const int INF = 1e9;
  9. const ll LINF = 1e18;
  10.  
  11. const int N = 3e3 + 5;
  12. const int B = 63;
  13. const int K = 48;
  14.  
  15. int n;
  16. ll mask[N][K];
  17.  
  18. int nC2(int n) {
  19. if (n < 2) return 0;
  20. return n * (n - 1) / 2;
  21. }
  22.  
  23. int main() {
  24. ios::sync_with_stdio(false);
  25. cin.tie(nullptr);
  26. cin >> n;
  27. for (int x = 0; x < n; x++) {
  28. string s; cin >> s;
  29. for (int y = 0; y < n; y++) {
  30. int bit_idx = y % B;
  31. mask[x][y / B] |= (1ll << bit_idx) * (s[y] - '0');
  32. }
  33. }
  34.  
  35. // Giả sử x1, x2 (x1 < x2) là 2 hàng rìa của bảng cần đếm
  36. ll ans = 0;
  37. for (int x1 = 0; x1 + 1 < n; x1++) {
  38. for (int x2 = x1 + 1; x2 < n; x2++) {
  39. int cnt = 0; // Số vị trí cùng bằng 1 của 2 hàng x1, x2
  40. for (int cid = 0; cid < K; cid++) {
  41. cnt += __builtin_popcountll(mask[x1][cid] & mask[x2][cid]);
  42. }
  43. ans += nC2(cnt);
  44. }
  45. }
  46.  
  47. cout << ans << '\n';
  48. }
Success #stdin #stdout 0.01s 5280KB
stdin
5
00010
11111
00110
11001
00010
stdout
4