結果
問題 | No.2876 Infection |
ユーザー |
![]() |
提出日時 | 2024-09-06 23:48:36 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 165 ms / 2,000 ms |
コード長 | 1,767 bytes |
コンパイル時間 | 5,529 ms |
コンパイル使用メモリ | 317,680 KB |
実行使用メモリ | 113,152 KB |
最終ジャッジ日時 | 2024-09-06 23:48:48 |
合計ジャッジ時間 | 10,836 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include <atcoder/all>#include <bits/stdc++.h>#define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)using namespace atcoder;using namespace std;typedef long long ll;using mint = modint998244353;struct Comb {vector<mint> fact, ifact;int MAX_COM;Comb() {}Comb(int n) {MAX_COM = n; // ここでMAX入力を調整init(998244353, MAX_COM);}void init(long long MOD, long long MAX_COM) {int n = MAX_COM;assert(n < MOD);fact = vector<mint>(n + 1);ifact = vector<mint>(n + 1);fact[0] = 1;for (int i = 1; i <= n; ++i)fact[i] = fact[i - 1] * i;ifact[n] = fact[n].inv();for (int i = n; i >= 1; --i)ifact[i - 1] = ifact[i] * i;}mint operator()(long long n, long long k) {if (k < 0 || k > n)return 0;return fact[n] * ifact[k] * ifact[n - k];}};Comb comb(5000010);int main() {int N, x;cin >> N >> x;vector<int> alc(3000);vector<mint> c(3000);vector als(3000, vector<int>(3000));vector s(3000, vector<mint>(3000));mint ans = 0;mint p = (mint)x / 100;mint q = 1 - p;function<mint(int)> fc;function<mint(int, int)> fs;fc = [&](int n) {if (alc[n])return c[n];mint ret = 1;rep(i, 1, n) { ret -= fs(n, i); }alc[n] = 1;return c[n] = ret;};fs = [&](int n, int k) {if (als[n][k])return s[n][k];mint ret = comb(n - 1, k - 1);ret *= fc(k);ret *= q.pow(k * (n - k));als[n][k] = 1;return s[n][k] = ret;};rep(k, 1, N + 1) { ans += k * fs(N, k); }cout << ans.val() << endl;}