結果

問題 No.2963 Mecha DESU
コンテスト
ユーザー liveworldlike
提出日時 2024-11-16 16:58:21
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 227 ms / 2,000 ms
コード長 2,468 bytes
コンパイル時間 1,248 ms
コンパイル使用メモリ 89,920 KB
実行使用メモリ 25,552 KB
最終ジャッジ日時 2024-11-16 16:59:17
合計ジャッジ時間 7,765 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 57
権限があれば一括ダウンロードができます

ソースコード

diff # 

// Sat Nov 16 10:36:03 2024
// Problem "No.2963 Mecha DESU" in contest "unknown_contest"
#include <cmath>
#include <map>
#include <vector>
#pragma GCC optimize("O3")
#include <stdio.h>
#ifdef NOJUDGE
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...)
#endif
using namespace std;
typedef long long int ll;
const ll mod = 998244353;

constexpr inline ll fastpow(ll x, ll p) {
  ll res = 1;
  while (p) {
    if (p & 1)
      res = res * x % mod;
    x = x * x % mod;
    p >>= 1;
  }
  return res;
}

constexpr inline ll inv(ll x) { return fastpow(x, mod - 2); }

struct modint {
  ll x;
  double z;
  constexpr inline modint(ll x) : x(x % mod), z(x) {}
  constexpr inline modint(ll x, double z) : x(x % mod), z(z) {}
  constexpr inline modint operator+(modint y) {
    return modint(x + y.x, z + y.z);
  }
  constexpr inline modint operator-(modint y) {
    return modint(x - y.x, z - y.z);
  }
  constexpr inline modint operator*(modint y) {
    return modint(x * y.x, z * y.z);
  }
  constexpr inline modint operator/(modint y) {
    return modint(x * inv(y.x), z / y.z);
  }
  constexpr inline modint operator+=(modint y) {
    *this = *this + y;
    return *this;
  }
  constexpr inline modint operator-=(modint y) {
    *this = *this - y;
    return *this;
  }
  constexpr inline modint operator*=(modint y) {
    *this = *this * y;
    return *this;
  }
  constexpr inline modint operator/=(modint y) {
    *this = *this / y;
    return *this;
  }
  constexpr inline ll norm() { return (x + mod) % mod; }
};

constexpr inline modint sqr(modint x) { return x * x; }
constexpr inline modint fastpow(modint x, ll p) {
  return modint{fastpow(x.x, p), pow(x.z, p)};
}

inline void solve() {
  ll n, m, k;
  scanf("%lld %lld %lld", &n, &m, &k);
  map<ll, ll> freq;
  for (ll i = 0; i < m; i++) {
    ll x;
    scanf("%lld", &x);
    freq[x]++;
  }
  modint invm = modint{1} / modint(m);
  const ll N = n + 10;
  vector<modint> P(N, 0);
  for (auto [card, count] : freq) {
    for (ll i = card; i < N; i += card) {
      P[i] += modint{count} * invm;
    }
  }
  modint res{0};
  for (ll i = 1; i <= n; i++) {
    debug("P[%lld] = %f\n", i, P[i].z);
    res += modint{1} - fastpow(modint{1} - P[i], k);
  }
  printf("%lld\n", res.norm());
  debug("%f\n", res.z);
}

#define yukicoder

int main() {
#if defined(Codeforces) || defined(CodeChef)
  ll t;
  scanf("%lld", &t);
  for (int i = 0; i < t; i++) {
    solve();
  }
#else
  solve();
#endif
}
0