結果

問題 No.3123 Inversion
ユーザー kenken714
提出日時 2025-04-18 00:04:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,443 ms / 10,000 ms
コード長 1,417 bytes
コンパイル時間 3,325 ms
コンパイル使用メモリ 192,112 KB
実行使用メモリ 198,912 KB
最終ジャッジ日時 2025-04-18 00:17:41
合計ジャッジ時間 55,686 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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(){
    int T;
    cin >> T >> M;
    solve();
    while(T--){
        int N;
        cin >> N;
		ll ans;
        if(N == 1){
        	ans = 1;
        }
		else {
			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;
			ans = (2 * (c2[N] + c3) + 4 * (c4 + c5 * 2) + 8 * c7) % M;
		}
		cout << ans % M << endl;
    }
}
0