結果

問題 No.3123 Inversion
ユーザー Kevgen
提出日時 2025-04-19 16:12:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,858 bytes
コンパイル時間 2,382 ms
コンパイル使用メモリ 200,844 KB
実行使用メモリ 144,036 KB
最終ジャッジ日時 2025-04-19 16:13:16
合計ジャッジ時間 39,378 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other AC * 1 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// fast modular arithmetic
static int add(int a, int b, int M){ a+=b; if(a>=M) a-=M; return a; }
static int sub(int a, int b, int M){ a-=b; if(a<0) a+=M; return a; }
static int64 mul(int64 a, int64 b, int M){ return (a*b) % M; }
static int64 modpow(int64 x, int64 e, int M) {
    int64 r=1%M, y=x%M;
    while(e){ if(e&1) r=(r*y)%M; y=(y*y)%M; e>>=1; }
    return r;
}

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

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

    // Precompute factorials and inv‐factorials mod M:
    vector<int> fac(Nmax+1, 1);
    for(int i=1;i<=Nmax;i++)
        fac[i] = int(mul(fac[i-1], i, M));

    // Precompute 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] = add( A[n-1], int(mul(n-1, A[n-2], M)), M );
    }

    // Precompute B[n] = floor(n/2) even?    B[n] = (t)! / (t/2)! else 0
    vector<int> B(Nmax+1, 0);
    // We need factorials up to Nmax/2 and inverse factorials if M not prime
    // but here we only divide factorials by factorial (t/2)!; M may be non‐prime so we do it by
    // building up via B[n] = B[n-2] * (n/2) * (n/2 - 1) ... accordingly.
    B[0] = 1 % M;  // by convention
    for(int n=1;n<=Nmax;n++){
        int t = n/2;
        if(t%2==0){
            // B[n] = fac[t] * inv( fac[t/2] ) mod M
            // we'll just do fac[t] * modinv(fac[t/2])
            // since M up to 1e9 (not prime), we can precompute invs by extended gcd if needed.
            // For simplicity, we'll precompute all inverses by egcd:
            static vector<int64> invFac; 
            if(invFac.empty()){
                invFac.resize(Nmax+1);
                // compute invFac[i] = inv( fac[i] ) mod M via extended‐gcd
                auto exgcd = [&](auto self, int64 a, int64 b, int64 &x, int64 &y)->int64 {
                    if(!b){ x=1; y=0; return a; }
                    int64 x1,y1;
                    int64 g = self(self, b, a%b, x1, y1);
                    x = y1;
                    y = x1 - (a/b)*y1;
                    return g;
                };
                for(int i=0;i<=Nmax;i++){
                    int64 x,y;
                    int64 g = exgcd(exgcd, fac[i], M, x, y);
                    // Since fac[i] and M may not be coprime, but in every test
                    // fac[t/2] will be invertible for our ranges (by constraints),
                    // we assume g==1 here.
                    x %= M; if(x<0) x += M;
                    invFac[i] = x;
                }
            }
            B[n] = int( mul( fac[t], invFac[t/2], M ) );
        } else {
            B[n] = 0;
        }
    }

    // Precompute C[n] = m1! * 2^{m2} * m2! mod M
    vector<int> C(Nmax+1, 0), pow2(Nmax+1,1);
    for(int i=1;i<=Nmax;i++) pow2[i] = add(pow2[i-1], pow2[i-1], M);
    for(int n=0;n<=Nmax;n++){
        int m1 = n & 1;
        int m2 = n >> 1;
        int64 v = fac[m1];
        v = (v * pow2[m2]) % M;
        v = (v * fac[m2]) % M;
        C[n] = int(v);
    }

    // Now answer each query:
    //   S(N) = 8*N! - 4*A[N] - 2*B[N] - 2*C[N]   (for N>=2),  S(1)=1
    for(int n: Ns){
        if(n==1){
            cout << 1 << "\n";
        } else {
            int64 res = 0;
            // 8*N!
            res = (res + 8LL * fac[n]) % M;
            // -4*A[n]
            res = (res - 4LL * A[n]) % M;
            // -2*B[n]
            res = (res - 2LL * B[n]) % M;
            // -2*C[n]
            res = (res - 2LL * C[n]) % M;
            if(res<0) res += M;
            cout << res << "\n";
        }
    }
    return 0;
}
0