結果

問題 No.3048 Swing
ユーザー qwewe
提出日時 2025-05-14 13:25:19
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,989 bytes
コンパイル時間 885 ms
コンパイル使用メモリ 71,332 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-05-14 13:26:14
合計ジャッジ時間 2,528 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 55
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric> // Not strictly needed for this solution

// Computes (base^exp) % mod
long long power(long long base, long long exp) {
    long long res = 1;
    long long mod = 1000000007;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

// Computes modular inverse of n under modulo mod using Fermat's Little Theorem
long long modInverse(long long n) {
    long long mod = 1000000007;
    return power(n, mod - 2);
}

// Computes C(n, r) % mod
// C(n, r) = n * (n-1) * ... * (n-r+1) / r!
long long nCr_mod_p(int n, int r) {
    if (r < 0 || r > n) return 0; // Invalid r
    if (r == 0 || r == n) return 1; // Base cases C(n,0)=1, C(n,n)=1
    if (r > n / 2) r = n - r; // Symmetry: C(n, r) = C(n, n-r). Use smaller r.

    long long mod = 1000000007;

    // Calculate numerator: n * (n-1) * ... * (n-r+1)
    long long num = 1;
    for (int i = 0; i < r; ++i) {
        num = (num * (n - i)) % mod;
    }

    // Calculate denominator: r!
    long long den = 1;
    for (int i = 1; i <= r; ++i) {
        den = (den * i) % mod;
    }

    // Result is (num * inv(den)) % mod
    return (num * modInverse(den)) % mod;
}

int main() {
    std::ios_base::sync_with_stdio(false); // Speeds up C++ I/O
    std::cin.tie(NULL); // Unties cin from cout

    int K;
    std::cin >> K;

    if (K % 2 != 0) {
        std::cout << 0 << std::endl;
    } else {
        // We need to calculate C(K, K/2)
        // For K = 114514810, K/2 = 57257405.
        // The nCr_mod_p function performs about K/2 multiplications for numerator
        // and K/2 for denominator. Total roughly K multiplications.
        // For K/2 = 5.7 * 10^7, this means about 1.14 * 10^8 multiplications.
        // This should be acceptable within the 2-second time limit for C++.
        std::cout << nCr_mod_p(K, K / 2) << std::endl;
    }

    return 0;
}
0