fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <numeric>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. long long count_ones(long long n, int j) {
  10.     long long cycle = 1LL << (j + 1);
  11.     long long half = 1LL << j;
  12.     long long res = (n / cycle) * half;
  13.     long long rem = n % cycle;
  14.     if (rem >= half) {
  15.         res += rem - half + 1;
  16.     }
  17.     return res;
  18. }
  19.  
  20. void solve() {
  21.     int n;
  22.     if (!(cin >> n)) return;
  23.     int k = 0;
  24.     while ((1LL << k) <= n) k++;
  25.  
  26.     vector<string> S(k);
  27.     for (int i = 0; i < k; ++i) {
  28.         cin >> S[i];
  29.     }
  30.  
  31.     vector<int> R_req(k);
  32.     for (int j = 0; j < k; ++j) {
  33.         R_req[j] = count_ones(n, j);
  34.     }
  35.  
  36.     vector<int> C_cnt(k);
  37.     for (int i = 0; i < k; ++i) {
  38.         int c = 0;
  39.         for (int j = 0; j < n; ++j) {
  40.             if (S[i][j] == '1') c++;
  41.         }
  42.         C_cnt[i] = c;
  43.     }
  44.  
  45.     vector<int> R_idx(k), S_idx(k);
  46.     iota(R_idx.begin(), R_idx.end(), 0);
  47.     iota(S_idx.begin(), S_idx.end(), 0);
  48.  
  49.     sort(R_idx.begin(), R_idx.end(), [&](int a, int b) {
  50.         return R_req[a] < R_req[b];
  51.     });
  52.     sort(S_idx.begin(), S_idx.end(), [&](int a, int b) {
  53.         return C_cnt[a] < C_cnt[b];
  54.     });
  55.  
  56.     bool ok = true;
  57.     for (int i = 0; i < k; ++i) {
  58.         if (R_req[R_idx[i]] != C_cnt[S_idx[i]]) {
  59.             ok = false;
  60.             break;
  61.         }
  62.     }
  63.  
  64.     if (!ok) {
  65.         cout << 0 << "\n";
  66.         return;
  67.     }
  68.  
  69.     vector<int> val(n, 0);
  70.     for (int i = 0; i < k; ++i) {
  71.         int str_idx = S_idx[i];
  72.         int bit_idx = R_idx[i];
  73.         for (int c = 0; c < n; ++c) {
  74.             if (S[str_idx][c] == '1') {
  75.                 val[c] |= (1 << bit_idx);
  76.             }
  77.         }
  78.     }
  79.  
  80.     vector<bool> seen(n + 1, false);
  81.     bool valid = true;
  82.     for (int c = 0; c < n; ++c) {
  83.         if (val[c] < 1 || val[c] > n || seen[val[c]]) {
  84.             valid = false;
  85.             break;
  86.         }
  87.         seen[val[c]] = true;
  88.     }
  89.  
  90.     if (!valid) {
  91.         cout << 0 << "\n";
  92.         return;
  93.     }
  94.  
  95.     long long fact[20];
  96.     fact[0] = 1;
  97.     for (int i = 1; i <= 18; ++i) fact[i] = fact[i - 1] * i;
  98.  
  99.     long long ans = 1;
  100.     int i = 0;
  101.     while (i < k) {
  102.         int j = i;
  103.         while (j < k && C_cnt[S_idx[j]] == C_cnt[S_idx[i]]) {
  104.             j++;
  105.         }
  106.         int m = j - i;
  107.         ans *= fact[m];
  108.  
  109.         vector<int> group_idx;
  110.         for (int l = i; l < j; ++l) {
  111.             group_idx.push_back(S_idx[l]);
  112.         }
  113.  
  114.         sort(group_idx.begin(), group_idx.end(), [&](int a, int b) {
  115.             return S[a] < S[b];
  116.         });
  117.  
  118.         int dup = 1;
  119.         for (size_t l = 1; l < group_idx.size(); ++l) {
  120.             if (S[group_idx[l]] == S[group_idx[l - 1]]) {
  121.                 dup++;
  122.             } else {
  123.                 ans /= fact[dup];
  124.                 dup = 1;
  125.             }
  126.         }
  127.         ans /= fact[dup];
  128.  
  129.         i = j;
  130.     }
  131.  
  132.     cout << ans << "\n";
  133. }
  134.  
  135. int main() {
  136.     ios_base::sync_with_stdio(false);
  137.     cin.tie(NULL);
  138.     int t;
  139.     if (cin >> t) {
  140.         while (t--) {
  141.             solve();
  142.         }
  143.     }
  144.     return 0;
  145. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
6
1
1
4
1010
0001
0110
7
0101011
1100101
0110110
5
10110
01100
11001
6
001011
111000
000000
7
1100001
1100001
1100011
stdout
copy 
1
2
6
0
0
0
https://ideone.com/Scf5cp
language:
C++14 (gcc 8.3)
created:
4 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!