結果

問題 No.3045 反復重み付き累積和
コンテスト
ユーザー houren
提出日時 2025-03-01 00:57:22
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 4,741 ms / 5,000 ms
コード長 3,795 bytes
コンパイル時間 5,476 ms
コンパイル使用メモリ 319,928 KB
実行使用メモリ 8,236 KB
最終ジャッジ日時 2025-03-01 00:58:24
合計ジャッジ時間 61,785 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <bits/stdc++.h>
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/convolution>
using namespace atcoder;
using mint = modint998244353;
using ll = long long;
#define fix(x) fixed << setprecision(x)
#define rep(i, n) for(int i = 0; i < n; ++i)
#define all(x) (x).begin(),(x).end()
template<class T>bool chmin(T&a, const T&b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool chmax(T&a, const T&b){if(a<b){a=b;return 1;}return 0;}
constexpr ll INFLL = (1LL << 62), MOD = 998244353;
constexpr int INF = (1 << 30);
vector<mint> fps_inv(const vector<mint>& f, int n = -1){
    assert(f.size());
    assert(f[0].val()!=0);
    if(n<0) n = f.size();
    vector<mint> g(1,f[0].inv());
    int t = 1, d = f.size();
    while(t<n){
        t <<= 1;
        auto g_ = g;
        g = convolution(convolution(vector<mint>(f.begin(), f.begin()+min(t,d)), g), g);
        g.resize(t);
        for(int i=0;i<t;++i) g[i] = -g[i];
        for(int i=0;i<(t>>1);++i) g[i] += 2*g_[i];
    }
    g.resize(n);
    return g;
}

vector<mint> fps_log(const vector<mint>& f, int n = -1){
    assert(f.size());
    assert(f[0].val()==1);
    if(n<0) n = f.size();
    int d = f.size();
    auto g = f;
    for(int i=1;i<d;++i) g[i-1] = g[i] * i;
    g[d-1] = 0;
    g = convolution(g, fps_inv(f, n));
    vector<mint> inv(n+2);
    inv[0] = inv[1] = 1;
    int mod = mint::mod();
    for(int i=2;i<n;++i) inv[i] = mod - inv[mod%i] * (mod/i);
    for(int i=n-1;i>=1;--i) g[i] = g[i-1] * inv[i];
    g[0] = 0;
    return g;
}

vector<mint> fps_exp(const vector<mint>& f, int n = -1){
    assert(f.size());
    assert(!f[0].val());
    if(n<0) n = f.size();
    int t = 1, d = f.size();
    vector<mint> g(1,1);
    while(t<n){
        t <<= 1;
        auto g_ = fps_log(g, t);
        for(mint& x:g_) x = -x;
        for(int i=0;i<min(t,d);++i) g_[i] += f[i];
        g_[0] += 1;
        g = convolution(g, g_);
        g.resize(t);
    }
    g.resize(n);
    return g;
}

vector<mint> fps_pow(vector<mint> f, long long m, int n = -1){
    assert(f.size() && m>=0);
    int d = f.size(), x = 0;
    if(n<0) n = (d-1) * m + 1;
    if(m==0){
        vector<mint> res(n,0);
        res[0] = 1;
        return res;
    }
    while(x<d && f[x].val()==0) ++x;
    if(x==d || (n+m-1)/m<=x) return vector<mint>(n,0);
    mint y = f[x], z = y.inv();
    y = y.pow(m);
    for(int i=x;i<d;++i) f[i] *= z;
    f = fps_log(vector<mint>(f.begin()+x, f.end()), n-x*m);
    for(mint& k:f) k *= m;
    f = fps_exp(f);
    for(mint& k:f) k *= y;
    vector<mint> g(n,0);
    for(int i=0,j=x*m;j<n;++i,++j) g[j] = f[i];
    return g;
}
mint BostanMori(vector<mint> f, vector<mint> g, ll k){
    vector<mint> g_, s, t;
    int m;
    while(k){
        m = g.size();
        g_ = g;
        for(int i=1;i<m;i+=2) g_[i] = -g_[i];
        s = convolution(f, g_), t = convolution(g, g_);
        f.resize(min<ll>(k+1, (s.size()+1-(k&1))>>1));
        g.resize(min<ll>(k+1, (t.size()+1)>>1));
        for(int i=k&1;i<(int)s.size()&&((i>>1)<=k);i+=2) f[i>>1] = s[i];
        for(int i=0;i<(int)t.size()&&((i>>1)<=k);i+=2) g[i>>1] = t[i];
        k >>= 1;
    }
    return f[0] / g[0];
}
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,q;
    cin >> n >> q;
    vector<mint> a(n), b(n,0);
    b[0] = 1;
    rep(i,n){
        int x;
        cin >> x;
        a[i] = x;
    }
    while(q--){
        int t;
        cin >> t;
        if(t==1){
            int k,x;
            cin >> k >> x;
            vector<mint> c(2);
            c[0] = 1, c[1] = -k;
            b = convolution(b, fps_pow(c, x, n));
            b.resize(n);
        }else{
            int x;
            cin >> x;
            cout << BostanMori(a,b,x-1).val() << '\n';
        }
    }
    return 0;
}
0