Advertisement
ThegeekKnight16

Lubenica

Sep 6th, 2022
239
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.40 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MAXN = 22;
  4. int viz[30];
  5. int dp[(1 << MAXN)][22];
  6. long long tab[(1 << MAXN)][22];
  7.  
  8. int main()
  9. {
  10.     ios_base::sync_with_stdio(false);
  11.     cin.tie(NULL);
  12.     int N, H;
  13.     cin >> N >> H;
  14.     for (int i = 0; i < N; i++)
  15.     {
  16.         string s;
  17.         cin >> s;
  18.         for (int j = 0; j < N; j++)
  19.         {
  20.             if (s[j] == '1') viz[i] |= (1LL << j);
  21.         }
  22.     }
  23.    
  24.     for (int mask = 0; mask < (1 << N); mask++)
  25.     {
  26.         int prox = 0; long long peso = 0LL;
  27.         for (int v = 0; v < N; v++)
  28.         {
  29.             if (mask & (1 << v))
  30.             {
  31.                 peso += (long long)__builtin_popcount(viz[v]);
  32.                 prox ^= viz[v];
  33.             }
  34.             else peso += 2LL*((long long)(__builtin_popcount(viz[v])));
  35.         }
  36.         dp[mask][0] = prox;
  37.         tab[mask][0] = peso;
  38.     }
  39.    
  40.     for (int k = 1; k < 22; k++)
  41.     {
  42.         for (int i = 0; i < (1 << N); i++)
  43.         {
  44.             dp[i][k] = dp[ dp[i][k-1] ][k-1];
  45.             tab[i][k] = tab[i][k-1] + tab[ dp[i][k-1] ][k-1];
  46.         }
  47.     }
  48.    
  49.     int A = viz[0]; long long resp = 0LL; H--;
  50.     resp = (long long)(__builtin_popcount(viz[0]));
  51.    
  52.     for (int k = 0; k < 22; k++)
  53.     {
  54.         if (H & (1 << k))
  55.         {
  56.             resp += tab[A][k];
  57.             A = dp[A][k];
  58.         }
  59.     }
  60.     cout << resp;
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement