結果
| 問題 |
No.148 試験監督（3）
|
| コンテスト | |
| ユーザー |
 Min_25
|
| 提出日時 | 2016-05-17 15:36:01 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 593 ms / 1,000 ms |
| コード長 | 11,378 bytes |
| コンパイル時間 | 1,466 ms |
| コンパイル使用メモリ | 94,272 KB |
| 実行使用メモリ | 8,572 KB |
| 最終ジャッジ日時 | 2024-10-06 05:14:22 |
| 合計ジャッジ時間 | 9,736 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 12 |
コンパイルメッセージ
main.cpp: In function ‘void solve()’:
main.cpp:374:15: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
374 | u32 T; scanf("%u", &T);
| ~~~~~^~~~~~~~~~
main.cpp:377:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
377 | scanf("%s %s", C, P);
| ~~~~~^~~~~~~~~~~~~~~
ソースコード
#include <cstdio>
#include <cassert>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iostream>
#include <vector>
#include <tuple>
#include <functional>
#define _fetch(_1, _2, _3, _4, name, ...) name
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, c) for (int i = int(a); i < int(b); i += int(c))
#define rep(...) _fetch(__VA_ARGS__, rep4, rep3, rep2, _)(__VA_ARGS__)
using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using R = u32;
class poly {
enum {
KARATSUBA_CUTOFF = 64,
DIV_CUTOFF = 128
};
public:
poly() {}
poly(int n) : coefs(n) {}
poly(int n, int c) : coefs(n, c % mod) {}
poly(const vector<R>& v) : coefs(v) {}
poly(const poly& f, int beg, int end=-1) {
if (end < 0) end = beg, beg = 0;
resize(end - beg);
rep(i, beg, end) if (i < f.size()) coefs[i - beg] = f[i];
}
static u32 ilog2(u64 n) {
return 63 - __builtin_clzll(n);
}
static void init_mod(int s, R m) {
mod = m;
lmod = (u64(-1) / m - m) * m;
facts.resize(s + 1, 1);
ifacts.resize(s + 1, 1);
invs.resize(s + 1, 1);
rep(i, 2, s + 1) {
invs[i] = u64(invs[mod % i]) * (mod - mod / i) % mod;
facts[i] = u64(facts[i - 1]) * i % mod;
ifacts[i] = u64(ifacts[i - 1]) * invs[i] % mod;
}
}
int size() const { return coefs.size(); }
void resize(int s) { coefs.resize(s); }
void push_back(R c) { coefs.push_back(c); }
const R* data() const { return coefs.data(); }
R* data() { return coefs.data(); }
const R& operator [] (int i) const { return coefs[i]; }
R& operator [] (int i) { return coefs[i]; }
static void add(R& a, R b) { if ((a += b) >= mod) a -= mod; }
static void add64(u64& a, u64 b) { if ((a += b) >= lmod) a -= lmod; }
static void sub(R& a, R b) { if (int(a -= b) < 0) a += mod; }
static R pow_mod(R b, u32 e) {
R ret = 1;
while (e) {
if (e & 1) ret = u64(ret) * b % mod;
b = u64(b) * b % mod;
e >>= 1;
}
return ret;
}
poly operator - () {
poly ret = *this;
rep(i, ret.size()) ret[i] = (ret[i] == 0 ? 0 : mod - ret[i]);
return ret;
}
poly& operator += (const poly& rhs) {
if (size() < rhs.size()) resize(rhs.size());
rep(i, rhs.size()) add(coefs[i], rhs[i]);
return *this;
}
poly operator + (const poly& rhs) const {
return poly(*this) += rhs;
}
poly& operator -= (const poly& rhs) {
if (size() < rhs.size()) resize(rhs.size());
rep(i, rhs.size()) sub(coefs[i], rhs[i]);
return *this;
}
poly operator - (const poly& rhs) const {
return poly(*this) -= rhs;
}
poly operator * (const poly& rhs) const {
return this->mul(rhs);
}
poly& operator *= (const poly& rhs) {
return *this = *this * rhs;
}
bool operator == (const poly& rhs) const {
if (size() != rhs.size()) return false;
rep(i, size()) if (coefs[i] != rhs[i]) return false;
return true;
}
poly operator * (const R c) const {
poly ret = poly(*this);
rep(i, size()) ret[i] = u64(ret[i]) * c % mod;
return ret;
}
poly operator / (const R c) const {
return *this * pow_mod(c, mod - 2);
}
// return a * b (mod x^prec)
poly mul(const poly& b, int prec=-1) const {
if (prec < 0) prec = max(0, size() + b.size() - 1);
poly ret = poly(prec);
amul(data(), size(), b.data(), b.size(), ret.data(), prec);
return ret;
}
// return (q, r) such that a = q * b + r
// - 2 * M(n/2) + 4 * M(n/4) + ...
pair<poly, poly> divmod(const poly& b) const {
if (size() < b.size()) {
return make_pair(poly(), poly(*this));
}
poly q(size() - b.size() + 1);
poly r(b.size() - 1);
divmod_dc(data(), size(), b.data(), b.size(), q.data(), r.data());
return make_pair(q, r);
}
poly rem(const poly& b) const {
return this->divmod(b).second;
}
// ----------------
R evaluate(R x) const {
R ret = 0;
rep(i, size()) ret = (u64(ret) * x + coefs[i]) % mod;
return ret;
}
static poly expand(vector<R>& cs) {
function< poly(int, int) > rec = [&](int beg, int end) {
if (end - beg == 1) {
return poly(vector<R>({1, cs[beg] % mod}));
}
int mid = (beg + end) / 2;
return rec(beg, mid) * rec(mid, end);
};
return rec(0, cs.size());
}
static vector<R> multipoint_evaluation(const poly& f, vector<R>& points) {
int s = points.size();
int tree_size = 4 << ilog2(s - 1);
vector<poly> tree(tree_size);
function< void(int, int, int) > rec = [&](int beg, int end, int k) {
if (end - beg == 1) {
tree[k] = poly(vector<R>({1, (mod - points[beg] % mod) % mod}));
} else {
int mid = (beg + end) >> 1;
rec(beg, mid, 2 * k + 1);
rec(mid, end, 2 * k + 2);
tree[k] = tree[2 * k + 1] * tree[2 * k + 2];
}
};
rec(0, s, 0);
vector<R> res(s);
function< void(const poly&, int, int, int) > rec2 = [&](const poly& g, int beg, int end, int k) {
auto r = g.rem(tree[k]);
if (end - beg <= 32) {
rep(i, beg, end) res[i] = r.evaluate(points[i]);
} else {
int mid = (beg + end) >> 1;
rec2(r, beg, mid, 2 * k + 1);
rec2(r, mid, end, 2 * k + 2);
}
};
rec2(f, 0, s, 0);
return res;
}
private:
// f * g
static void amul(const R* a, int sa, const R* b, int sb, R* res, int prec, R* buff=nullptr) {
if (sa < sb) return amul(b, sb, a, sa, res, prec, buff);
if (prec < 0) prec = max(0, sa + sb - 1);
sa = min(sa, prec);
sb = min(sb, prec);
if (sb < KARATSUBA_CUTOFF) {
mul_basecase(a, sa, b, sb, res, prec);
} else {
// ...
vector<R> temp;
if (buff == nullptr) {
temp = vector<R>(8 * sa + 100);
buff = temp.data();
}
int q = sa / sb, r = sa % sb;
if (r > 0 && q * std::pow(sa / float(q), 1.59) > (q + 1) * std::pow(sb, 1.59)) q += 1;
int s = (sa + q - 1) / q;
if (sb * q < sa) {
copy(b, b + sb, buff); fill(buff + sb, buff + s, 0); b = buff; buff += s; sb = s;
}
if (sb * q > sa) {
copy(a, a + sa, buff); fill(buff + sa, buff + sb * q, 0); a = buff; buff += sb * q;
}
fill(res, res + prec, 0);
rep(i, q) {
mul_karatsuba(a + i * sb, b, sb, buff, buff + 2 * sb - 1);
rep(j, i * sb, min((i + 2) * sb - 1, prec)) add(res[j], buff[j - i * sb]);
}
}
}
static void mul_karatsuba(const R* a, const R* b, int s, R* res, R* buff) {
if (s <= KARATSUBA_CUTOFF) {
return mul_basecase(a, s, b, s, res, 2 * s - 1);
}
int sh = s / 2, sl = s - s / 2;
mul_karatsuba(a, b, sl, res, buff);
res[2 * sl - 1] = 0;
mul_karatsuba(a + sl, b + sl, sh, res + 2 * sl, buff);
auto* q1 = buff; copy(a, a + sl, q1); buff += sl;
auto* q2 = buff; copy(b, b + sl, q2); buff += sl;
auto* r1 = buff; buff += 2 * sl;
rep(i, sh) add(q1[i], a[i + sl]);
if (a != b) {
rep(i, sh) add(q2[i], b[i + sl]);
} else {
q2 = q1;
}
mul_karatsuba(q1, q2, sl, r1, buff);
rep(i, 2 * sl - 1) sub(r1[i], res[i]);
rep(i, 2 * sh - 1) sub(r1[i], res[i + 2 * sl]);
rep(i, 2 * sl - 1) add(res[i + sl], r1[i]);
buff -= 4 * sl;
}
static void square_basecase(const R* a, int s, R* res, int prec=-1) {
if (prec < 0) prec = max(0, 2 * s - 1);
tmp64.assign(prec, 0);
rep(i, s) tmp64[2 * i] = u64(a[i]) * a[i];
rep(i, s) if (a[i]) {
u32 c = (a[i] << 1) % mod;
rep(j, i + 1, min(prec - i, s)) add64(tmp64[i + j], u64(c) * a[j]);
}
rep(i, prec) res[i] = tmp64[i] % mod;
}
static void mul_basecase(const R* a, int sa, const R* b, int sb, R* res, int prec=-1) {
if (a == b) return square_basecase(a, sa, res, prec);
if (prec < 0) prec = max(0, sa + sb - 1);
tmp64.assign(prec, 0);
rep(i, sb) if (b[i]) rep(j, min(prec - i, sa)) add64(tmp64[i + j], u64(b[i]) * a[j]);
rep(i, prec) res[i] = tmp64[i] % mod;
}
// f % g
static void divmod_dc32(R* a, int sa, const R* b, int sb, R* buff) {
if (sa < sb) return;
int d = sa - sb;
divmod_dc21(a, 2 * d + 1, b, d + 1, buff);
amul(a, d + 1, b + d + 1, sb - (d + 1), buff, sb - 1, buff + sb - 1);
rep(i, sb - 1) sub(a[sa - 1 - i], buff[sb - 2 - i]);
}
static void divmod_dc21(R* a, int sa, const R* b, int sb, R* buff) {
if (sb < DIV_CUTOFF || sa - sb < DIV_CUTOFF) {
return divmod_basecase(a, sa, b, sb, a, a + sa - sb + 1);
}
int h = sb >> 1;
if (sa - h >= sb) {
divmod_dc32(a, sa - h, b, sb, buff);
divmod_dc32(a + (sa - h) - (sb - 1), h + (sb - 1), b, sb, buff);
} else {
divmod_dc32(a, sa, b, sb, buff);
}
}
static void divmod_dc(const R* a, int sa, const R* b, int sb, R* q, R* r) {
assert(sa >= sb);
int dq = sa / sb, dr = sa % sb;
vector<R> tmp(vector<R>(a, a + sa)), buff(8 * sb + 100, 0);
auto* t = tmp.data();
rep(i, dq) {
int end = dr + sb * (i + 1);
int beg = max(0, end - (2 * sb - 1));
divmod_dc21(t + beg, end - beg, b, sb, buff.data());
}
rep(i, sa - sb + 1) q[i] = t[i];
rep(i, sb - 1) r[i] = t[i + sa - sb + 1];
}
static void divmod_basecase(const R* a, int sa, const R* b, int sb, R* q, R* r) {
assert(sb >= 1 && b[0] == 1);
tmp64.resize(sa);
rep(i, sa) tmp64[i] = a[i];
int d = sa - sb + 1;
rep(i, d) {
R c = tmp64[i] % mod;
if (c) rep(j, 1, sb) add64(tmp64[i + j], u64(mod - c) * b[j]);
q[i] = c;
}
rep(i, d, sa) r[i - d] = tmp64[i] % mod;
}
public:
vector<R> coefs;
static R mod;
static u64 lmod;
static vector<R> facts, ifacts, invs;
static vector<u64> tmp64;
};
R poly::mod;
u64 poly::lmod;
vector<R> poly::facts, poly::ifacts, poly::invs;
vector<u64> poly::tmp64;
pair<R, vector<R>> calc_facts(R N, R MOD) {
R v = sqrt(N);
vector<R> cs(v);
rep(i, v) cs[i] = i + 1;
auto f = poly::expand(cs);
rep(i, v) cs[i] = v * i;
auto vs = poly::multipoint_evaluation(f, cs);
rep(i, 1, v) vs[i] = u64(vs[i-1]) * vs[i] % MOD;
return make_pair(v, vs);
}
void solve() {
const u32 MOD = 1e9 + 7;
poly::init_mod(0, MOD);
auto pow_mod = poly::pow_mod;
auto p = calc_facts(MOD / 2, MOD);
const R d = p.first;
auto& facts = p.second;
function< u32(u32) > fact = [&](R n) {
if (n >= MOD) return u32(0);
if (n > MOD / 2) {
n = MOD - 1 - n;
return u32(u64(pow_mod(fact(n), MOD - 2)) * (n & 1 ? 1 : MOD - 1) % MOD);
}
R q = min(d, n / d);
R ret = (q > 0) ? facts[q - 1] : 1;
rep(i, q * d + 1, n + 1) ret = u64(ret) * i % MOD;
return ret;
};
u32 T; scanf("%u", &T);
rep(_, T) {
static char C[10010], P[10010];
scanf("%s %s", C, P);
int len_C = strlen(C);
int len_P = strlen(P);
u32 ans = 0;
if (len_P <= 10) {
u64 p = atoll(P);
u64 c = 0;
rep(i, len_C) {
c = c * 10 + (C[i] - '0');
if (c >= 2 * MOD) c = c % MOD + 2 * MOD;
}
if (p < MOD && c >= 2 * p - 1) {
c = (c + 1 + MOD - p) % MOD;
if (c >= p) ans = u64(fact(c)) * pow_mod(fact(c - p), MOD - 2) % MOD;
}
}
printf("%u\n", ans);
}
}
int main() {
clock_t beg = clock();
solve();
clock_t end = clock();
fprintf(stderr, "%.3f sec\n", double(end - beg) / CLOCKS_PER_SEC);
return 0;
}