#92693 (C++11) No.148 試験監督（3）

提出ソース

結果

問題	No.148 試験監督（3）
ユーザー	Min_25
提出日時	2016-05-17 15:36:01
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	592 ms / 1,000 ms
コード長	11,378 bytes
コンパイル時間	1,230 ms
コンパイル使用メモリ	94,036 KB
実行使用メモリ	8,700 KB
最終ジャッジ日時	2024-04-15 22:47:56
合計ジャッジ時間	9,673 ms
ジャッジサーバーID （参考情報）	judge3 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	588 ms 8,440 KB
testcase_01	AC	587 ms 8,444 KB
testcase_02	AC	589 ms 8,572 KB
testcase_03	AC	592 ms 8,524 KB
testcase_04	AC	590 ms 8,700 KB
testcase_05	AC	590 ms 8,568 KB
testcase_06	AC	591 ms 8,572 KB
testcase_07	AC	592 ms 8,576 KB
testcase_08	AC	592 ms 8,572 KB
testcase_09	AC	590 ms 8,444 KB
testcase_10	AC	588 ms 8,572 KB
testcase_11	AC	584 ms 8,572 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

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);
      |     ~~~~~^~~~~~~~~~~~~~~

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード