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.  
  13. // Đây là một bài kinh điển của bitset
  14. // Còn có tên gọi là đếm số tam giác hay đếm số chu trình độ dài 3 có trong đồ thị vô hướng
  15. // Với mỗi cạnh (i, j), ta cần đếm số lượng đỉnh k thoả mãn tồn tại cạnh (i, k) và cạnh (j, k)
  16. // Thuật trâu: O(n^3) / O(m * n)
  17. // => Tối ưu bằng bitset, với mỗi đỉnh i ta có bs[i] là bitset đại diện cho tập đỉnh kề với i
  18. // bs[i][j] = 1 nếu tồn tại cạnh (i, j),
  19. // = 0, trong trường hợp ngược lại
  20. // => Với mỗi cạnh (i, j) thì tập đỉnh k cần tìm chính là phần giao giữa bs[i] và bs[j]
  21. // => O(n^3 / 64) / O(m * n / 64)
  22. int n;
  23. bitset<N> bs[N];
  24.  
  25. int main() {
  26. ios::sync_with_stdio(false);
  27. cin.tie(nullptr);
  28. cin >> n;
  29. for (int i = 0; i < n; i++) {
  30. string s; cin >> s;
  31. for (int j = 0; j < n; j++) {
  32. bs[i][j] = s[j] - '0';
  33. }
  34. }
  35.  
  36. ll ans = 0;
  37. for (int i = 0; i + 1 < n; i++) {
  38. for (int j = i + 1; j < n; j++) {
  39. if (bs[i][j]) {
  40. ans += (bs[i] & bs[j]).count();
  41. }
  42. }
  43. }
  44. ans /= 3; // Theo cách đếm này thì mỗi bộ (i, j, k) thoả mãn bị đếm lặp 3 lần
  45.  
  46. cout << ans << '\n';
  47. }
Success #stdin #stdout 0.01s 5280KB
stdin
4
0011
0011
1101
1110
stdout
2