結果

問題 No.2378 Cards and Subsequences
ユーザー pockyny
提出日時 2025-09-02 07:09:38
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 484 ms / 2,000 ms
コード長 1,434 bytes
コンパイル時間 2,580 ms
コンパイル使用メモリ 117,840 KB
実行使用メモリ 66,944 KB
最終ジャッジ日時 2025-09-02 07:09:53
合計ジャッジ時間 15,442 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <atcoder/modint>
#include <atcoder/convolution>

using namespace std;
using namespace atcoder;
using mint = modint998244353;
int pre[2010],s[2010],a[2010],b[2010];
vector<mint> dp[2010],sum[2010];
vector<mint> f[2010];
vector<int> pos[2010];
int main(){
    int i,j,n,m,k; cin >> n >> m >> k;
    for(i=0;i<m;i++) pos[i].push_back(0);
    for(i=1;i<=n;i++){
        cin >> s[i]; s[i]--;
        pre[i] = pos[s[i]].back();
        pos[s[i]].push_back(i);
    }
    for(i=0;i<m;i++) cin >> a[i];
    for(i=0;i<m;i++) cin >> b[i];
    for(i=0;i<m;i++){
        if(a[i]>b[i]) swap(a[i],b[i]);
        f[i].resize(b[i] + 1);
        f[i][a[i]]++; f[i][b[i]]++;
    }
    for(i=0;i<=n + 1;i++) sum[i].resize(k + 1);
    dp[0] = {1};
    sum[0][0] = 0; sum[1][0] = 1;
    for(i=1;i<=n;i++){
        vector<mint> F(k + 1);
        for(j=0;j<=k;j++){
            F[j] = sum[i][j] - sum[pre[i]][j];
        }
        dp[i] = convolution(F,f[s[i]]);
        dp[i].resize(k + 1);
        for(j=0;j<=k;j++) sum[i + 1][j] = sum[i][j] + dp[i][j];
    }
    mint ans = 0;
    for(i=1;i<=n;i++) ans += dp[i][k];
    cout << ans.val() << "\n";
    // for(i=0;i<=n;i++){
    //     for(j=0;j<=k;j++){
    //         cout << dp[i][j].val() << "x^" << j;
    //         if(j<k) cout << "+";
    //     }
    //     cout << "\n";
    // }
    // for(i=1;i<=n;i++) cout << pre[i] << " ";
    // cout << "\n";
}
0