fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define endl '\n'
  5. #define all(x) x.begin(), x.end()
  6. #define rall(x) x.rbegin(), x.rend()
  7. #define mem(a, b) memset(a, b, sizeof(a))
  8. #define read(x)        \
  9.     for (auto &it : x) \
  10.         cin >> it;
  11. #define write(x)      \
  12.     for (auto it : x) \
  13.         cout << it << " ";
  14. const int MOD = 1e9 + 7;
  15. ll arr[200008];
  16.  
  17. ll power(ll base, ll exp)
  18. {
  19.     int result = 1;
  20.     base %= MOD;
  21.     while (exp > 0)
  22.     {
  23.         if (exp % 2 == 1)
  24.         {
  25.             result = (result * base) % MOD;
  26.         }
  27.         base = (base * base) % MOD;
  28.         exp /= 2;
  29.     }
  30.     return result;
  31. }
  32.  
  33. ll modInverse(ll a)
  34. {
  35.     return power(a, MOD - 2); ////power is the function for binary_exponentiation
  36. }
  37. ll nCr(int n, int r)
  38. {
  39.     if (r > n)
  40.         return 0LL;
  41.  
  42.     return (arr[n] * modInverse(((arr[r]) * arr[n - r]) % MOD)) % MOD;
  43. }
  44. int32_t main()
  45. {
  46.     ios::sync_with_stdio(false);
  47.     cin.tie(NULL);
  48.  
  49.     arr[0] = 1;
  50.     for (int i = 1; i <= 200005; i++)
  51.     {
  52.         arr[i] = (arr[i - 1] * i) % MOD;
  53.         }
  54.  
  55.     ll t;
  56.     cin >> t;
  57.     while (t--)
  58.     {
  59.         ll n, k;
  60.         cin >> n >> k;
  61.         vector<int> v(n);
  62.         read(v) ll x = 0, y = 0;
  63.         for (int i = 0; i < n; i++)
  64.         {
  65.             if (v[i])
  66.                 x++;
  67.             else
  68.                 y++;
  69.         }
  70.  
  71.         ll f = (k / 2) + 1;
  72.  
  73.         ll sum = 0;
  74.         for (ll i = f; i <= min(k, x); i++)
  75.  
  76.         {
  77.  
  78.             ll ff = (nCr(x, i) * nCr(y, k - i)) % MOD;
  79.             sum = (sum + ff) % MOD;
  80.         }
  81.  
  82.         cout << sum << endl;
  83.     }
  84.  
  85.     return 0;
  86. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/zZnEGF
language:
C++14 (gcc 8.3)
created:
21 hours 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!