Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MAXN = 22;
- int viz[30];
- int dp[(1 << MAXN)][22];
- long long tab[(1 << MAXN)][22];
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- int N, H;
- cin >> N >> H;
- for (int i = 0; i < N; i++)
- {
- string s;
- cin >> s;
- for (int j = 0; j < N; j++)
- {
- if (s[j] == '1') viz[i] |= (1LL << j);
- }
- }
- for (int mask = 0; mask < (1 << N); mask++)
- {
- int prox = 0; long long peso = 0LL;
- for (int v = 0; v < N; v++)
- {
- if (mask & (1 << v))
- {
- peso += (long long)__builtin_popcount(viz[v]);
- prox ^= viz[v];
- }
- else peso += 2LL*((long long)(__builtin_popcount(viz[v])));
- }
- dp[mask][0] = prox;
- tab[mask][0] = peso;
- }
- for (int k = 1; k < 22; k++)
- {
- for (int i = 0; i < (1 << N); i++)
- {
- dp[i][k] = dp[ dp[i][k-1] ][k-1];
- tab[i][k] = tab[i][k-1] + tab[ dp[i][k-1] ][k-1];
- }
- }
- int A = viz[0]; long long resp = 0LL; H--;
- resp = (long long)(__builtin_popcount(viz[0]));
- for (int k = 0; k < 22; k++)
- {
- if (H & (1 << k))
- {
- resp += tab[A][k];
- A = dp[A][k];
- }
- }
- cout << resp;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement