結果

問題 No.1857 Gacha Addiction
コンテスト
ユーザー GOTKAKO
提出日時 2025-05-07 13:03:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 571 ms / 6,000 ms
コード長 1,590 bytes
コンパイル時間 4,979 ms
コンパイル使用メモリ 265,744 KB
実行使用メモリ 58,960 KB
最終ジャッジ日時 2025-05-07 13:04:00
合計ジャッジ時間 23,440 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
using fps = vector<mint>;

pair<fps,fps> SumfpsFraction(vector<fps> A,vector<fps> B){ //次数の和=n O(nlog^2n).
    //ΣAi/Biを求める 分割統治でO(nlog^2n).
    //a/b+c/d = (ad+bc)/bd 面倒なのでvector<mint>は用意せずfpsだけ;
    assert(A.size() == B.size() && A.size());
    int n = A.size();
    auto comp = [&](int a,int b) -> bool {return A[a].size()+B[a].size()>A[b].size()+B[b].size();};
    priority_queue<int,vector<int>,decltype(comp)> Q(comp);
    for(int i=0; i<n; i++) Q.push(i);
    while(Q.size() > 1){
        int p = Q.top(); Q.pop();
        int q = Q.top(); Q.pop();
        fps num = convolution(A.at(p),B.at(q));
        fps num2 = convolution(B.at(p),A.at(q));
        if(num.size() < num2.size()) num.resize(num2.size());
        for(int i=0; i<num2.size(); i++) num.at(i) += num2.at(i);
        A.at(p) = num; B.at(p) = convolution(B.at(p),B.at(q));
        Q.push(p);
    }
    int leader = Q.top();
    return {A.at(leader),B.at(leader)};
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N,S; cin >> N >> S;
    vector<fps> A(N),B(N);
    mint divS = mint(1)/S;
    for(int i=0; i<N; i++){
        int p; cin >> p;
        mint one = divS*p,two = one*one;
        A.at(i) = {two}; B.at(i) = {1,one};
    }
    auto [n,d] = SumfpsFraction(A,B);
    mint answer = 0,fac = 1;
    for(int i=0; i<n.size(); i++) answer += n.at(i)*fac*(i+2),fac *= i+2;
    cout << answer.val() << endl;
}
0