結果

問題 No.3123 Inversion
コンテスト
ユーザー kenken714
提出日時 2025-03-19 03:46:15
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,473 bytes
コンパイル時間 3,689 ms
コンパイル使用メモリ 191,448 KB
実行使用メモリ 394,160 KB
最終ジャッジ日時 2025-04-18 00:19:27
合計ジャッジ時間 124,598 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 1
other WA * 3 RE * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define ll long long

const ll MAX_N = 10000000, mod = 998244353;
ll dp1[MAX_N + 10], dp2[MAX_N + 10];
ll c2[MAX_N + 10];
ll pow2[MAX_N + 10]; //2^N
ll fact[MAX_N + 10]; //N!

void solve(){
    pow2[0] = 1;
    fact[0] = 1;
    for(ll N = 1; N <= MAX_N; N++) {
        // 2^N
        pow2[N] = 2 * pow2[N - 1] % mod;

        // N!
        fact[N] = N * fact[N - 1] % mod;

        // dp1
        if(N == 1) dp1[N] = 2;
        else if(N == 2) dp1[N] = 6;
        else dp1[N] = 2 * (dp1[N - 1] + (N - 1) * dp1[N - 2] % mod) % mod;

        // dp2
        if(N == 1) dp2[N] = 1;
        else if(N == 2) dp2[N] = 2;
        else dp2[N] = (dp2[N - 1] + (N - 1) * dp2[N - 2] % mod) % mod;

        // c2
        if(N == 1) c2[N] = 1;
        else if(N == 4) c2[N] = 2;
        else if(N % 4 == 0) c2[N] = (N - 2) * c2[N - 4] % mod;
        else if(N % 4 == 1) c2[N] = (N - 3) * c2[N - 4] % mod;
        else c2[N] = 0;
    }
}

int main(){
    int T;
    cin >> T;
    solve();
    while(T--){
        int N;
        cin >> N;
        if(N == 1){
        cout << 1 << "\n";
        continue;
        }
        ll c3 = dp1[N / 2];
        ll c4 = (pow2[N / 2] * fact[N / 2] % mod - c2[N] - c3 + mod * 2) % mod;
        ll c5 = (dp2[N] - c3 + mod) % mod;
        ll c6 = c5;
        ll c7 = (fact[N] - c2[N] - c3 - c4 - c5 - c6 + mod * 5) % mod;
        cout << (2 * (c2[N] + c3) + 4 * (c4 + c5 * 2) + 8 * c7) % mod << "\n";
    }
}
0