fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using i64 = int_fast64_t;
  5.  
  6. bool adj[18][18];
  7.  
  8. i64 dp[1<<18][18];
  9. i64 lenCnt[19][1<<18];
  10.  
  11. // length = 2^N
  12. template <typename T> void subset_transform(int N, T a[1<<18]) {
  13. for (int k = 1; k < (1<<N); k *= 2) {
  14. for (int i = 0; i < (1<<N); i += 2*k) {
  15. for (int j = 0; j < k; j++) {
  16. a[i+j+k] += a[i+j];
  17. }
  18. }
  19. }
  20. }
  21.  
  22. template <typename T> void inverse_superset_transform(int N, T a[1<<18]) {
  23. for (int k = 1; k < (1<<N); k *= 2) {
  24. for (int i = 0; i < (1<<N); i += 2*k) {
  25. for (int j = 0; j < k; j++) {
  26. a[i+j] -= a[i+j+k];
  27. }
  28. }
  29. }
  30. }
  31.  
  32. i64 ans[1<<17];
  33.  
  34. int main() {
  35. ios::sync_with_stdio(0), cin.tie(0);
  36. int N; cin >> N;
  37. for (int i = 0; i < N; i++) {
  38. string s; cin >> s;
  39. for (int j = 0; j < N; j++) {
  40. adj[i][j] = s[j] - '0';
  41. }
  42. }
  43.  
  44. for (int i = 0; i < N; i++) {
  45. dp[1<<i][i] = 1;
  46. }
  47. for (int m = 1; m < (1<<N); m++) {
  48. for (int i = 0; i < N; i++) {
  49. if (!(m & (1<<i))) continue;
  50. for (int j = 0; j < N; j++) {
  51. if (m & (1<<j)) continue;
  52. if (adj[i][j]) {
  53. dp[m | (1<<j)][j] += dp[m][i];
  54. }
  55. }
  56. }
  57. }
  58.  
  59. for (int m = 1; m < (1<<N); m++) {
  60. int pc = __builtin_popcount(m);
  61. for (int i = 0; i < N; i++) {
  62. lenCnt[pc][m] += dp[m][i];
  63. }
  64. }
  65. for (int l = 1; l <= N; l++) {
  66. subset_transform(N, lenCnt[l]);
  67. }
  68.  
  69. map<vector<int>, i64> memo;
  70. for (int p = 0; p < (1<<(N-1)); p++) {
  71. int cnt = 0;
  72. vector<int> partition;
  73. for (int i = 0; i < N; i++) {
  74. cnt++;
  75. if (!(p & (1<<i))) {
  76. partition.push_back(cnt);
  77. cnt = 0;
  78. }
  79. }
  80. sort(partition.begin(), partition.end());
  81.  
  82. if (!memo.count(partition)) {
  83. i64 res = 0;
  84. for (int m = 1; m < (1<<N); m++) {
  85. i64 v = 1;
  86. for (int l : partition) {
  87. v *= lenCnt[l][m];
  88. }
  89. if ((N - __builtin_popcount(m)) % 2 == 0) {
  90. res += v;
  91. } else {
  92. res -= v;
  93. }
  94. }
  95. memo[partition] = res;
  96. }
  97. ans[p] = memo[partition];
  98. }
  99.  
  100. inverse_superset_transform(N-1, ans);
  101. for (int p = 0; p < (1<<(N-1)); p++) { cout << ans[p] << " \n"[p==(1<<(N-1))-1]; }
  102.  
  103. return 0;
  104. }
  105.  
Success #stdin #stdout 0s 4404KB
stdin
4
0101
1000
0001
1010
stdout
2 2 6 2 2 6 2 2