#1191413 (C++23) No.148 試験監督（3）

• 問題: No.148 試験監督（3）
• ユーザー: T1610
• 提出日時: 2026-10-04 13:50:10
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 3,846 bytes
• コンパイル時間: 1,155 ms
• コンパイル使用メモリ: 176,584 KB
• 実行使用メモリ: 9,916 KB
• 最終ジャッジ日時: 2026-10-04 13:51:37
• 合計ジャッジ時間: 13,054 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge4_1

ファイルパターン	結果
other	TLE * 3 -- * 9

ソースコード

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <iostream>
#include <string>
#include <vector>

using namespace std;

const long long MOD = 1e9 + 7;

// 巨大な数字文字列をMODで割った余りを計算する
long long parse_mod(const string& s) {
    long long res = 0;
    for (char c : s) {
        res = (res * 10 + (c - '0')) % MOD;
    }
    return res;
}

// 文字列による大なりイコール比較 (a >= b)
bool is_greater_or_equal(const string& a, const string& b) {
    if (a.length() != b.length()) {
        return a.length() > b.length();
    }
    return a >= b;
}

// 文字列による大なり比較 (a > b)
bool is_greater(const string& a, const string& b) {
    if (a.length() != b.length()) {
        return a.length() > b.length();
    }
    return a > b;
}

// 文字列の数値に対して 2倍して1を引く (2P - 1 を計算)
string multiply_by_2_and_subtract_1(string s) {
    int carry = 0;
    // 2倍する
    for (int i = (int)s.length() - 1; i >= 0; --i) {
        int val = (s[i] - '0') * 2 + carry;
        s[i] = (val % 10) + '0';
        carry = val / 10;
    }
    if (carry > 0) {
        s = to_string(carry) + s;
    }
    // 1を引く
    for (int i = (int)s.length() - 1; i >= 0; --i) {
        if (s[i] > '0') {
            s[i]--;
            break;
        } else {
            s[i] = '9';
        }
    }
    // 先頭の余分な0を取り除く
    int pos = 0;
    while (pos < (int)s.length() - 1 && s[pos] == '0') {
        pos++;
    }
    return s.substr(pos);
}

// 繰り返し二乗法による累乗計算
long long modpow(long long a, long long n) {
    long long res = 1;
    a %= MOD;
    while (n > 0) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

void solve() {
    string C_str, P_str;
    cin >> C_str >> P_str;
    
    // 1. P が 10^9+7 以上なら、P! が 10^9+7 で割り切れるため 0
    string mod_str = "1000000007";
    if (is_greater_or_equal(P_str, mod_str)) {
        cout << 0 << "\n";
        return;
    }
    
    // 2. 2P - 1 > C なら物理的に座れないため 0
    string limit_str = multiply_by_2_and_subtract_1(P_str);
    if (is_greater(limit_str, C_str)) {
        cout << 0 << "\n";
        return;
    }
    
    // ここまできた時点で P は 10^9+7 未満であることが確定
    long long p_val = stoll(P_str);
    long long c_mod = parse_mod(C_str);
    
    // 掛け算のスタート位置を算出 (C - P + 1) mod MOD
    long long start_val = (c_mod - p_val + 1) % MOD;
    if (start_val < 0) start_val += MOD;
    
    // 3. 連続する P 個の整数の間に MOD の倍数が含まれるか判定
    if (start_val < p_val) {
        cout << 0 << "\n";
        return;
    }
    
    long long ans = 1;
    // P が MOD/2 以下なら直接計算（最大 5*10^8 回）
    if (p_val <= MOD / 2) {
        for (long long i = 0; i < p_val; ++i) {
            ans = (ans * (start_val - i)) % MOD;
        }
    } 
    // P が MOD/2 より大きい場合は、ウィルソンの定理を利用して計算量を削減（最大 5*10^8 回）
    else {
        long long inv_prod = 1;
        for (long long i = start_val + 1; i <= MOD - 1; ++i) {
            inv_prod = (inv_prod * i) % MOD;
        }
        for (long long i = 1; i <= start_val - p_val; ++i) {
            inv_prod = (inv_prod * i) % MOD;
        }
        // (MOD-1)! ≡ -1 ≡ MOD-1 (mod MOD) にフェルマーの小定理を適用
        ans = (MOD - 1) * modpow(inv_prod, MOD - 2) % MOD;
    }
    
    cout << ans << "\n";
}

int main() {
    // 入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T;
    if (cin >> T) {
        while (T--) {
            solve();
        }
    }
    
    return 0;
}