結果
問題 | No.3095 Many Min Problems |
ユーザー |
![]() |
提出日時 | 2025-04-06 17:27:59 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 146 ms / 2,000 ms |
コード長 | 1,499 bytes |
コンパイル時間 | 2,957 ms |
コンパイル使用メモリ | 140,660 KB |
実行使用メモリ | 11,160 KB |
最終ジャッジ日時 | 2025-04-06 17:28:06 |
合計ジャッジ時間 | 6,284 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
//https://atcoder.jp/contests/oupc2023-day1/submissions/49049182 #include<iostream> #include<cassert> #include<atcoder/modint> #include<atcoder/convolution> using namespace std; using mint=atcoder::modint998244353; using Fps=vector<mint>; int sz(const Fps& a) { return a.size(); } Fps inv(const Fps& a) { Fps res{a[0].inv()}; for (res.reserve(sz(a)); sz(res) < sz(a);) { Fps buf(2 * sz(res)), fres(sz(buf)); std::copy(a.begin(), a.begin() + std::min(sz(buf), sz(a)), buf.begin()); std::copy(res.begin(), res.end(), fres.begin()); atcoder::internal::butterfly(buf); atcoder::internal::butterfly(fres); for (int i = 0; i < sz(buf); ++i) buf[i] *= fres[i]; atcoder::internal::butterfly_inv(buf); std::fill(buf.begin(), buf.begin() + sz(res), 0); atcoder::internal::butterfly(buf); for (int i = 0; i < sz(buf); ++i) buf[i] *= fres[i]; atcoder::internal::butterfly_inv(buf); mint coeff = -mint((1 - mint::mod()) / sz(buf)).pow(2); for (int i = sz(res); i < std::min(sz(buf), sz(a)); ++i) res.push_back(buf[i] * coeff); } return res; } int N; long long M; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>N>>M; mint ans=0; {//a const int sz=N; Fps P(sz+1),Q(sz+1); mint fac=1; for(int i=0;i<=sz;i++) { fac*=mint(i+1).inv(); P[i]=mint(M+1).pow(i+1)*fac; Q[i]=fac; } P=atcoder::convolution(P,inv(Q)); fac=1; for(int k=1;k<=N;k++) { mint a = mint(M).pow(N-k); fac*=k; ans+=a*P[k]*fac; } } cout<<ans.val()<<endl; }