fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. ll dp[32][2][2][2][2];
  7.  
  8. void precompute() {
  9.     for (int k = 0; k <= 30; k++)
  10.         for (int b1 = 0; b1 < 2; b1++)
  11.             for (int b2 = 0; b2 < 2; b2++)
  12.                 for (int c1 = 0; c1 < 2; c1++)
  13.                     for (int c2 = 0; c2 < 2; c2++)
  14.                         if (k == 0) dp[k][b1][b2][c1][c2] = (b1 == 1 && c1 == 1) + (b2 == 1 && c2 == 1);
  15.                         else {
  16.                             int mid_b = b1 ^ b2, mid_c = c1 ^ c2;
  17.                             ll L = dp[k - 1][b1][mid_b][c1][mid_c], R = dp[k - 1][mid_b][b2][mid_c][c2];
  18.                             dp[k][b1][b2][c1][c2] = L + R;
  19.                             if (mid_b == 1 && mid_c == 1) dp[k][b1][b2][c1][c2]--;
  20.                         }
  21. }
  22.  
  23. void solve() {
  24.     int n, k; cin >> n >> k;
  25.     string s, z; cin >> s >> z;
  26.  
  27.     ll F[2][2] = {0};
  28.     for (int i = 0; i < n; i++) {
  29.         int b1 = s[i] - '0', b2 = z[i] - '0';
  30.         F[b1][b2]++;
  31.     }
  32.  
  33.     ll sum = 0, sum2 = 0;
  34.     for (int b1 = 0; b1 < 2; b1++)
  35.         for (int b2 = 0; b2 < 2; b2++) {
  36.             if (F[b1][b2] == 0) continue;
  37.             sum += F[b1][b2] * dp[k][b1][b2][b1][b2];
  38.             for (int c1 = 0; c1 < 2; c1++)
  39.                 for (int c2 = 0; c2 < 2; c2++) {
  40.                     if (F[c1][c2] == 0) continue;
  41.                     sum2 += F[b1][b2] * F[c1][c2] * dp[k][b1][b2][c1][c2];
  42.                 }
  43.         }
  44.     ll ans = n * sum - sum2;
  45.     cout << ans << '\n';
  46. }
  47.  
  48. int main() {
  49.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  50.  
  51.     precompute();
  52.  
  53.     int tests = 1; cin >> tests;
  54.     while (tests--) solve();
  55.  
  56.     return 0;
  57. }
  58.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
4
3 2
010
110
1 1
0
0
2 2
01
00
7 30
1010111
0011010
stdout
copy 
10
0
3
12169074016
https://ideone.com/7pZYOE
language:
C++14 (gcc 8.3)
created:
1 day 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!