結果

問題 No.3123 Inversion
ユーザー Takao Obi
提出日時 2025-04-19 13:20:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,880 bytes
コンパイル時間 2,441 ms
コンパイル使用メモリ 197,656 KB
実行使用メモリ 261,156 KB
最終ジャッジ日時 2025-04-19 13:21:08
合計ジャッジ時間 30,258 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other AC * 2 WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

    int T;
    ll 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]);
    }

    // 1) factorial
    vector<ll> fact(maxN+1, 0);
    fact[0] = 1;
    for(int i = 1; i <= maxN; i++){
        fact[i] = fact[i-1] * i % M;
    }

    // 2) involution numbers a[n]
    vector<ll> a(maxN+1, 0);
    a[0] = 1; 
    if(maxN >= 1) a[1] = 1;
    for(int n = 2; n <= maxN; n++){
        a[n] = (a[n-1] + (ll)(n-1) * a[n-2]) % M;
    }

    // 3) central-symmetric count c[n] = (floor(n/2))! * 2^{floor(n/2)} mod M
    vector<ll> c(maxN+1, 0), pow2(maxN+1, 0);
    pow2[0] = 1;
    for(int i = 1; i <= maxN; i++){
        pow2[i] = (pow2[i-1] * 2) % M;
    }
    // we also need factorial up to floor(maxN/2)
    int half = maxN/2;
    vector<ll> fact_half(half+1,0);
    fact_half[0] = 1;
    for(int i = 1; i <= half; i++){
        fact_half[i] = fact_half[i-1] * i % M;
    }
    for(int n = 0; n <= maxN; n++){
        int m = n/2;
        c[n] = fact_half[m] * pow2[m] % M;
    }

    // 4) intersection count d[n] = 2^{floor(n/2)} mod M
    vector<ll> d(maxN+1, 0);
    for(int n = 0; n <= maxN; n++){
        d[n] = pow2[n/2];
    }

    // 5) まとめて S[n] を計算
    //    S[0]=1, S[1]=1, S[2]=4 (検算済み)
    vector<ll> S(maxN+1, 0);
    if(maxN >= 0) S[0] = 1 % M;
    if(maxN >= 1) S[1] = 1 % M;
    if(maxN >= 2) S[2] = 4 % M;
    for(int n = 3; n <= maxN; n++){
        ll v = (8LL * fact[n]) % M;
        v = (v - 4LL * a[n] % M + M) % M;
        v = (v - 8LL * c[n] % M + M) % M;
        v = (v + 2LL * d[n] % M) % M;
        S[n] = v;
    }

    // 出力
    for(int n : Ns){
        cout << S[n] << "\n";
    }
    return 0;
}
0