結果

問題 No.2633 Subsequence Combination Score
ユーザー 👑 potato167
提出日時 2025-04-17 11:22:26
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,216 bytes
コンパイル時間 3,669 ms
コンパイル使用メモリ 239,760 KB
実行使用メモリ 25,700 KB
最終ジャッジ日時 2025-04-17 11:22:36
合計ジャッジ時間 8,898 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other TLE * 1 -- * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/convolution>
using namespace std;
using ll = long long;
const int MOD = 998244353;
 
// fast power mod
ll modpow(ll a, ll e=MOD-2){
    ll r=1;
    while(e){
        if(e&1) r=r*a%MOD;
        a=a*a%MOD;
        e>>=1;
    }
    return r;
}
 
// precompute factorials up to MAXA, and invfact
static const int MAXA = 100000;
ll fact[MAXA+1], invfact[MAXA+1];
inline ll C(int n,int k){
    if(k<0 || k>n) return 0;
    return fact[n]*invfact[k]%MOD*invfact[n-k]%MOD;
}
 
vector<int> A;
vector<ll> dp, tmp;  // dp[x]: 現在までの累積 dp 値、tmp は CDQ用
 
// CDQ 区間 [l, r) で更新
void cdq(int l,int r){
    if(r-l<=1) return;
    int m=(l+r)/2;
    // 左半分で再帰
    cdq(l,m);
    // 左半分の dp 増分を使って右半分 tmp を更新
    // we want for each j in [m,r) sum_{i in [l,m)} dp[i] * C(A[i], A[j]) over those A[i] >= A[j]
    // group by value v = A[j], gather all i's and j's
    // build f,g sequences of length MAXA+1: f[v] = sum dp[i] for i in [l,m) with A[i]=v
    // g[v] = C(v, k) for k = A[j]
    vector<ll> f(MAXA+1,0), g(MAXA+1,0);
    for(int i=l;i<m;i++) f[A[i]] = (f[A[i]] + dp[i])%MOD;
    // prefix sum on f: F[v] = sum_{u>=v} f[u]
    for(int v=MAXA-1;v>=0;v--) f[v]=(f[v]+f[v+1])%MOD;
    // build G[k][v]=C(v,k), but we only need for k = A[j]
    // instead: for fixed k we need G_k[v] = C(v,k) for v>=k else 0.
    // We will do convolution of F (length MAXA+1) and H where H[u]=C(u,k) for u<=MAXA.
    // But since k varies per j, we cannot do single convolution: instead we do for each distinct k group all j.
    // For simplicity, do naive inner for distinct k in [m,r):
    unordered_map<int, vector<int>> pos;
    for(int j=m;j<r;j++) pos[A[j]].push_back(j);
    for(auto &kv : pos){
        int k = kv.first;
        auto &vec = kv.second;
        // build h[v]=C(v,k) for v=0..MAXA
        for(int v=0;v<=MAXA;v++){
            g[v] = C(v,k);
        }
        // convolution of f and g
        auto conv = atcoder::convolution(f, g);
        // conv[v + u] contains sum f[u]*g[v], but we want for each j: sum_{v>=k} F[v]*C(v,k)
        // Actually, conv index i = u+v. We need for each j:
        // sum_{u>=0} F[u] * C(u,k) = conv[k]
        ll val = (k < (int)conv.size() ? conv[k] : 0);
        for(int j : vec){
            tmp[j] = (tmp[j] + val) % MOD;
        }
    }
    // 右半分 dp に反映
    for(int i=m;i<r;i++){
        dp[i] = (dp[i] + tmp[i]) % MOD;
    }
    fill(tmp.begin()+m, tmp.begin()+r, 0);
    // 右半分再帰
    cdq(m,r);
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N;
    cin >> N;
    A.resize(N);
    for(int i=0;i<N;i++) cin >> A[i];
    // 前処理
    fact[0]=1;
    for(int i=1;i<=MAXA;i++) fact[i]=fact[i-1]*i%MOD;
    invfact[MAXA]=modpow(fact[MAXA]);
    for(int i=MAXA;i>0;i--) invfact[i-1]=invfact[i]*i%MOD;
 
    dp.assign(N, 0);
    tmp.assign(N, 0);
    // 初期状態：長さ1 の部分列それぞれ f=1
    for(int i=0;i<N;i++) dp[i]=1;
    // CDQ 全体
    cdq(0, N);
 
    // 答えは dp の総和
    ll ans = 0;
    for(int i=0;i<N;i++) ans = (ans + dp[i]) % MOD;
    cout << ans << "\n";
    return 0;
}
0