/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 6ms 3.402 MiB
#2 Accepted 6ms 3.562 MiB
#3 Wrong Answer 6ms 3.566 MiB
#4 Wrong Answer 6ms 3.566 MiB

Code


#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define endl '\n';

 
const int N = 2e5 + 9, mod = 998244353;

long long binmul(long long a, long long b) {
    return ((a % mod) * (b % mod)) % mod;
}
long long binpow(long long a, long long b) {
    a %= mod;
    long long res = 1LL;
    while (b > 0) {
        if (b & 1) res = binmul(res , a );
        a = binmul(a, a);
        b >>= 1;
    }
    return res;
}
long long inverse(long long a) {
    return binpow(a, mod - 2);
}



int power(long long n, long long k) {
    int ans = 1 % mod; n %= mod; if (n < 0) n += mod;
    while (k) {
        if (k & 1) ans = (long long) ans * n % mod;
        n = (long long) n * n % mod;
        k >>= 1;
    }
    return ans;
}
int f[N], invf[N];
void pre_call() {
    f[0] = 1;
    for (int i = 1; i < N; i++) {
        f[i] = 1LL * i * f[i - 1] % mod;
    }
    invf[N - 1] = power(f[N - 1], mod - 2);
    for (int i = N - 2; i >= 0; i--) {
        invf[i] = 1LL * invf[i + 1] * (i + 1) % mod;
    }
}
int nCr(int n, int r) {
    if (n < r or n < 0 ) return 0;
    if (r < 0) return 1;
    return 1LL * f[n] * invf[r] % mod * invf[n - r] % mod;
}
int nPr(int n, int r) {
    if (n < r or n < 0) return 1;
    return 1LL * f[n] * invf[n - r] % mod;
}


int minuss(int a, int b) {
   a %= mod;
   b %= mod;

   
   a += mod;
   a -= b;

   a %= mod;

   return a;
} 



 
void solve() {
    int n , k; cin >> n >> k;

int ar[n + 3];
int one = 0, zero = 0;
    for(int i = 1; i <= n; i++) {
      cin >> ar[i];
      if(ar[i] == 1) {
         one++;
      }
      else zero++;
    }


    if(k > one) {
       cout << 0 << endl;
       return;
    }
    else {
      int x = 0;
     for(int i = k; k <= one; k++) {
      x += nCr(one, k);
     }

     x  = binmul(binpow(2, zero), x);
     x = minuss(x , 1);
     cout << x << endl;
    }
}
int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = 1;
    pre_call();
    cin >> t;
    while (t--)
        solve();
    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:08:01
Judged At
2024-11-11 03:01:37
Judged By
Score
3
Total Time
6ms
Peak Memory
3.566 MiB