結果

問題 No.148 試験監督（3）
コンテスト
ユーザー T1610
提出日時 2026-09-23 17:58:38
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 2,467 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,297 ms
コンパイル使用メモリ 158,464 KB
実行使用メモリ 9,856 KB
最終ジャッジ日時 2026-09-23 17:58:55
合計ジャッジ時間 14,984 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge4_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 3 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <string>

using namespace std;

const long long MOD = 1000000007;

// 繰り返し二乗法
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;
}

// フェルマーの小定理による逆元
long long modInverse(long long n) {
    return power(n, MOD - 2);
}

void solve() {
    string C_str, P_str;
    if (!(cin >> C_str >> P_str)) return;

    // 足切り1: P >= MOD
    // 文字列が11桁以上なら確実に 10^9+7 を超えている
    if (P_str.length() > 10) {
        cout << 0 << "\n";
        return;
    }
    long long P = stoll(P_str);
    if (P >= MOD) {
        cout << 0 << "\n";
        return;
    }

    // 足切り2: C < 2P - 1
    // P < MOD より 2P-1 は高々 2*10^9+13。Cが12桁以上なら余裕で満たす
    if (C_str.length() <= 11) {
        long long C = stoll(C_str);
        if (C < 2 * P - 1) {
            cout << 0 << "\n";
            return;
        }
    }

    // C mod M を文字列から O(|C|) で計算
    long long C_mod = 0;
    for (char c : C_str) {
        C_mod = (C_mod * 10 + (c - '0')) % MOD;
    }

    // N mod M の計算
    long long n0 = (C_mod - P + 1) % MOD;
    if (n0 < 0) n0 += MOD;

    // 足切り3: n_mod < P
    if (n0 < P) {
        cout << 0 << "\n";
        return;
    }

    long long ans = 1;

    // 最適化: O(min(P, MOD-P)) で階乗の割り算を処理
    if (P <= MOD / 2) {
        // P が小さい場合は愚直に P 回掛ける
        for (long long i = 0; i < P; i++) {
            ans = (ans * (n0 - i)) % MOD;
        }
    } else {
        // P が大きい場合はウィルソンの定理を利用し、M-P 回の掛け算に抑える
        long long denom1 = 1;
        for (long long i = n0 + 1; i < MOD; i++) {
            denom1 = (denom1 * i) % MOD;
        }

        long long denom2 = 1;
        for (long long i = 1; i <= n0 - P; i++) {
            denom2 = (denom2 * i) % MOD;
        }

        long long denom = (denom1 * denom2) % MOD;
        ans = (MOD - 1) * modInverse(denom) % MOD; // -1 * (denom^-1)
    }

    cout << ans << "\n";
}

int main() {
    // 入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    if (cin >> T) {
        while (T--) solve();
    }
    return 0;
}
0