#1083965 (C++17) No.2048 L(I+D)S

• 問題: No.2048 L(I+D)S
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:11:33
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 7 ms / 2,000 ms
• コード長: 6,236 bytes
• コンパイル時間: 728 ms
• コンパイル使用メモリ: 70,632 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2025-05-14 13:13:16
• 合計ジャッジ時間: 1,562 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

ファイルパターン	結果
sample	AC * 3
other	AC * 16

ソースコード

#include <iostream>
#include <vector>

// Define the modulus
const long long MOD = 998244353;

// Function for modular exponentiation (calculates base^exp % MOD)
// Used for calculating modular inverse via Fermat's Little Theorem
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// Function to calculate modular inverse using Fermat's Little Theorem
// This works because MOD = 998244353 is a prime number.
// The inverse of n modulo MOD is n^(MOD-2) % MOD.
long long modInverse(long long n) {
    // The constraints of the problem ensure n will be positive and less than MOD.
    // Thus n % MOD != 0. No need to handle n=0 case.
    return power(n, MOD - 2);
}

// Maximum value of N based on problem constraints
const int MAXN = 100005; 
// Arrays to store precomputed values:
// fact[i] = i! % MOD
// invFact[i] = (i!)^(-1) % MOD, modular inverse of i!
// inv[i] = i^(-1) % MOD, modular inverse of i
long long fact[MAXN];
long long invFact[MAXN];
long long inv[MAXN];

// Function to precompute factorials, inverse factorials, and modular inverses up to N
void precompute(int N) {
    // Base cases for factorial and inverse factorial
    fact[0] = 1;
    invFact[0] = 1;
    
    // Handle N >= 1 cases if needed
    if (N >= 1) {
        fact[1] = 1;
        invFact[1] = 1;
        inv[1] = 1; // Modular inverse of 1 is 1
    }

    // Calculate factorials, modular inverses, and inverse factorials iteratively up to N
    for (int i = 2; i <= N; ++i) {
        // Calculate factorial: fact[i] = (i-1)! * i % MOD
        fact[i] = (fact[i - 1] * i) % MOD;
        
        // Calculate modular inverse using the O(N) formula:
        // inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD
        // This formula is derived from the extended Euclidean algorithm relation:
        // MOD = q*i + r => q*i + r = 0 (mod MOD) => r = -q*i (mod MOD)
        // => r^{-1} = (-q*i)^{-1} (mod MOD) => r^{-1} = -(q^{-1}) * i^{-1} (mod MOD) -- No this is wrong derivation
        // Better explanation: q*i + r = 0 (mod MOD) => r = -q*i (mod MOD)
        // 1 = r * inv[r] (mod MOD) => 1 = (-q*i) * inv[r] (mod MOD)
        // Multiply by inv[i]: inv[i] = (-q*i) * inv[r] * inv[i] (mod MOD)
        // inv[i] = -q * inv[r] (mod MOD)
        // inv[i] = -(MOD / i) * inv[MOD % i] (mod MOD)
        // To ensure positive result: inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD
        inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD;
        
        // Calculate inverse factorials using the relation:
        // (i!)^{-1} = ((i-1)!)^{-1} * i^{-1} % MOD
        invFact[i] = (invFact[i - 1] * inv[i]) % MOD; 
    }
}


int main() {
    // Use fast I/O operations
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int N; // Input integer N
    std::cin >> N;

    // If N <= 3, the condition LIS + LDS = N cannot be satisfied by any permutation.
    // The number of rows k must satisfy 2 <= k <= N-2. This range is empty if N-2 < 2, i.e., N < 4.
    if (N <= 3) {
        std::cout << 0 << std::endl;
        return 0;
    }

    // Precompute factorials, inverse factorials, and modular inverses up to N
    // The maximum index needed is N for fact, invFact, and N-1 for inv.
    precompute(N);

    long long total_count = 0; // Initialize the total count of permutations satisfying the condition
    
    // Iterate through possible values of k (length of the Longest Decreasing Subsequence)
    // The Robinson-Schensted correspondence relates LIS/LDS lengths to Young Tableau shapes.
    // LIS = lambda_1 (length of first row), LDS = k (number of rows)
    // The condition LIS + LDS = N translates to lambda_1 + k = N.
    // Analysis shows the shapes must be of the form lambda = (N-k, 2, 1^{k-2})
    // The constraints require 2 <= k <= N-2.
    for (int k = 2; k <= N - 2; ++k) {
        // Calculate f^lambda, the number of Standard Young Tableaux (SYT) for the shape lambda.
        // The hook length formula gives f^lambda = N! / H, where H is the product of hook lengths.
        // The product of hook lengths H for shape (N-k, 2, 1^{k-2}) is:
        // H = (N-1) * (N-k) * (N-k-2)! * k * (k-2)!
        
        // Prepare indices and values needed for calculation
        long long N_minus_1 = N - 1;
        long long N_minus_k = N - k;
        long long k_val = k;
        int N_minus_k_minus_2 = N - k - 2; // Index for invFact array
        int k_minus_2 = k - 2;             // Index for invFact array

        // Ensure indices are valid (non-negative).
        // Given k in [2, N-2], we have k >= 2 => k-2 >= 0.
        // Also N-k >= 2 => N-k-2 >= 0. The indices are always valid.
        
        // Calculate the modular inverse of H.
        // H^{-1} = (N-1)^{-1} * (N-k)^{-1} * ((N-k-2)! )^{-1} * k^{-1} * ((k-2)! )^{-1} (mod MOD)
        
        // Fetch precomputed modular inverses and inverse factorials
        long long inv_N_minus_1 = inv[N_minus_1];
        long long inv_N_minus_k = inv[N_minus_k];
        long long inv_k = inv[k_val];
        long long invFact_N_minus_k_minus_2 = invFact[N_minus_k_minus_2];
        long long invFact_k_minus_2 = invFact[k_minus_2];

        // Compute f^lambda = (N! * H^{-1}) % MOD
        long long f_lambda = fact[N]; // Start with N!
        f_lambda = (f_lambda * inv_N_minus_1) % MOD; // Multiply by (N-1)^{-1}
        f_lambda = (f_lambda * inv_N_minus_k) % MOD; // Multiply by (N-k)^{-1}
        f_lambda = (f_lambda * invFact_N_minus_k_minus_2) % MOD; // Multiply by ((N-k-2)! )^{-1}
        f_lambda = (f_lambda * inv_k) % MOD; // Multiply by k^{-1}
        f_lambda = (f_lambda * invFact_k_minus_2) % MOD; // Multiply by ((k-2)! )^{-1}

        // The number of permutations corresponding to shape lambda is (f^lambda)^2.
        long long f_lambda_sq = (f_lambda * f_lambda) % MOD; // Calculate (f^lambda)^2 mod MOD
        
        // Add this count to the total sum
        total_count = (total_count + f_lambda_sq) % MOD;
    }

    // Output the final computed count modulo MOD
    std::cout << total_count << std::endl;

    return 0;
}