提出 #31644007

---

ソースコード 拡げる

#include <iostream>
#include <utility>
#include <vector>
using namespace std;

#include "atcoder/modint.hpp"
using mint = atcoder::static_modint<7>;
struct Binomial {
  vector<mint> fac, invfac, inv;
  Binomial(int n) : fac(n + 1), invfac(n + 1), inv(n + 1) {
    fac[0] = invfac[0] = inv[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i;
    invfac[n] = fac[n].inv();
    for (int i = n - 1; i >= 0; i--) {
      invfac[i] = invfac[i + 1] * (i + 1);
      inv[i + 1] = invfac[i + 1] * fac[i];
    }
  }
  mint operator()(int n, int r) {
    if (n < 0 || r < 0 || n < r) return 0;
    return fac[n] * invfac[n - r] * invfac[r];
  }
} C{6};

constexpr int p = 7;

// return binom(n, r)
mint binom(int n, int r) {
  if (n < 0 or r < 0 or n < r) return 0;
  if (n < p) return C(n, r);
  mint res = 1;
  while (n) {
    if (n % p < r % p) return 0;
    res *= C(n % p, r % p);
    n = n / p, r = r / p;
  }
  return res;
}

// return ( {sum_{r=0...R-1} binom(N, r)}, binom(N, R) )
pair<mint, mint> binom_acc(int n, int R) {
  if (R <= 0) return {0, (R == 0 ? 1 : 0) % p};
  auto [sum, bin] = binom_acc(n / p, R / p);
  sum *= (1 << (n % p));
  for (int r = R / p * p; r < R; r++) sum += bin * binom(n % p, r % p);
  bin *= binom(n % p, R % p);
  return {sum, bin};
}

// enumerate (binom(n, l), ..., binom(n, r) )
vector<mint> binom_enum(int n, int l, int r) {
  if (l == r) return {binom(n, r)};
  auto par = binom_enum(n / p, l / p, r / p);
  int nr = n % p, lr = l % p, lq = l / p;
  vector<mint> res(r - l + 1);
  for (int i = l, ir = lr, iq = lq; i <= r; i++, ir++) {
    if (ir == 7) ir = 0, iq++;
    res[i - l] = par[iq - lq] * binom(nr, ir);
  }
  return res;
}

int main() {
  int N, M, K;
  vector<pair<int, int>> ac;

  cin >> N >> M >> K;
  ac.resize(M);
  for (auto &[a, c] : ac) cin >> a >> c;
  for (int i = 1; i < M; i++) {
    (ac[i - 1].first += p - ac[i].first) %= p;
    ac[i].second += ac[i - 1].second;
  }
  vector<mint> B(K + 1);
  for (auto &[a, c] : ac) {
    int upper = min(N - K, c - 1);
    mint bin = binom_acc(N - K, upper + 1).first;
    int lower = max(0, upper - K);
    auto diff = binom_enum(N - K, lower, upper);
    for (int s = 1; s <= K; s++) {
      int cur_upper = min(N - K, c - s);
      if (cur_upper < upper) {
        if (upper >= 0) {
          bin -= diff.back();
          diff.pop_back();
        }
        upper--;
      }
      B[s] += a * bin;
    }
  }
  for (int i = 1; i <= K; i++) {
    cout << B[i].val() << " \n"[i == K];
  }
}

提出情報

ジャッジ結果