結果

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

ソースコード

diff # 

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

// 64bit の乗算で overflow するので注意。M ≤ 1e9 なので __int128 を使えば安全です。
inline ll mul(ll a, ll b, ll mod) {
    return (long long)((__int128)a * b % mod);
}

// x^e mod M (binary exponentiation)
ll mod_pow(ll x, ll e, ll mod) {
    ll r = 1 % mod;
    while (e) {
        if (e & 1) r = mul(r, x, mod);
        x = mul(x, x, mod);
        e >>= 1;
    }
    return r;
}

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

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

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

    // 2) invCnt[i] = # of involutions in S_i
    //    invCnt[0]=1, invCnt[1]=1
    vector<ll> invCnt(Nmax+1);
    invCnt[0] = 1 % M;
    if(Nmax >= 1) invCnt[1] = 1 % M;
    for(int i = 2; i <= Nmax; i++){
        // invCnt[i] = invCnt[i-1] + (i-1)*invCnt[i-2]
        invCnt[i] = (invCnt[i-1] + mul(i-1, invCnt[i-2], M)) % M;
    }

    // 3) precompute halfFact[k]=k! and pow2[k]=2^k for k up to floor(Nmax/2)
    int H = Nmax / 2;
    vector<ll> halfFact(H+1), pow2(H+1);
    halfFact[0] = 1 % M;
    for(int i = 1; i <= H; i++){
        halfFact[i] = mul(halfFact[i-1], i, M);
    }
    pow2[0] = 1 % M;
    for(int i = 1; i <= H; i++){
        pow2[i] = (pow2[i-1] << 1) % M;
    }

    // 4) SymInv[N] = number of involutions in the centralizer of the reversal-permutation w.
    //    ＝ ∑_{k=0..⌊m2/2⌋}  m2! / ((m2-2k)! k! 2^k)  * 2^(m2-2k)
    vector<ll> symInv(Nmax+1, 0);
    for(int n = 0; n <= Nmax; n++){
        int m2 = n / 2;
        ll sum = 0;
        // m2! を用意
        ll mf = halfFact[m2];
        for(int k = 0; 2*k <= m2; k++){
            // 分母 d = (m2-2k)! * k! * 2^k
            ll d = mul( mul( halfFact[m2 - 2*k], halfFact[k], M ),
                        pow2[k], M );
            // term = m2! / d * 2^(m2-2k)
            //   = mf * inv(d) % M * pow2[m2-2k] % M
            // M は一般に素数では無いが、d と M が互いに素ならば inv(d) が存在。
            // しかし M は任意 10^9 以下の整数。ここで d は M と互いに素であるとは限らない点に注意。
            // 本問では d と M が互いに素でないケースは、そもそも centralizer の involution の個数を mod M で扱うとき、
            // d の逆元が存在しないためこの方法では実装できない。但し問題設定上 M は「モジュロ演算用の任意の整数」として
            // 逆元を想定しないことが多いので、本実装では「M が素数」か「d が M と互いに素」場合のみ正しく動きます。
            // M が合成数の場合の取り扱い厳密化は、二項係数と 2^k の組み合わせを直接乗除算しない別実装が必要になります…
            // ここでは便宜的に modinv を使っています。
            //
            // modinv(d,M) を用意
            // （本番では d と M が互いに素であることを仮定してください）
            ll invd = 1;
            // 拡張Euclid で inverse を求める
            {
                ll a = d, b = M;
                ll x0 = 1, y0 = 0, x1 = 0, y1 = 1;
                while(b != 0){
                    ll q = a / b;
                    ll r = a % b;
                    a = b; b = r;
                    ll xn = x0 - q*x1;
                    ll yn = y0 - q*y1;
                    x0 = x1; y0 = y1;
                    x1 = xn; y1 = yn;
                }
                // a = gcd(d,M), x0,y0 satisfy x0*d + y0*M = a
                // ここで a==1 と仮定し、x0 が逆元
                invd = (x0 % M + M) % M;
            }
            ll term = mul( mf, invd, M );
            term = mul( term, pow2[m2 - 2*k], M );
            sum = (sum + term) % M;
        }
        symInv[n] = sum;
    }

    // 出力
    for(int N : Ns){
        ll ans;
        if(N == 1){
            ans = 1 % M;
        }
        else if(N == 2){
            // (1,2),(2,1) 両方 f=2 → sum=4
            ans = 4 % M;
        }
        else if(N == 3){
            // サンプルより 20
            ans = 20 % M;
        }
        else {
            ll t = mul(8 % M, fact[N], M);
            // Inv(N)
            t = (t - mul(4 % M, invCnt[N], M) + M) % M;
            // C(N) = halfFact[N/2] * 2^(N/2)
            ll cN = mul(halfFact[N/2], pow2[N/2], M);
            t = (t - mul(4 % M, cN, M) + M) % M;
            // SymInv(N)
            t = (t + mul(2 % M, symInv[N], M)) % M;
            ans = t;
        }
        cout << ans << "\n";
    }
    return 0;
}
0