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

• 問題: No.148 試験監督（3）
• ユーザー: T1610
• 提出日時: 2026-10-04 13:39:42
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 2,913 bytes
• コンパイル時間: 989 ms
• コンパイル使用メモリ: 169,116 KB
• 実行使用メモリ: 9,920 KB
• 最終ジャッジ日時: 2026-10-04 13:40:03
• 合計ジャッジ時間: 12,894 ms
• ジャッジサーバーID （参考情報）: judge4_1 / judge3_0

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

ソースコード

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

using namespace std;

const int 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);
}

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;
    for (long long i = 0; i < p_val; ++i) {
        ans = (ans * (start_val - i)) % 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;
}