結果

問題 No.3153 probability max K
ユーザー asmin
提出日時 2025-05-20 21:39:50
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 27 ms / 2,000 ms
コード長 5,735 bytes
コンパイル時間 2,465 ms
コンパイル使用メモリ 207,864 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-05-20 21:39:54
合計ジャッジ時間 4,066 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma region
/*
\(^o^)/
import sys
私は人間です．



吾輩はやれば出来る子である.

　　　　∩ ∩
　　　（´･ω･）
　　 ＿|　⊃／(＿＿_
　／　└-(＿＿＿_／
　￣￣￣￣￣￣￣

　やる気はまだない.

　　 ⊂⌒／ヽ-、＿_
　／⊂_/＿＿＿＿ ／
　￣￣￣￣￣￣￣
*/
#include<algorithm>
#include<array>
#include<bitset>
#include<cassert>
#include<chrono>
#include<cinttypes>
#include<climits>
#include<cmath>
#include<complex>
#include<cstdio>
#include<cstring>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<limits>
#include<map>
#include<numeric>
#include<queue>
#include<random>
#include<set>
#include<sstream>
#include<stack>
#include<string>
#include<tuple>
#include<type_traits>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>
using namespace std;
struct Init{Init(){std::cin.tie(0); ios::sync_with_stdio(false); cout << setprecision(20) << fixed;}}init;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define all(x) begin((x)), end((x))
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define uq(v) v.erase(unique(begin(v), end(v)), end(v))
#define _overload4(_1,_2,_3,_4,name,...) name
#define _overload3(_1,_2,_3,name,...) name
#define _rep1(n) for(int i=0;i<n;++i)
#define _rep2(i,n) for(int i=0;i<n;++i)
#define _rep3(i,a,b) for(int i=a;i<b;++i)
#define _rep4(i,a,b,c) for(int i=a;i<b;i+=c)
#define rep(...) _overload4(__VA_ARGS__,_rep4,_rep3,_rep2,_rep1)(__VA_ARGS__)
#define _rrep1(n) for(int i=(n)-1;i>=0;i--)
#define _rrep2(i,n) for(int i=(n)-1;i>=0;i--)
#define _rrep3(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define _rrep4(i,a,b,c) for(int i=a+(b-a-1)/c*c;i>=a;i-=c)
#define rrep(...) _overload4(__VA_ARGS__,_rrep4,_rrep3,_rrep2,_rrep1)(__VA_ARGS__)
template<class T> using pq = priority_queue<T>;
template<class T> using pq_g = priority_queue<T, vector<T>, greater<T>>;
template<class T> bool chmax(T &a, const T &b){if(a < b){a = b; return 1; } return 0;}
template<class T> bool chmin(T &a, const T &b){if(a > b){a = b; return 1; } return 0;}
template<class T> auto min(const T& a){ return *min_element(all(a)); }
template<class T> auto max(const T& a){ return *max_element(all(a)); }
constexpr ull INF = (1ULL << 61) + (1ULL << 30);
constexpr int inf = (1 << 30);
constexpr ld EPS = 1e-9;
constexpr int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
constexpr int dy[] = {0, 1 ,0, -1, 1, -1, 1, -1};

#pragma endregion

template <uint32_t mod_, bool fast = false>
struct MontgomeryModInt {
private:
    using mint = MontgomeryModInt;
    using i32 = int32_t;
    using i64 = int64_t;
    using u32 = uint32_t;
    using u64 = uint64_t;

    static constexpr u32 get_r() {
        u32 ret = mod_;
        for (i32 i = 0; i < 4; i++) ret *= 2 - mod_ * ret;
        return ret;
    }

    static constexpr u32 r = get_r();

    static constexpr u32 n2 = -u64(mod_) % mod_;

    static_assert(r * mod_ == 1, "invalid, r * mod != 1");
    static_assert(mod_ < (1 << 30), "invalid, mod >= 2 ^ 30");
    static_assert((mod_ & 1) == 1, "invalid, mod % 2 == 0");

    u32 x;

    public:
    MontgomeryModInt() : x{} {}

    MontgomeryModInt(const i64 &a): x(reduce(u64(fast ? a : (a % mod() + mod())) * n2)) {}

    static constexpr u32 reduce(const u64 &b) {
        return u32(b >> 32) + mod() - u32((u64(u32(b) * r) * mod()) >> 32);
    }

    mint &operator+=(const mint &p) {
        if (i32(x += p.x - 2 * mod()) < 0) x += 2 * mod();
        return *this;
    }

    mint &operator-=(const mint &p) {
        if (i32(x -= p.x) < 0) x += 2 * mod();
        return *this;
    }

    mint &operator*=(const mint &p) {
        x = reduce(u64(x) * p.x);
        return *this;
    }

    mint &operator/=(const mint &p) {
        *this *= p.inv();
        return *this;
    }

    mint operator-() const { return mint() - *this; }

    mint operator+(const mint &p) const { return mint(*this) += p; }

    mint operator-(const mint &p) const { return mint(*this) -= p; }

    mint operator*(const mint &p) const { return mint(*this) *= p; }

    mint operator/(const mint &p) const { return mint(*this) /= p; }

    bool operator==(const mint &p) const {
        return (x >= mod() ? x - mod() : x) == (p.x >= mod() ? p.x - mod() : p.x);
    }

    bool operator!=(const mint &p) const {
        return (x >= mod() ? x - mod() : x) != (p.x >= mod() ? p.x - mod() : p.x);
    }

    u32 val() const {
        u32 ret = reduce(x);
        return ret >= mod() ? ret - mod() : ret;
    }

    mint pow(u64 n) const {
        mint ret(1), mul(*this);
        while (n > 0) {
            if (n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }

    mint inv() const { return pow(mod() - 2); }

    friend ostream &operator<<(ostream &os, const mint &p) {
        return os << p.val();
    }

    friend istream &operator>>(istream &is, mint &a) {
        i64 t;
        is >> t;
        a = mint(t);
        return is;
    }

    static constexpr u32 mod() { return mod_; }
};

template <uint32_t mod>
using modint = MontgomeryModInt<mod>;
using mint = modint<998244353>;

int main(){
    int N, K; cin >> N >> K;
    mint cnt1 = 1, cnt2 = 1;
    bool ok = false;
    mint sum = 1;
    rep(i, N){
        int A; cin >> A;
        sum *= A;
        if(A >= K) ok = true;
        if(A >= K){
            cnt1 *= K;
            cnt2 *= K - 1;
        }else if(A == K - 1){
            cnt1 *= K - 1;
            cnt2 *= K - 1;
        }else{
            cnt1 *= A;
            cnt2 *= A;
        }
    }
    if(ok) cout << (cnt1 - cnt2) / sum;
    else cout << 0;
    cout << "\n";
}
0