結果

問題 No.3123 Inversion
ユーザー keigo kuwata
提出日時 2025-04-23 09:09:26
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,669 bytes
コンパイル時間 2,082 ms
コンパイル使用メモリ 194,596 KB
実行使用メモリ 56,040 KB
最終ジャッジ日時 2025-04-23 09:09:46
合計ジャッジ時間 20,051 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other AC * 1 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    int M;
    cin >> T >> M;
    vector<int> Ns(T);
    int maxN = 0;
    for(int i = 0; i < T; i++){
        cin >> Ns[i];
        maxN = max(maxN, Ns[i]);
    }

    // 特殊ケース N=1 だけ別扱い
    // N>=2 は以下の前処理で対応
    int N = maxN;
    vector<int> fac(N+1), invcount(N+1);
    int half = N/2;
    vector<int> g(half+1);

    // 階乗 mod M
    fac[0] = 1;
    for(int i = 1; i <= N; i++){
        fac[i] = int( (int64)fac[i-1] * i % M );
    }
    // Inv(n) の前処理 (自己逆置換の数)
    invcount[0] = 1;
    if(N >= 1) invcount[1] = 1;
    for(int i = 2; i <= N; i++){
        invcount[i] = int((invcount[i-1] + (int64)(i-1) * invcount[i-2]) % M);
    }
    // g[k] の前処理 (反転置換と可換な互換置換の数)
    // g[0]=1, g[1]=2, g[k]=2*g[k-1] + 2*(k-1)*g[k-2]
    g[0] = 1;
    if(half >= 1) g[1] = 2 % M;
    for(int k = 2; k <= half; k++){
        g[k] = int(( 2LL * g[k-1]
                   + 2LL * (k-1) % M * g[k-2] ) % M);
    }

    // 各クエリを O(1) で回答
    // N=1 の場合だけ f(id)=1 固定
    for(int i = 0; i < T; i++){
        int n = Ns[i];
        if(n == 1){
            cout << 1 << "\n";
            continue;
        }
        int64 res = 0;
        // 8 * n!
        res += 8LL * fac[n] % M;
        // -8 * Inv(n)
        res = (res - 8LL * invcount[n]) % M;
        // +2 * g[floor(n/2)]
        res = (res + 2LL * g[n/2]) % M;

        if(res < 0) res += M;
        cout << res << "\n";
    }

    return 0;
}
0