Submission #4794711


Source Code Expand

Copy
#include <cstdint>

template <std::uint_fast64_t Modulus> class modint {
  using u64 = std::uint_fast64_t;

public:
  u64 a;

  constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
  constexpr u64 &value() noexcept { return a; }
  constexpr const u64 &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= Modulus) {
      a -= Modulus;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += Modulus;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % Modulus;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    u64 exp = Modulus - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
};

#include <utility>

template <class T, class U> constexpr T power(T x, U exp) {
  T ret = static_cast<T>(1);
  while (exp) {
    if (exp % static_cast<U>(2) == static_cast<U>(1))
      ret *= x;
    exp /= static_cast<U>(2);
    x *= x;
  }
  return ::std::move(ret);
}

#include <iostream>
#include <vector>

int main() {
  using mint = modint<1000000007>;

  int b, w;
  std::cin >> b >> w;
  int n = b + w;

  std::vector<mint> fact(n);
  fact[0] = 1;
  for (int i = 1; i < n; ++i) {
    fact[i] = fact[i - 1] * i;
  }
  const auto comb = [&fact](int n, int r) {
    return fact[n] / fact[r] / fact[n - r];
  };

  mint p = 0, q = 0;

  for (int i = 1; i <= n; ++i) {
    std::cout << ((mint(1) - p + q) / 2).value() << std::endl;

    if (i >= b) {
      p += comb(i - 1, b - 1) / power(mint(2), i);
    }
    if (i >= w) {
      q += comb(i - 1, w - 1) / power(mint(2), i);
    }
  }

  return 0;
}

Submission Info

Submission Time
Task E - Black or White
User noshi91
Language C++14 (GCC 5.4.1)
Score 700
Code Size 2328 Byte
Status AC
Exec Time 425 ms
Memory 3712 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 3
AC × 15
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
test_01.txt AC 425 ms 3712 KB
test_02.txt AC 226 ms 2048 KB
test_03.txt AC 405 ms 3584 KB
test_04.txt AC 234 ms 2176 KB
test_05.txt AC 333 ms 2944 KB
test_06.txt AC 215 ms 2048 KB
test_07.txt AC 220 ms 2048 KB
test_08.txt AC 282 ms 2560 KB
test_09.txt AC 282 ms 2560 KB
test_10.txt AC 210 ms 1920 KB
test_11.txt AC 206 ms 1920 KB
test_12.txt AC 129 ms 1280 KB