提出 #5074666

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;

const int64_t MOD = 998244353;
void add(int64_t& a, int64_t b){
    a = (a+b) % MOD;
}
void mul(int64_t& a, int64_t b){
    a = (a*b) % MOD;
}

vector<int64_t> fact, seq_inv, fact_inv;

void create_fact_mod(int num){
    fact[0] = 1;
    fact[1] = 1;
    for(int i=2; i<=num; i++){
        fact[i] = fact[i-1] * i % MOD;
    }
}

void create_seq_inv_mod(int num){
    seq_inv[0] = 1;
    seq_inv[1] = 1;
    for(int i=2; i<=num; i++){
        seq_inv[i] = (MOD - MOD/i) * seq_inv[MOD%i] % MOD;
    }
}

void create_fact_inv_mod(int num){
    fact_inv[0] = 1;
    fact_inv[1] = 1;
    for(int i=2; i<=num; i++){
        fact_inv[i] = fact_inv[i-1] * seq_inv[i] % MOD;
    }
}

void create_mod_tables(int num){
    fact.resize(num+1);
    seq_inv.resize(num+1);
    fact_inv.resize(num+1);
    create_fact_mod(num);
    create_seq_inv_mod(num);
    create_fact_inv_mod(num);
}

int64_t comb_mod(int n, int k){
    return fact[n] * fact_inv[n-k] % MOD * fact_inv[k] % MOD;
}

int64_t perm_mod(int n, int k){
    return fact[n] * fact_inv[n-k] % MOD;
}

int main(){
    int N, X;
    cin >> N >> X;
    create_mod_tables(6010);

    static int64_t dp[3001][6010], dp2[3001][6010];
    dp[0][0] = 1;
    dp2[0][0] = 1;
    for(int i=0; i<N; i++) for(int j=0; j<=2*N; j++){
        for(int k=0; k<=2; k++) add(dp[i+1][j+k], dp[i][j]);
        for(int k=1; k<=2; k++) add(dp2[i+1][j+k], dp2[i][j]);
    }
    int64_t ans = 0;
    for(int j=0; j<X; j++) add(ans, dp[N][j]);

    for(int y=1; X+y<=2*N; y+=2){
        if(y+1 < X-1){
            for(int n=1; n+y+1<=N; n++){
                int64_t result = dp2[n][X-y-2];
                mul(result, comb_mod(N, n+y+1));
                add(ans, result);
            }
        }else{
            if(X%2) add(ans, comb_mod(N, (X+y)/2));
        }
    }
    cout << ans << endl;
    return 0;
}

提出情報

ジャッジ結果