結果

問題 No.148 試験監督（3）
コンテスト
ユーザー vjudge1
提出日時 2026-10-16 20:24:05
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 2,700 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,675 ms
コンパイル使用メモリ 339,924 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-10-16 20:24:27
合計ジャッジ時間 14,993 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge5_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 3 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1'000'000'007;

// ?????
static string norm(string s) {
    size_t i = 0;
    while (i + 1 < s.size() && s[i] == '0') ++i;
    return s.substr(i);
}

// ????????????
static int cmp(const string &a, const string &b) {
    string x = norm(a), y = norm(b);
    if (x.size() != y.size()) return x.size() < y.size() ? -1 : 1;
    if (x < y) return -1;
    if (x > y) return 1;
    return 0;
}

// a >= b : ??????b ??????????? b = P??????
static string subBig(const string &a, const string &b) {
    string x = norm(a), y = norm(b);
    int n = x.size(), m = y.size();
    string r(n, '0');
    int borrow = 0;
    for (int i = 0; i < n; ++i) {
        int d = (x[n - 1 - i] - '0') - borrow;
        if (i < m) d -= (y[m - 1 - i] - '0');
        if (d < 0) { d += 10; borrow = 1; } else borrow = 0;
        r[n - 1 - i] = char('0' + d);
    }
    return norm(r);
}

static string addOne(const string &a) {
    string s = a;
    int c = 1;
    for (int i = (int)s.size() - 1; i >= 0 && c; --i) {
        c += s[i] - '0'; s[i] = char('0' + c % 10); c /= 10;
    }
    if (c) s.insert(s.begin(), '1');
    return s;
}

// ?? % ???
static int modInt(const string &s, int m) {
    long long r = 0;
    for (char c : s) r = (r * 10 + (c - '0')) % m;
    return (int)r;
}

// ? s < limit ?????????? -1
static long long toIntIfSmall(const string &s, long long limit) {
    string t = norm(s);
    char buf[32]; snprintf(buf, sizeof(buf), "%lld", limit);
    if (t.size() > strlen(buf)) return -1;
    if (t.size() == strlen(buf) && t > string(buf)) return -1;
    return stoll(t);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        string C, P;
        cin >> C >> P;
        C = norm(C); P = norm(P);

        // P == 0 ???????? P>=1??????
        if (P == "0") { cout << 1 << '\n'; continue; }

        // 1) P >= MOD => P! ??? MOD
        long long pVal = toIntIfSmall(P, MOD);
        if (pVal < 0) { cout << 0 << '\n'; continue; }
        int k = (int)pVal;          // k = P < MOD

        // 2) ?????? C - P + 1 >= P  <=>  C >= 2P - 1
        // ?? n = C - P + 1?? C < P ????????? 0?
        if (cmp(C, P) < 0) { cout << 0 << '\n'; continue; }
        string n = addOne(subBig(C, P));   // n = C - P + 1
        if (cmp(n, P) < 0) { cout << 0 << '\n'; continue; }

        // 3) Lucas ????? n mod MOD
        int n0 = modInt(n, MOD);
        if (n0 < k) { cout << 0 << '\n'; continue; }

        // 4) ???? n0*(n0-1)*...*(n0-k+1)
        long long ans = 1;
        for (int i = 0; i < k; ++i) ans = ans * (n0 - i) % MOD;
        cout << ans << '\n';
    }
}
0