結果

問題 No.3153 probability max K
ユーザー Shivam kumar Singh
提出日時 2025-05-20 22:13:38
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 115 ms / 2,000 ms
コード長 6,581 bytes
コンパイル時間 3,203 ms
コンパイル使用メモリ 224,516 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-20 22:13:44
合計ジャッジ時間 5,176 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
// #include <atcoder/all>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;

using namespace __gnu_pbds;
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
      x += 0x9e3779b97f4a7c15;
      x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
      x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
      return x ^ (x >> 31);
  }

  size_t operator()(uint64_t x) const {
      static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
      return splitmix64(x + FIXED_RANDOM);
  }
};



// https://docs.google.com/document/d/1VuLkJfkaBBFdcV-BPtT2JdTDrD2lC3POFj6NPTl_Pzo/edit?addon_store&tab=t.0
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; // find_by_order, order_of_key
//find by order-> element at ith idx(starting from 0)//gives iterator to that index//if not present *it gives 0
//order of key-> number of element less than a number

// erase function for ordered multiset
// void myerase(pbds &t, int v){
//     int rank = t.order_of_key(v);//Number of elements that are less than v in t
//     pbds::iterator it = t.find_by_order(rank); //Iterator that points to the (rank+1)th element in t
//     t.erase(it);
// }



#define int long long int 
// #define ll long long int
#define loop(var, s, e) for(int var = s; var < e; var++)
#define rloop(var, e, s) for(int var = e; var>= s; var--)
#define v vector<int>
// #define vll vector<long long int>
#define printyes cout<<"YES\n"
#define printno cout<<"NO\n"
//COMMENT THIS FOR INTERACTIVE PROBLEMS...............
// #define endl '\n'
#define mod (int)(998244353)
#define inf 1e18
#define dbg(x) cerr<<"value of "<<#x<<" is => "<<x<<endl;
#define all(x) x.begin(), x.end()
#define vpii vector<pair<int, int>>
#define pii pair<int,int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define vpll vector<pll>
#define here(i) cerr<<"here "<<i<<" "<<endl;
#define sz(x) (int)x.size()
#define rt return;
#define mx max_element
#define mn min_element
#define asum accumulate
#define i128 __int128_t
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

template <class A>
ostream& operator<<(ostream& out, const vector<A>& ve);

template <class A, class B>
ostream& operator<<(ostream& out, const pair<A, B>& a);

template <class A, class B>
ostream& operator<<(ostream& out, const pair<A, B>& a) {
    return out << "(" << a.first << ", " << a.second << ")";
}

template <class A>
ostream& operator<<(ostream& out, const vector<A>& ve) {
    out << "[";
    loop(i, 0, ve.size()) {
        if (i) out << ", ";
        out << ve[i];
    }
    return out << "]";
}



namespace bit {
  int setBit(int n, int bitNo) {
    n = (n|(1LL<<bitNo));
    return n;
  }

  int currBit(int n, int bitNo) {
    return ((n&(1ll<<bitNo)) == 0)?0:1;
  }

  int unSetBit(int n, int bitNo) {
    n = (n&(~(1ll<<bitNo)));
    return n;
  }
  /*
  __lg() returns the highest set bit index in a number i.e for 100 it will be 2 and for 000 will be -1

  __builtin_ctz() give number of trailing zeros -> 1000-> 3

  n&(n - 1) clears the first set bit

  n&(-n) give the first set bit => 101100 -> 000100

  n&(n + 1) clear all trailing ones

  n|(n + 1) set the first unset bit
  */
}
//*************************************************CHECK THE CONSTRAINTS**********************************************************//
int extendedEuclidean(int a, int b, int&x, int& y) {
  if(b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  int x1, y1;
  int d = extendedEuclidean(b, a%b, x1, y1);
  x = y1;
  y = x1 - y1*(a/b);
  return d;
}


int f(int a, int b) {
  if(b == 0)return 1;
  int res = f(a, b/2);
  if(b%2 != 0) {
    return (((res)%mod* (res)%mod)%mod * a)%mod;
  }
  else {
    return ((res)%mod * (res)%mod)%mod;
  }
}


int _f(int a, int b) {
  if(b == 0)return 1;
  int res = f(a, b/2);
  if(b%2 != 0) {
    return (((res)* (res))* a);
  }
  else {
    return ((res) * (res));
  }
}


int inv(int a, int b){
 return 1<a ? b - inv(b%a,a)*b/a : 1;
}


pair<v, v> linear_sieve(int n) {
  //https://cp-algorithms.com/algebra/prime-sieve-linear.html
  vector<int> lp(n + 1, 0);
  vector<int> primes;
  loop(i, 2, n + 1) {
    if(lp[i] == 0) {
      primes.pb(i);
      lp[i] = i;
    }
    for(int j = 0; i * primes[j] <= n; j++) {
      lp[primes[j] * i] = primes[j];
      if(primes[j] == lp[i])break;
    }
  }
  return pair<v, v>{lp, primes};
}

vector<bool> sieve(int n) {
  vector<bool> is_prime(n+1, 1);
  // v prime;
  // v dp(n + 1, 0);
  is_prime[0] = 0;
  is_prime[1] = 0;
  for(int i = 2; i <= n; i++) {
    if(is_prime[i] == 1) {
      // prime.pb(i);
      for(int j = i*i; j <= n; j+=i) {
        is_prime[j] = 0;
      }
    }
  }
  return is_prime;
}

int floor_div(int a, int b) {
  int res = a/b;
  if(a > 0 && b < 0 || a < 0 && b > 0)res--;
  return res;
}

int ceil_div(int a, int b) {
  if(a > 0 && b < 0 || a < 0 && b > 0) {
    return a/b;
  }
  return (a + b - 1)/b;
}
// void *memcpy(void *dest, const void *src, size_t n);
// make the hard time of your life as your strength
// first write complete pseudo code on paper then code dont care about the time!!!!!!
const int delRow[16] = {1, 0, 0, -1, 1, 1, -1, -1, 2, 2, 1, 1, -1, -1, -2, -2};
const int delCol[16] = {0, -1, 1, 0, -1, 1, -1, 1, -1, 1, -2, 2, -2, 2, -1, 1};
//               U  L   D  R


//find by order-> element at ith idx(starting from 0)//gives iterator to that index//if not present *it gives 0
//order of key-> number of element less than a number


void pikachu(int tt, int tc) {
  int n, k;
  cin>>n>>k;
  v arr(n);
  loop(i, 0, n)cin>>arr[i];
  int sub = 1;
  int big = 1;
  loop(i, 0, n) {
    if(arr[i] >= k) {
      int a = inv(arr[i], mod);
      int b = (a * (k - 1))%mod;
      sub = (sub * b)%mod;
      big = (big * ((a + b)%mod))%mod;
    }
  }
  cout<<(big - sub + mod)%mod<<endl;
} 




int32_t main() {
  auto begin = std::chrono::high_resolution_clock::now();
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
  #endif
  int gsBall = 1;
//   cin>>gsBall;
  int tt = gsBall;
  int tc = 1; 
  cout<<setprecision(20);
  
  while(gsBall--) {
    pikachu(tt, tc);
    tc++;
  }
  auto end = std::chrono::high_resolution_clock::now();
  auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
  cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
  return 0;
}
0