fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. const int N=4e5+7;
  6. const int mod =1000000007;
  7. int fact[N];
  8.  
  9. int binpow(int a,int b,int m) {
  10.     a %= m;
  11.     int res = 1;
  12.     while(b>0) {
  13.         if (b&1)
  14.         {
  15.             res=res*a%m;
  16.         }
  17.         a=a*a%m;
  18.         b>>=1;
  19.     }
  20.     return res;
  21. }
  22. int ncr(int n,int k)
  23. {
  24.     int res=fact[n];
  25.     res=(res*1LL*binpow(fact[k],mod-2,mod))%mod;
  26.     res=(res*1LL*binpow(fact[n-k],mod-2,mod))%mod;
  27.     return res;
  28. }
  29.  
  30. void solve() {
  31. 	int n;
  32. 	cin >> n;
  33.  
  34. 	string a, b;
  35. 	cin >> a >> b;
  36.  
  37.     fact[0]=fact[1]=1;
  38. 	for (int i = 2; i <= n; ++i) {
  39. 		fact[i] = (1LL * fact[i - 1] * i) % mod;
  40. 	}
  41.  
  42. 	int ones_a = count(a.begin(), a.end(), '1');
  43. 	int ones_b = count(b.begin(), b.end(), '1');
  44.  
  45. 	int min_ones = abs(ones_a - ones_b);
  46. 	int max_ones = ones_a + ones_b - 2 * max(0LL, ones_a + ones_b - n);
  47.  
  48. 	int ans = 0;
  49. 	for (int ones = min_ones; ones <= max_ones; ones+=2) {
  50. 		ans = (ans + ncr(n, ones)) % mod;
  51. 	}
  52.  
  53. 	cout << ans << "\n";
  54. }
  55.  
  56. signed main () {
  57. 	int t;
  58. 	cin >> t;
  59. 	for (int i = 0; i < t; ++i) {
  60. 		solve();
  61. 	}
  62.  
  63. 	return 0;
  64. }
  65.  
Success #stdin #stdout 0.01s 5512KB
comments (?)
stdin
copy 
1
2
00
10
stdout
copy 
2
https://ideone.com/SmjroW
language:
C++14 (gcc 8.3)
created:
1 year 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!