結果

問題 No.1327 グラフの数え上げ
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:13:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 6,189 bytes
コンパイル時間 664 ms
コンパイル使用メモリ 75,768 KB
実行使用メモリ 21,644 KB
最終ジャッジ日時 2025-05-14 13:14:31
合計ジャッジ時間 4,168 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 12 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdexcept> // For std::stoll exception

// Define the modulus P
const long long P = 1000000007;

// Function for modular exponentiation (base^exp % MOD)
// Uses unsigned long long for intermediate products to prevent overflow
long long power(long long base, long long exp) {
    long long res = 1;
    base %= P; // Ensure base is within [0, P-1]
    while (exp > 0) {
        if (exp % 2 == 1) {
            // Multiply result by base, using unsigned long long for intermediate product
            res = (unsigned long long)res * base % P;
        }
        // Square the base, using unsigned long long for intermediate product
        base = (unsigned long long)base * base % P;
        exp /= 2; // Halve the exponent
    }
    return res;
}

// Function for modular multiplicative inverse using Fermat's Little Theorem
// Calculates n^(P-2) mod P
long long modInverse(long long n) {
    // Ensure n is within [0, P-1] before calculating inverse
    n %= P;
    if (n < 0) n += P; // Handle potential negative input, although unlikely in this context
    
    // Inverse exists only for n != 0 mod P.
    // In our context, n is product of terms N to P-1. If N < P, none are 0 mod P.
    // So product is non-zero mod P. Inverse exists.
    if (n == 0) {
        // This case should not happen based on the logic and constraints.
        // If it occurs, it indicates an error.
        // std::cerr << "Error: Modular inverse requested for 0." << std::endl;
         return 0; // Or handle error appropriately
    }
    return power(n, P - 2);
}

int main() {
    // Use faster I/O operations
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    std::string N_str; // Read N as a string
    std::cin >> N_str;
    
    // String representations of P and P+1 for comparison
    std::string P_str = "1000000007"; 
    std::string P_p1_str = "1000000008"; 

    // Case 1: N >= P+1
    // Compare N as string with "1000000008".
    // If N_str is longer, or same length and lexicographically >= P_p1_str, then N >= P+1.
    if (N_str.length() > P_p1_str.length() || (N_str.length() == P_p1_str.length() && N_str >= P_p1_str)) {
        // (N-1)! contains P as a factor, so (N-1)! = 0 mod P.
        // S(N) = (N-1)! * (-1)^(N-1) = 0 * (...) = 0 mod P.
        std::cout << 0 << std::endl;
        return 0;
    }

    // Case 2: N = P
    // Check if N_str is exactly the string representation of P.
    if (N_str == P_str) {
        // S(P) = (P-1)! * (-1)^(P-1) mod P
        // By Wilson's Theorem, (P-1)! = -1 mod P.
        // Since P = 10^9+7 is an odd prime > 2, P-1 is even. (-1)^(P-1) = 1.
        // S(P) = (-1) * 1 = -1 mod P.
        // -1 mod P is P-1.
        std::cout << P - 1 << std::endl; 
        return 0;
    }

    // Case 3: 2 <= N < P
    // N must be converted from string to long long.
    // Since N < P, it fits within a standard 64-bit signed long long.
    long long N;
    try {
        N = std::stoll(N_str);
    } catch (const std::out_of_range& oor) {
         // This should not happen given the length/string comparisons above.
         // If it does, it indicates an unexpected issue.
         std::cerr << "Error: N string parsing failed unexpectedly for value < P." << std::endl;
         return 1; // Exit with error code
    }
    
    // Constraint check: Problem statement guarantees N >= 2.
    // If N happens to be less than 2, print error and exit.
    if (N < 2) {
         std::cerr << "Error: N < 2 encountered, constraint N >= 2 violated." << std::endl;
         return 1; // Exit with error code
    }

    // Now we need to compute S(N) = (N-1)! * (-1)^(N-1) mod P for 2 <= N < P.
    // This requires computing (N-1)! mod P.

    long long factN_1; // Variable to store (N-1)! mod P

    // Optimization: Choose faster method to compute (N-1)! mod P.
    // Method 1: Direct computation: 1 * 2 * ... * (N-1). Takes O(N) time (N-2 multiplications).
    // Method 2: Inverse property: (N-1)! = (-1) * (product_{k=N}^{P-1} k)^{-1} mod P. Based on Wilson's Thm. Takes O(P-N) time (P-N multiplications + 1 modular inverse O(log P)).
    // Compare costs: N-2 vs P-N. Direct is faster if N-2 < P-N => 2N < P+2 => N <= (P+1)/2.
    // Threshold for P = 10^9+7 is (10^9+7+1)/2 = 10^9+8 / 2 = 500000004.
    // Let's use threshold = (P + 2) / 2 for integer arithmetic precision. P is odd, P+2 is odd. floor((P+2)/2) = (P+1)/2.
    long long threshold = (P + 1) / 2; // Threshold = 500000004

    if (N <= threshold) {
        // Compute (N-1)! directly. Best for smaller N.
        factN_1 = 1; 
        for (long long i = 1; i < N; ++i) {
            // Use unsigned long long for intermediate product to prevent overflow
            factN_1 = (unsigned long long)factN_1 * i % P;
        }
    } else {
        // Compute (N-1)! using inverse property. Best for larger N (closer to P).
        // (N-1)! = (-1) * (product_{k=N}^{P-1} k)^{-1} mod P
        
        long long prod_N_to_P_1 = 1;
        // Calculate product N * (N+1) * ... * (P-1) mod P. Loop runs from N up to P-1.
        for (long long k = N; k < P; ++k) {
            prod_N_to_P_1 = (unsigned long long)prod_N_to_P_1 * k % P;
        }
        
        // Calculate modular inverse of the product
        long long inv_prod = modInverse(prod_N_to_P_1);
        
        // Calculate (N-1)! = (-1 * inv_prod) mod P
        // Ensure result is positive: (P - inv_prod) % P is equivalent to -inv_prod mod P
        factN_1 = (P - inv_prod) % P; 
    }

    // Final result S(N) = (N-1)! * (-1)^(N-1) mod P
    long long result;
    if ((N - 1) % 2 == 0) { // Check if N-1 is even (i.e., N is odd)
        // If N-1 is even, (-1)^(N-1) = 1. S(N) = (N-1)! mod P.
        result = factN_1;
    } else { // N-1 is odd (i.e., N is even)
        // If N-1 is odd, (-1)^(N-1) = -1. S(N) = -(N-1)! mod P.
        // Ensure result is positive: (P - factN_1) % P is equivalent to -factN_1 mod P.
        result = (P - factN_1) % P;
    }
    
    // Print the final result followed by a newline.
    std::cout << result << std::endl;

    return 0; // Successful execution
}
0