結果
問題 |
No.3045 反復重み付き累積和
|
ユーザー |
|
提出日時 | 2025-02-28 23:01:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 385 ms / 5,000 ms |
コード長 | 1,617 bytes |
コンパイル時間 | 2,144 ms |
コンパイル使用メモリ | 106,732 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2025-02-28 23:01:36 |
合計ジャッジ時間 | 7,311 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include<iostream> #include<cassert> #include<atcoder/modint> #include<atcoder/convolution> using namespace std; #include<vector> template<typename T> struct combination{ vector<T>fac,ifac; combination(size_t N=0):fac(1,1),ifac(1,1) { make_table(N); } void make_table(size_t N) { if(fac.size()>N)return; size_t now=fac.size(); N=max(N,now*2); fac.resize(N+1); ifac.resize(N+1); for(size_t i=now;i<=N;i++)fac[i]=fac[i-1]*i; ifac[N]=1/fac[N]; for(size_t i=N;i-->now;)ifac[i]=ifac[i+1]*(i+1); } T factorial(size_t n) { make_table(n); return fac[n]; } T invfac(size_t n) { make_table(n); return ifac[n]; } T P(size_t n,size_t k) { if(n<k)return 0; make_table(n); return fac[n]*ifac[n-k]; } T C(size_t n,size_t k) { if(n<k)return 0; make_table(n); return fac[n]*ifac[n-k]*ifac[k]; } T H(size_t n,size_t k) { if(n==0)return k==0?1:0; return C(n-1+k,k); } }; using mint=atcoder::modint998244353; combination<mint>C; int N,Q; vector<mint>A; mint inv[2020]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>N>>Q; for(int i=1;i<=N;i++)inv[i]=mint::raw(i).inv(); A.resize(N); for(int i=0;i<N;i++) { int a;cin>>a; A[i]=mint::raw(a); } for(;Q--;) { int o;cin>>o; if(o==1) { int k,x;cin>>k>>x; vector<mint>F(N); //1,1,1,1,1 //1,2,3,4,5 //1,3,6,10,15 mint c=1; for(int i=0;i<N;i++) { //F[i]=C.C(i+x-1,i); F[i]=c; c=c*mint::raw(k)*mint(x+i)*inv[i+1]; //mint(i+1).inv(); } A=atcoder::convolution(A,F); A.resize(N); } else { int x;cin>>x; cout<<A[x-1].val()<<"\n"; } } }