/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 6ms 3.566 MiB
#2 Wrong Answer 5ms 3.566 MiB
#3 Wrong Answer 6ms 3.48 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;
      int mxCut = one - k;
      for (int i = 1; k <= mxCut; k++)
      {
         x += nCr(one, i);
      }
      // cout << binpow(2, zero) << endl;
      x = binmul(binpow(2, zero), x);
      // cout << "ncr "  << x << endl;
      // cout << x << endl;
      if(zero)
      x += minuss(binpow(2, zero), 1);


      x %= mod;
      // cout << x << endl;
      // if (zero)
      // 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
P1093 Number of Ways (Easy version)
Contest
Brain Booster #5
Language
C++20 (G++ 13.2.0)
Submit At
2024-09-05 16:28:11
Judged At
2024-11-11 03:00:32
Judged By
Score
1
Total Time
6ms
Peak Memory
3.566 MiB