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

• 問題: No.148 試験監督（3）
• ユーザー: vjudge1
• 提出日時: 2026-10-16 20:51:30
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 8,418 bytes
• コンパイル時間: 2,922 ms
• コンパイル使用メモリ: 362,432 KB
• 実行使用メモリ: 24,000 KB
• 最終ジャッジ日時: 2026-10-16 20:52:01
• 合計ジャッジ時間: 12,314 ms
• ジャッジサーバーID （参考情報）: judge5_0 / judge2_0

ファイルパターン	結果
other	TLE * 1 -- * 11

ソースコード

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;
using cd = complex<double>;
const double PI = acos(-1.0);

/* ---------- ??? ---------- */
inline int addmod(int a, int b) { int s = a + b; if (s >= MOD) s -= MOD; return s; }
inline int submod(int a, int b) { int s = a - b; if (s < 0) s += MOD; return s; }
inline int mulmod(long long a, long long b) { return int((a * b) % MOD); }

int modpow(long long a, long long e = MOD - 2) {
    long long r = 1;
    for (a %= MOD; e; e >>= 1, a = a * a % MOD) if (e & 1) r = r * a % MOD;
    return int(r);
}
int modinv(int a) { return modpow(a); }

/* ---------- FFT???????? 15 ? + ????? ---------- */
void fft(vector<cd>& a, bool inv) {
    int n = (int)a.size();
    for (int i = 1, j = 0; i < n; ++i) {
        int b = n >> 1;
        for (; j & b; b >>= 1) j ^= b;
        j ^= b;
        if (i < j) swap(a[i], a[j]);
    }
    for (int len = 2; len <= n; len <<= 1) {
        double ang = 2 * PI / len * (inv ? -1 : 1);
        cd wlen(cos(ang), sin(ang));
        for (int i = 0; i < n; i += len) {
            cd w(1);
            for (int j = 0; j < len / 2; ++j) {
                cd u = a[i + j], v = a[i + j + len / 2] * w;
                a[i + j] = u + v;
                a[i + j + len / 2] = u - v;
                w *= wlen;
            }
        }
    }
    if (inv) for (auto& x : a) x /= n;
}

vector<int> convolution(const vector<int>& a, const vector<int>& b) {
    if (a.empty() || b.empty()) return {};
    int need = (int)a.size() + (int)b.size() - 1;
    int n = 1;
    while (n < need) n <<= 1;
    const int B = 1 << 15;
    const long long B2 = (long long)B * B % MOD;

    vector<cd> fa(n), fb(n);
    for (int i = 0; i < (int)a.size(); ++i) fa[i] = cd(a[i] & (B - 1), a[i] >> 15);
    for (int i = 0; i < (int)b.size(); ++i) fb[i] = cd(b[i] & (B - 1), b[i] >> 15);
    fft(fa, false);
    fft(fb, false);

    vector<cd> f00(n), f01(n), f11(n);
    const cd J(0, 1);
    for (int i = 0; i < n; ++i) {
        cd ca = conj(fa[(n - i) & (n - 1)]), cb = conj(fb[(n - i) & (n - 1)]);
        cd a0 = (fa[i] + ca) * 0.5, a1 = (fa[i] - ca) * (-J * 0.5);
        cd b0 = (fb[i] + cb) * 0.5, b1 = (fb[i] - cb) * (-J * 0.5);
        f00[i] = a0 * b0;
        f01[i] = a0 * b1 + a1 * b0;
        f11[i] = a1 * b1;
    }
    fft(f00, true);
    fft(f01, true);
    fft(f11, true);

    vector<int> r(need);
    for (int i = 0; i < need; ++i) {
        long long c0 = (long long)(f00[i].real() + 0.5);
        long long c1 = (long long)(f01[i].real() + 0.5);
        long long c2 = (long long)(f11[i].real() + 0.5);
        long long v = (c0 + c1 % MOD * B + c2 * B2) % MOD;
        r[i] = int(v);
    }
    while (r.size() > 1 && r.back() == 0) r.pop_back();
    return r;
}

/* ---------- ???? / ?? ---------- */
vector<int> poly_inv(const vector<int>& a, int n) {      // a^{-1} mod x^n, a[0]!=0
    vector<int> r(1, modinv(a[0]));
    int cur = 1;
    while (cur < n) {
        int nxt = min(cur << 1, n);
        vector<int> tmp(a.begin(), a.begin() + nxt);
        auto c = convolution(r, r);
        c.resize(nxt);
        c = convolution(c, tmp);
        c.resize(nxt);
        r.resize(nxt);
        for (int i = 0; i < nxt; ++i) {
            int v = submod(mulmod(2, r[i]), c[i]);
            r[i] = v;
        }
        cur = nxt;
    }
    r.resize(n);
    return r;
}

// ?? a % b?deg b >= 1?
vector<int> poly_mod(vector<int> a, const vector<int>& b) {
    int n = (int)a.size() - 1, m = (int)b.size() - 1;
    if (n < m) return a;
    vector<int> ar = a; reverse(ar.begin(), ar.end()); ar.resize(n - m + 1);
    vector<int> br = b; reverse(br.begin(), br.end()); br.resize(n - m + 1);
    auto q = convolution(ar, poly_inv(br, n - m + 1));
    q.resize(n - m + 1);
    reverse(q.begin(), q.end());
    auto qb = convolution(q, b);
    qb.resize(n + 1);
    vector<int> r(n + 1);
    for (int i = 0; i <= n; ++i) {
        int v = a[i] - qb[i];
        if (v < 0) v += MOD;
        r[i] = v;
    }
    while (r.size() > 1 && r.back() == 0) r.pop_back();
    return r;
}

