結果

問題 No.3123 Inversion
ユーザー Kevgen
提出日時 2025-04-19 16:25:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,734 bytes
コンパイル時間 2,521 ms
コンパイル使用メモリ 197,048 KB
実行使用メモリ 80,548 KB
最終ジャッジ日時 2025-04-19 16:25:38
合計ジャッジ時間 23,312 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other AC * 5 WA * 16
権限があれば一括ダウンロードができます

ソースコード

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> N(T);
    int Nmax = 0;
    for(int i = 0; i < T; i++){
        cin >> N[i];
        Nmax = max(Nmax, N[i]);
    }

    // 1) factorials fac[n] = n! mod M
    vector<int> fac(Nmax+1,1);
    for(int i = 1; i <= Nmax; i++){
        fac[i] = int((int64)fac[i-1] * i % M);
    }

    // 2) number of involutions A[n]: A[0]=A[1]=1, A[n]=A[n-1] + (n-1)*A[n-2]
    vector<int> A(Nmax+1,0);
    A[0] = 1 % M;
    if(Nmax >= 1) A[1] = 1 % M;
    for(int n = 2; n <= Nmax; n++){
        A[n] = A[n-1] + int((int64)(n-1) * A[n-2] % M);
        if(A[n] >= M) A[n] -= M;
    }

    // 3) K[j] = # of involutions commuting with the "half‑turn" on 2j points
    //    Exponential generating fn: e^{2y + y^2} => recurrence
    //    K[0]=1, K[1]=2,  K[j+1] = (2*K[j] + 2*j*K[j-1]) mod M
    int Jmax = Nmax/2;
    vector<int> K(Jmax+1,0);
    K[0] = 1 % M;
    if(Jmax >= 1) K[1] = 2 % M;
    for(int j = 1; j < Jmax; j++){
        // careful with 64‑bit intermediate
        int64 v = 2LL * K[j] + 2LL * j * K[j-1];
        K[j+1] = int(v % M);
    }

    // 4) powers of two
    vector<int> pow2(Nmax+1,1);
    for(int i = 1; i <= Nmax; i++){
        pow2[i] = pow2[i-1] * 2;
        if(pow2[i] >= M) pow2[i] -= M * (pow2[i] / M);
    }

    // 5) B_steps[u] = (2u)! / u!  for u=0..Nmax/4, via B_steps[u] = B_steps[u-1] * (4u-2)
    int Umax = Nmax/4;
    vector<int> Bsteps(Umax+1,1);
    for(int u = 1; u <= Umax; u++){
        // (2u)!/u! = ( (2u-2)!/(u-1)! ) * ((2u-1)*(2u)/u) = Bsteps[u-1] * (4u-2)
        int64 mul = int64(4LL*u - 2);
        Bsteps[u] = int( (int64)Bsteps[u-1] * mul % M );
    }

    // now answer
    // formula for N>=2:
    //   S(N) = 8*n!   - 8*A[N]   - 2*B[N]   - 4*C[N]   + 6*K[floor(N/2)]
    // C[N] = 2^{floor(N/2)} * (floor(N/2))!   (and for N=1, S=1)
    for(int n: N){
        if(n == 1){
            cout << 1%M << "\n";
            continue;
        }
        int64 E = fac[n];                     // n!
        int64 a = A[n];                       // A[n]
        int64 b = 0;                          // B[n]
        if(n % 4 == 0){
            b = Bsteps[n/4];
        }
        int m2 = n/2;
        int64 c = (int64)pow2[m2] * fac[m2] % M; // C[n]
        int64 k = K[m2];                       // k[n] = K[floor(n/2)]

        int64 ans = 0;
        ans = (ans + 8LL * E) % M;
        ans = (ans - 8LL * a) % M;
        ans = (ans - 2LL * b) % M;
        ans = (ans - 4LL * c) % M;
        ans = (ans + 6LL * k) % M;
        if(ans < 0) ans += M;
        cout << ans << "\n";
    }

    return 0;
}
0