/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 21ms 5.117 MiB
#2 Wrong Answer 21ms 5.109 MiB
#3 Wrong Answer 23ms 5.105 MiB

Code

#include <bits/stdc++.h>
using namespace std;

#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using ll = long long;

const ll MOD = 1'000'000'007;

ll power(ll a, ll p, ll m = MOD) {
  a %= m;
  ll ans = 1;
  while (p) {
    if (p & 1ll) ans = (ans*a) % m;
    p >>= 1ll;
    a = (a*a) % m;
  }
  return ans;
}

struct Combinatorics {
  ll n, mod;
  vector<ll> _fac, _inv, _ifac;

  Combinatorics(ll n, ll mod) : n(n), mod(mod) {
    _fac.resize(n+1);
    _inv.resize(n+1);
    _ifac.resize(n+1);

    ll i;
    for (i = 0; i <= 1; ++i) _fac[i] = _inv[i] = _ifac[i] = 1;
    for (i = 2; i <= n; ++i) _fac[i] = (_fac[i-1] * i) % mod;
    for (i = 2; i <= n; ++i) _inv[i] = mod - ((mod/i * _inv[mod % i]) % mod);
    for (i = 2; i <= n; ++i) _ifac[i] = (_ifac[i-1] * _inv[i]) % mod;
  }

  ll fac(ll n) { return _fac[n]; }
  ll ifac(ll n) { return _ifac[n]; }
  ll inv(ll n) { return _inv[n]; }
  ll ncr(ll n, ll r) {
    if (r > n) return 0;
    ll ans = fac(n);
    ans = (ans * ifac(r)) % mod;
    ans = (ans * ifac(n-r)) % mod;
    return ans;
  }
} C(200005, MOD);

int main() {
  FAST;
  
  int tc = 1, ti;
  cin >> tc;

  for (ti = 1; ti <= tc; ++ti) {
    ll n, k, i, x, c0, c1, ans;
    cin >> n >> k;

    c0 = c1 = 0;
    for (i = 0; i < n; ++i) {
      cin >> x;
      if (x == 0) c0 += 1;
        else c1 += 1;
    }

    ans = 0;
    if (c1 >= k) {
      ans = 0;
      for (i = k; i < c1; ++i) {
        ans = (ans + C.ncr(c1, c1-i)) % MOD;
      }
      ans = (ans * power(2, c0)) % MOD;
      if (c0 > 0) {
        ans = (ans + power(2, c0-1)) % MOD;
      }
    }
    
    cout << ans << "\n";
  }

  return 0;
}

Information

Submit By
Type
Submission
Problem
P1094 Number of ways (Hard version)
Contest
Brain Booster #5
Language
C++20 (G++ 13.2.0)
Submit At
2024-09-05 16:18:28
Judged At
2024-11-11 03:01:00
Judged By
Score
1
Total Time
23ms
Peak Memory
5.117 MiB