/* ---------- ????? ---------- */
struct EvalTree {
    int n = 0;                       // ?? 2 ??
    vector<vector<int>> seg;
    vector<int> xs;                  // ?????

    void build(int o, int l, int r) {
        if (r - l == 1) {
            seg[o] = {xs[l], 1};     // X - xs[l]
            return;
        }
        int m = (l + r) >> 1;
        build(o << 1, l, m);
        build(o << 1 | 1, m, r);
        seg[o] = convolution(seg[o << 1], seg[o << 1 | 1]);
    }
    void init(const vector<int>& points) {
        xs = points;
        n = 1;
        while (n < (int)xs.size()) n <<= 1;
        seg.assign(4 * n, {});
        build(1, 0, n);
    }
    void dfs(int o, int l, int r, const vector<int>& f, vector<int>& res) {
        if (r - l <= 48) {           // ?????? Horner
            for (int i = l; i < r; ++i) {
                long long v = 0;
                for (int k = (int)f.size() - 1; k >= 0; --k)
                    v = (v * xs[i] + f[k]) % MOD;
                res[i] = int(v);
            }
            return;
        }
        int m = (l + r) >> 1;
        dfs(o << 1, l, m, poly_mod(f, seg[o << 1]), res);
        dfs(o << 1 | 1, m, r, poly_mod(f, seg[o << 1 | 1]), res);
    }
    // ?? F ? xs[0..cnt-1] ???
    vector<int> eval(const vector<int>& F, int cnt) {
        vector<int> f = F;
        f.resize(max(f.size(), size_t(1)));
        vector<int> res(cnt);
        dfs(1, 0, n, f, res);
        return res;
    }
};

/* ---------- ???F(X) = (X)_B = prod_{i=0}^{B-1}(X-i) ---------- */
constexpr int B = 32768;
vector<int> Fpoly;                   // deg = B

void build_F() {
    // ?????????? F
    int n = 1;
    while (n < B) n <<= 1;
    vector<vector<int>> seg(4 * n);
    function<void(int, int, int)> go = [&](int o, int l, int r) {
        if (r - l == 1) {
            int v = MOD - l;         // X - l
            if (v == MOD) v = 0;
            seg[o] = {v, 1};
            return;
        }
        int m = (l + r) >> 1;
        go(o << 1, l, m);
        go(o << 1 | 1, m, r);
        seg[o] = convolution(seg[o << 1], seg[o << 1 | 1]);
    };
    go(1, 0, n);
    Fpoly = seg[1];
    Fpoly.resize(B + 1);             // ??? B
}

/* ---------- ???? ---------- */
int falling(long long x0, long long P) {   // (x0)_P mod MOD, x0 ???? x0>=P
    if (P == 0) return 1;
    const long long DIRECT = 2000000;      // ? P ????? FFT ?
    if (P <= DIRECT) {
        long long ans = 1;
        for (long long i = 0; i < P; ++i) ans = mulmod(ans, (x0 - i) % MOD + MOD >= MOD ? ((x0 - i) % MOD + MOD) : ((x0 - i) % MOD));
        // ???????????
        ans = 1;
        for (long long i = 0; i < P; ++i) {
            long long t = x0 - i;
            t %= MOD; if (t < 0) t += MOD;
            ans = mulmod(ans, t);
        }
        return int(ans);
    }
    long long q = P / B, r = P % B;
    // ???
    vector<int> pts(q);
    for (long long j = 0; j < q; ++j) {
        long long t = (x0 - j * B) % MOD;
        if (t < 0) t += MOD;
        pts[j] = int(t);
    }
    static EvalTree tree;
    tree.init(pts);
    auto vals = tree.eval(Fpoly, (int)q);

    long long ans = 1;
    for (long long j = 0; j < q; ++j) ans = mulmod(ans, vals[j]);
    long long tail = x0 - q * B;
    for (long long i = 0; i < r; ++i) {
        long long t = (tail - i) % MOD;
        if (t < 0) t += MOD;
        ans = mulmod(ans, t);
    }
    return int(ans);
}

int solve_one(const string& Cs, const string& Ps) {
    // P >= MOD => P! ? 0
    bool pBig = (Ps.size() > 10) || (Ps.size() == 10 && Ps > "1000000007");
    if (pBig) return 0;
    long long P = stoll(Ps);
    if (P == 0) return 1;

    long long cMod = 0;
    for (char c : Cs) cMod = (cMod * 10 + (c - '0')) % MOD;

    // ???? C < 2P-1??? x = C-P+1 < P???? C ??? long long ??????
    long long Cval = -1;
    if (Cs.size() <= 18) Cval = stoll(Cs);
    if (Cval >= 0 && Cval < 2 * P - 1) return 0;

    long long x0 = (cMod - (P % MOD) + 1) % MOD;
    if (x0 < 0) x0 += MOD;
    if (x0 < P) return 0;              // Lucas ????????? 0????"???"?

    return falling(x0, P);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    build_F();                         // ?????????
    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        string C, P;
        cin >> C >> P;
        cout << solve_one(C, P) << '\n';
    }
}