結果

問題 No.3123 Inversion
ユーザー kenken714
提出日時 2025-03-19 03:37:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,640 bytes
コンパイル時間 3,507 ms
コンパイル使用メモリ 192,496 KB
実行使用メモリ 792,048 KB
最終ジャッジ日時 2025-04-18 00:20:47
合計ジャッジ時間 31,917 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other MLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

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], c3[MAX_N + 10], c4[MAX_N + 10], c5[MAX_N + 10], c6[MAX_N + 10], c7[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;

        // c3
        c3[N] = dp1[N / 2];

        // c4
        c4[N] = (pow2[N / 2] * fact[N / 2] % mod - c2[N] - c3[N] + mod * 2) % mod;

        // c5 = c6
        c5[N] = c6[N] = (dp2[N] - c3[N] + mod) % mod;

        //c7
        c7[N] = (fact[N] - c2[N] - c3[N] - c4[N] - c5[N] - c6[N] + mod * 5) % mod;
    }
}

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