fork download 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. long long dp[35][4][4];
  9.  
  10. void precompute() {
  11.     for (int u = 0; u < 4; ++u) {
  12.         for (int v = 0; v < 4; ++v) {
  13.             dp[0][u][v] = (u == 2) + (v == 2);
  14.         }
  15.     }
  16.     for (int i = 0; i < 30; ++i) {
  17.         for (int u = 0; u < 4; ++u) {
  18.             for (int v = 0; v < 4; ++v) {
  19.                 int mid = u ^ v;
  20.                 dp[i+1][u][v] = dp[i][u][mid] + dp[i][mid][v] - (mid == 2);
  21.             }
  22.         }
  23.     }
  24. }
  25.  
  26. void print128(__int128 n) {
  27.     if (n == 0) {
  28.         cout << 0 << "\n";
  29.         return;
  30.     }
  31.     string s;
  32.     while (n > 0) {
  33.         s += (char)('0' + (n % 10));
  34.         n /= 10;
  35.     }
  36.     reverse(s.begin(), s.end());
  37.     cout << s << "\n";
  38. }
  39.  
  40. void solve() {
  41.     int n, k;
  42.     cin >> n >> k;
  43.     string s, z;
  44.     cin >> s >> z;
  45.  
  46.     long long cnt[4] = {0};
  47.     for (int i = 0; i < n; ++i) {
  48.         int tp = ((s[i] - '0') << 1) | (z[i] - '0');
  49.         cnt[tp]++;
  50.     }
  51.  
  52.     __int128 total_sum = 0;
  53.     for (int tp = 0; tp < 4; ++tp) {
  54.         for (int tq = 0; tq < 4; ++tq) {
  55.             long long pairs = cnt[tp] * cnt[tq];
  56.             if (pairs == 0) continue;
  57.             int sL = ((tp >> 1) << 1) | (tq >> 1);
  58.             int sR = ((tp & 1) << 1) | (tq & 1);
  59.             total_sum += (__int128)pairs * dp[k][sL][sR];
  60.         }
  61.     }
  62.     print128(total_sum);
  63. }
  64.  
  65. int main() {
  66.     ios_base::sync_with_stdio(false);
  67.     cin.tie(NULL);
  68.     precompute();
  69.     int t;
  70.     if (cin >> t) {
  71.         while (t--) {
  72.             solve();
  73.         }
  74.     }
  75.     return 0;
  76. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
4
3 2
010
110
1 1
0
0
2 2
01
00
7 30
1010111
0011010
stdout 
10
0
3
12169074016
https://ideone.com/zkKncq
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!