/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 8ms 3.562 MiB
#2 Accepted 6ms 3.57 MiB
#3 Accepted 8ms 3.582 MiB
#4 Accepted 8ms 3.59 MiB
#5 Accepted 7ms 3.594 MiB
#6 Accepted 7ms 3.57 MiB
#7 Accepted 7ms 3.582 MiB
#8 Accepted 7ms 3.586 MiB
#9 Accepted 7ms 3.59 MiB
#10 Accepted 7ms 3.57 MiB
#11 Accepted 7ms 3.516 MiB
#12 Accepted 7ms 3.566 MiB
#13 Accepted 7ms 3.613 MiB
#14 Accepted 7ms 3.586 MiB
#15 Accepted 7ms 3.527 MiB
#16 Accepted 32ms 3.605 MiB
#17 Accepted 32ms 3.812 MiB
#18 Accepted 33ms 3.609 MiB
#19 Accepted 30ms 3.523 MiB
#20 Accepted 29ms 3.621 MiB
#21 Accepted 29ms 3.59 MiB

Code

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1000000007;
#define sz(x) (ll)(x).size()
#define rd ({ll x; cin >> x; x; })
#define dbg(x) cerr << "[" #x "]  " << (x) << "\n\n"
// #define errv(x) {cerr << "["#x"]  ["; for (const auto& ___ : (x)) cerr << ___ << ", "; cerr << "]\n";}
// #define errvn(x, n) {cerr << "["#x"]  ["; for (auto ___ = 0; ___ < (n); ++___) cerr << (x)[___] << ", "; cerr << "]\n";}
// #define cerr if(0)cerr
#define xx first
#define yy second
mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
/*_________________________________________________________________________________________________________________________*/
ll modpow(ll a, ll b)
{
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = (res * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }
    return res;
}
vector<ll> fact(200005, 1), inv(200005, 1);
void factoMod()
{
    for (int i = 1; i < 200005; i++)
        fact[i] = (fact[i - 1] * i) % MOD;
    inv[200004] = modpow(fact[200004], MOD - 2);
    for (int i = 200003; i >= 0; i--)
        inv[i] = (inv[i + 1] * (i + 1)) % MOD;
}
ll ncrMod(ll n, ll r)
{
    if (r > n)
        return 0;
    return (fact[n] * inv[r] % MOD * inv[n - r] % MOD) % MOD;
}
void Solve()
{
    ll n, k;
    cin >> n >> k;
    ll count[2] {};
    for (int i = 0; i < n; i++)
        count[rd]++;
    ll zer = modpow(2, count[0]);
    ll ans = 0;
    for (int i = 1; i <= count[1]; i++) {
        if (count[1] - i < k)
            break;
        ans += (ncrMod(count[1], i) * zer) % MOD;
        ans %= MOD;
    }
    if (k <= count[1])
        cout << (ans + zer - 1 + 2 * MOD) % MOD << '\n';
    else
        cout << ans << '\n';
}

int32_t main()
{
    factoMod();
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        // cout << "Case #" << i << ": "; // cout << "Case " << i << ": ";
        Solve();
    }
    return 0;
}
// Coded by Tahsin Arafat (@TahsinArafat)

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:43:20
Judged At
2024-11-11 02:59:41
Judged By
Score
100
Total Time
33ms
Peak Memory
3.812 MiB