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

• 問題: No.148 試験監督（3）
• ユーザー: vjudge1
• 提出日時: 2026-10-16 20:53:56
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 8,914 bytes
• コンパイル時間: 3,496 ms
• コンパイル使用メモリ: 359,616 KB
• 実行使用メモリ: 12,192 KB
• 最終ジャッジ日時: 2026-10-16 20:54:12
• 合計ジャッジ時間: 12,938 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge4_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);
}

/* ---------- 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, w *= wlen) {
                cd u = a[i + j], v = a[i + j + len / 2] * w;
                a[i + j] = u + v;
                a[i + j + len / 2] = u - v;
            }
        }
    }
    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 {0};
    int sz = (int)a.size() + (int)b.size() - 1, n = 1;
    while (n < sz) n <<= 1;
    const int MASK = (1 << 15) - 1;
    const long long B2 = (long long)(1 << 15) * (1 << 15) % MOD;

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

    vector<cd> c0(n), c1(n), c2(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);
        c0[i] = a0 * b0;
        c1[i] = a0 * b1 + a1 * b0;
        c2[i] = a1 * b1;
    }
    fft(c0, true); fft(c1, true); fft(c2, true);

    vector<int> r(sz);
    for (int i = 0; i < sz; ++i) {
        long long v0 = (long long)(c0[i].real() + 0.5) % MOD;
        long long v1 = (long long)(c1[i].real() + 0.5) % MOD;
        long long v2 = (long long)(c2[i].real() + 0.5) % MOD;
        r[i] = int((v0 + v1 * (1 << 15) % MOD + v2 * B2) % MOD);
    }
    while (r.size() > 1 && r.back() == 0) r.pop_back();
    return r;
}

/* ---------- ???? (mod x^n) ---------- */
vector<int> poly_inv(const vector<int>& a, int n) {
    vector<int> r(1, modpow(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) r[i] = submod(mulmod(2, r[i]), c[i]);
        cur = nxt;
    }
    r.resize(n);
    return r;
}

/* ---------- ??? + ???? + ???? ---------- */
struct MultiEval {
    int N = 0;
    vector<vector<int>> seg;      // seg[o]: prod_{i in node} (X - pts[i])
    vector<vector<int>> invrev;   // inv(reverse(seg[o]))

    void build(const vector<int>& pts) {
        int m = (int)pts.size();
        N = 1; while (N < m) N <<= 1;
        seg.assign(2 * N, vector<int>{1});
        for (int i = 0; i < N; ++i) {
            if (i < m) {
                int v = pts[i] ? (MOD - pts[i]) : 0;
                seg[N + i] = {v, 1};          // X - pts[i]
            }
        }
        for (int i = N - 1; i >= 1; --i)
            seg[i] = convolution(seg[i << 1], seg[i << 1 | 1]);

        invrev.assign(2 * N, {});
        for (int o = 1; o < 2 * N; ++o) {
            if ((int)seg[o].size() <= 1) continue;   // ?????????
            auto rev = seg[o];
            reverse(rev.begin(), rev.end());
            invrev[o] = poly_inv(rev, (int)rev.size());
        }
    }

    // a mod b, deg b >= 1
    static vector<int> mod_with(const vector<int>& a, const vector<int>& b,
                                const vector<int>& invb) {
        int n = (int)a.size() - 1, m = (int)b.size() - 1;
        if (n < m) return a;
        int len = n - m + 1;
        vector<int> ar(len), br(len);
        for (int i = 0; i < len; ++i) { ar[i] = a[n - i]; br[i] = b[m - i]; }
        auto q = convolution(ar, invb);
        q.resize(len);
        auto qb = convolution(q, b);
        vector<int> r(n + 1);
        for (int i = 0; i <= n; ++i) {
            int v = a[i] - (i < (int)qb.size() ? qb[i] : 0);
            if (v < 0) v += MOD;
            r[i] = v;
        }
        while (r.size() > 1 && r.back() == 0) r.pop_back();
        return r;
    }

    vector<int> eval(const vector<int>& F, const vector<int>& pts) {
        int m = (int)pts.size();
        vector<int> res(m);
        function<void(int,int,int,vector<int>)> dfs = [&](int o, int l, int r, vector<int> f) {
            if (f.size() == 1 || r - l <= 32) {          // ???? Horner
                for (int i = l; i < r && i < m; ++i) {
                    long long v = 0;
                    for (int k = (int)f.size() - 1; k >= 0; --k)
                        v = (v * pts[i] + f[k]) % MOD;
                    res[i] = int(v);
                }
                return;
            }
            int mid = (l + r) >> 1;
            dfs(o << 1, l, mid, mod_with(f, seg[o << 1], invrev[o << 1]));
            dfs(o << 1 | 1, mid, r, mod_with(f, seg[o << 1 | 1], invrev[o << 1 | 1]));
        };
        vector<int> f = F;
        if (f.empty()) f = {0};
        dfs(1, 0, N, move(f));
        return res;
    }
};

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

void build_F() {
    int N = 1; while (N < B) N <<= 1;
    vector<vector<int>> seg(2 * N, vector<int>{1});
    for (int i = 0; i < N; ++i) {
        int v = (i < B) ? (i ? MOD - i : 0) : 0;
        seg[N + i] = (i < B) ? vector<int>{v, 1} : vector<int>{1};
    }
    for (int i = N - 1; i >= 1; --i)
        seg[i] = convolution(seg[i << 1], seg[i << 1 | 1]);
    Fpoly = seg[1];
    Fpoly.resize(B + 1);
}

/* ---------- ??? (x0)_P ---------- */
int falling(long long x0, long long P) {
    if (P == 0) return 1;
    const long long SMALL = 3000000;            // ???? FFT ?
    if (P <= SMALL) {
        long long 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;

    // ????? -> ?? Horner??????
    if (q <= 600) {
        long long ans = 1;
        for (long long j = 0; j < q; ++j) {
            long long base = x0 - j * B;
            for (long long i = 0; i < B; ++i) {
                long long t = (base - i) % MOD; if (t < 0) t += MOD;
                ans = mulmod(ans, t);
            }
        }
        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);
    }

    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 MultiEval tree;
    tree.build(pts);
    auto vals = tree.eval(Fpoly, pts);

    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????? 0??C ???????
    if (Cs.size() <= 10) {
        long long C = stoll(Cs);
        if (C < 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();                            // ????? 0.05s
    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        string C, P;
        cin >> C >> P;
        cout << solve_one(C, P) << '\n';
    }
}