結果
問題 | No.1857 Gacha Addiction |
ユーザー |
|
提出日時 | 2022-02-26 23:04:35 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 229 ms / 6,000 ms |
コード長 | 677 bytes |
コンパイル時間 | 2,752 ms |
コンパイル使用メモリ | 149,224 KB |
実行使用メモリ | 7,336 KB |
最終ジャッジ日時 | 2025-01-03 13:28:22 |
合計ジャッジ時間 | 11,996 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 43 |
ソースコード
#include <iostream>#include <vector>#include <atcoder/convolution>#include <functional>using namespace std;using Mint = atcoder::modint998244353;int main(){int N, S;cin >> N >> S;Mint Sinv = Mint(S).inv();vector<Mint> P;for (int i = 0; i < N; ++i){int p;cin >> p;P.push_back(p * Sinv);}function<vector<Mint>(int, int)> calc = [&](int l, int r){if (l == r)return vector<Mint>({1, P[l]});int m = (l + r) / 2;return atcoder::convolution(calc(l, m), calc(m + 1, r));};auto ret = calc(0, N - 1);Mint ans = 0, fact = 1;for (int i = 0; i <= N; i++){ans += ret[i] * fact;fact *= i + 1;}cout << ans.val() << endl;}