fork download
copy 
  1. #include <cmath>
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <string>
  6. #include <set>
  7. #include <map>
  8. #include <list>
  9. #include <time.h>
  10. #include <math.h>
  11. #include <random>
  12. #include <deque>
  13. #include <queue>
  14. #include <cassert>
  15. #include <unordered_map>
  16. #include <unordered_set>
  17. #include <iomanip>
  18. #include <bitset>
  19. #include <sstream>
  20. #include <chrono>
  21. #include <cstring>
  22.  
  23. using namespace std;
  24.  
  25. typedef long long ll;
  26.  
  27. #ifdef iq
  28.   mt19937 rnd(228);
  29. #else
  30.   mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
  31. #endif
  32.  
  33. const int N = 1e5 + 7;
  34. const int M = 1e9 + 7;
  35.  
  36. int add(int a, int b) {
  37.   int c = a + b;
  38.   if (c < 0) c += M;
  39.   if (c >= M) c -= M;
  40.   return c;
  41. }
  42.  
  43. int mul(int a, int b) {
  44.   return (a * (ll) b) % M;
  45. }
  46.  
  47. int pw(int a, int n) {
  48.   int res = 1;
  49.   while (n) {
  50.     if (n % 2 == 0) {
  51.       a = mul(a, a);
  52.       n /= 2;
  53.     } else {
  54.       res = mul(res, a);
  55.       n--;
  56.     }
  57.   }
  58.   return res;
  59. }
  60.  
  61. int inv(int x) {
  62.   return pw(x, M - 2);
  63. }
  64.  
  65. int main() {
  66. #ifdef iq
  67.   freopen("a.in", "r", stdin);
  68. #endif
  69.   ios::sync_with_stdio(0);
  70.   cin.tie(0);
  71.   int t;
  72.   cin >> t;
  73.   while (t--) {
  74.     int n;
  75.     cin >> n;
  76.     vector <int> fact(n + 1), rfact(n + 1);
  77.     fact[0] = 1;
  78.     for (int i = 1; i <= n; i++) {
  79.       fact[i] = mul(fact[i - 1], i);
  80.     }
  81.     rfact[n] = inv(fact[n]);
  82.     for (int i = n - 1; i >= 0; i--) {
  83.       rfact[i] = mul(rfact[i + 1], i + 1);
  84.     }
  85.     auto C = [&] (int n, int k) {
  86.       return mul(fact[n], mul(rfact[k], rfact[n - k]));
  87.     };
  88.     string a, b;
  89.     cin >> a >> b;
  90.     vector <int> x(2), y(2);
  91.     for (auto c : a) {
  92.       x[c - '0']++;
  93.     }
  94.     for (auto c : b) {
  95.       y[c - '0']++;
  96.     }
  97.     int l = 0, r = 0;
  98.     for (int ts = 0; ts < 2; ts++) {
  99.       auto _x = x, _y = y;
  100.       int ret = 0;
  101.       for (int i = 0; i < 2; i++) {
  102.         int a = min(_x[i], _y[i ^ ts]);
  103.         _x[i] -= a, _y[i ^ ts] -= a;
  104.         ret += (ts * a);
  105.       }
  106.       for (int i = 0; i < 2; i++) {
  107.         int a = min(_x[i], _y[i ^ ts ^ 1]);
  108.         _x[i] -= a, _y[i ^ ts ^ 1] -= a;
  109.         ret += ((ts ^ 1) * a);
  110.       }
  111.       if (ts == 0) l = ret;
  112.       else r = ret;
  113.     }
  114.     int sum = 0;
  115.     for (int i = l; i <= r; i += 2) {
  116.       sum = add(sum, C(n, i));
  117.     }
  118.     cout << sum << endl;
  119.   }
  120. }
Success #stdin #stdout 0s 4176KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/rKHt5u
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!