fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. #define REP(i,n) for (int i = 1; i <= n; i++)
  3. #define mod 1000000007
  4. #define pb push_back
  5. #define ff first
  6. #define ss second
  7. #define ii pair<int,int>
  8. #define vi vector<int>
  9. #define vii vector<ii>
  10. #define lli long long int
  11. #define INF 1000000000
  12. #define endl '\n'
  13. const double PI = 3.141592653589793238460;
  14. typedef std::complex<double> Complex;
  15. typedef std::valarray<Complex> CArray;
  16.  
  17. using namespace std;
  18. lli fact[100001];
  19. int N = 100000;
  20.  
  21. void init()
  22. {
  23. 	fact[0] = 1;
  24. 	REP(i , N) fact[i] = (fact[i-1] * i) % mod;
  25. }
  26.  
  27. lli power(lli a , lli n)
  28. {
  29. 	lli res = 1;
  30. 	while(n)
  31. 	{
  32. 		if(n & 1)
  33. 			res = (res * a) % mod;
  34.  
  35. 		n >>= 1;
  36. 		a = (a * a) % mod;
  37. 	}
  38.  
  39. 	return res;
  40. }
  41. int main()
  42. {
  43. 	lli t , n , bitsA , bitsB , res , _min , _max;
  44. 	char c;
  45.  
  46. 	cin>>t , init();
  47. 	while(t--)
  48. 	{
  49. 		cin>>n , bitsA = 0 , bitsB = 0;
  50. 		REP(i , n) cin>>c , bitsA += c - '0';
  51. 		REP(i , n) cin>>c , bitsB += c - '0';
  52.  
  53. 		res = 0;
  54. 		_max = bitsA + bitsB - 2 * max((lli)0 , bitsB + bitsA - n);
  55. 		_min = abs(bitsA - bitsB);
  56.  
  57. 		for(int i=_max;i>=_min;i-=2)
  58. 		{
  59. 			lli tmp = (power(fact[i] , mod-2) * fact[n]) % mod;
  60. 			tmp = (tmp * power(fact[n-i] , mod-2)) % mod;
  61.  
  62. 			res = (res + tmp) % mod;
  63. 		}
  64.  
  65. 		cout<<res<<endl;
  66. 	}
  67. }
  68.  
Success #stdin #stdout 0s 4556KB
comments (?)
stdin
copy 
1
2
00
10
stdout
copy 
2
https://ideone.com/wk64RM
BINXOR Dec long challenge 2019
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!