結果

問題 No.3123 Inversion
コンテスト
ユーザー kenken714
提出日時 2025-03-28 14:25:52
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,580 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 17,470 ms
コンパイル使用メモリ 215,324 KB
実行使用メモリ 198,844 KB
最終ジャッジ日時 2025-04-18 00:22:04
合計ジャッジ時間 30,427 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

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

#define ll long long

const ll MAX_N = 5000000;
ll M;
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] % M;

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

        // 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] % M) % M;

        // 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] % M) % M;

        // 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] % M;
        else if(N % 4 == 1) c2[N] = (N - 3) * c2[N - 4] % M;
        else c2[N] = 0;
    }
}

int main(){
	ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
    int T;
    cin >> T >> M;
    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] % M - c2[N] - c3 + M * 2) % M;
        ll c5 = (dp2[N] - c3 + M) % M;
        ll c6 = c5;
        ll c7 = (fact[N] - c2[N] - c3 - c4 - c5 - c6 + M * 5) % M;
        cout << (2 * (c2[N] + c3) + 4 * (c4 + c5 * 2) + 8 * c7) % M << "\n";
    }
}
0