test/yukicoder/660/main.test.cpp
Depends on
Code
#define PROBLEM "https://yukicoder.me/problems/no/660"
#include <iostream>
#include <vector>
#include "Mylib/Combinatorics/catalan_number.cpp"
#include "Mylib/Combinatorics/factorial_table.cpp"
#include "Mylib/Number/Mint/mint.cpp"
namespace hl = haar_lib;
using mint = hl::modint<1000000007>;
const static auto ft = hl::factorial_table<mint>(500000);
int main() {
int N;
std::cin >> N;
std::vector<mint> c(N + 1);
for (int i = 0; i <= N; ++i) {
c[i] = hl::catalan_number<ft>(i);
}
for (int i = 1; i <= N; ++i) {
c[i] += c[i - 1];
}
mint ans = 0;
for (int k = 0; k <= N / 2; ++k) {
ans += ft.C(N + 2 * k, k);
}
for (int k = 0; k < N / 2; ++k) {
ans -= ft.C(N + 2 * k, k) * c[N / 2 - k - 1] * 2;
}
std::cout << ans << std::endl;
return 0;
}
#line 1 "test/yukicoder/660/main.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/660"
#include <iostream>
#include <vector>
#line 2 "Mylib/Combinatorics/catalan_number.cpp"
#include <cstdint>
#line 2 "Mylib/Combinatorics/factorial_table.cpp"
#include <cassert>
#line 5 "Mylib/Combinatorics/factorial_table.cpp"
namespace haar_lib {
template <typename T>
class factorial_table {
public:
using value_type = T;
private:
int N_;
std::vector<T> f_table_, if_table_;
public:
factorial_table() {}
factorial_table(int N) : N_(N) {
f_table_.assign(N + 1, 1);
if_table_.assign(N + 1, 1);
for (int i = 1; i <= N; ++i) {
f_table_[i] = f_table_[i - 1] * i;
}
if_table_[N] = f_table_[N].inv();
for (int i = N; --i >= 0;) {
if_table_[i] = if_table_[i + 1] * (i + 1);
}
}
T factorial(int64_t i) const {
assert(0 <= i and i <= N_);
return f_table_[i];
}
T inv_factorial(int64_t i) const {
assert(0 <= i and i <= N_);
return if_table_[i];
}
T P(int64_t n, int64_t k) const {
if (n < k or n < 0 or k < 0) return 0;
return factorial(n) * inv_factorial(n - k);
}
T C(int64_t n, int64_t k) const {
if (n < k or n < 0 or k < 0) return 0;
return P(n, k) * inv_factorial(k);
}
T H(int64_t n, int64_t k) const {
if (n == 0 and k == 0) return 1;
return C(n + k - 1, k);
}
};
} // namespace haar_lib
#line 4 "Mylib/Combinatorics/catalan_number.cpp"
namespace haar_lib {
template <const auto &ft>
auto catalan_number(int64_t n) {
return ft.C(2 * n, n) - ft.C(2 * n, n - 1);
}
} // namespace haar_lib
#line 3 "Mylib/Number/Mint/mint.cpp"
#include <utility>
namespace haar_lib {
template <int32_t M>
class modint {
uint32_t val_;
public:
constexpr static auto mod() { return M; }
constexpr modint() : val_(0) {}
constexpr modint(int64_t n) {
if (n >= M)
val_ = n % M;
else if (n < 0)
val_ = n % M + M;
else
val_ = n;
}
constexpr auto &operator=(const modint &a) {
val_ = a.val_;
return *this;
}
constexpr auto &operator+=(const modint &a) {
if (val_ + a.val_ >= M)
val_ = (uint64_t) val_ + a.val_ - M;
else
val_ += a.val_;
return *this;
}
constexpr auto &operator-=(const modint &a) {
if (val_ < a.val_) val_ += M;
val_ -= a.val_;
return *this;
}
constexpr auto &operator*=(const modint &a) {
val_ = (uint64_t) val_ * a.val_ % M;
return *this;
}
constexpr auto &operator/=(const modint &a) {
val_ = (uint64_t) val_ * a.inv().val_ % M;
return *this;
}
constexpr auto operator+(const modint &a) const { return modint(*this) += a; }
constexpr auto operator-(const modint &a) const { return modint(*this) -= a; }
constexpr auto operator*(const modint &a) const { return modint(*this) *= a; }
constexpr auto operator/(const modint &a) const { return modint(*this) /= a; }
constexpr bool operator==(const modint &a) const { return val_ == a.val_; }
constexpr bool operator!=(const modint &a) const { return val_ != a.val_; }
constexpr auto &operator++() {
*this += 1;
return *this;
}
constexpr auto &operator--() {
*this -= 1;
return *this;
}
constexpr auto operator++(int) {
auto t = *this;
*this += 1;
return t;
}
constexpr auto operator--(int) {
auto t = *this;
*this -= 1;
return t;
}
constexpr static modint pow(int64_t n, int64_t p) {
if (p < 0) return pow(n, -p).inv();
int64_t ret = 1, e = n % M;
for (; p; (e *= e) %= M, p >>= 1)
if (p & 1) (ret *= e) %= M;
return ret;
}
constexpr static modint inv(int64_t a) {
int64_t b = M, u = 1, v = 0;
while (b) {
int64_t t = a / b;
a -= t * b;
std::swap(a, b);
u -= t * v;
std::swap(u, v);
}
u %= M;
if (u < 0) u += M;
return u;
}
constexpr static auto frac(int64_t a, int64_t b) { return modint(a) / modint(b); }
constexpr auto pow(int64_t p) const { return pow(val_, p); }
constexpr auto inv() const { return inv(val_); }
friend constexpr auto operator-(const modint &a) { return modint(M - a.val_); }
friend constexpr auto operator+(int64_t a, const modint &b) { return modint(a) + b; }
friend constexpr auto operator-(int64_t a, const modint &b) { return modint(a) - b; }
friend constexpr auto operator*(int64_t a, const modint &b) { return modint(a) * b; }
friend constexpr auto operator/(int64_t a, const modint &b) { return modint(a) / b; }
friend std::istream &operator>>(std::istream &s, modint &a) {
s >> a.val_;
return s;
}
friend std::ostream &operator<<(std::ostream &s, const modint &a) {
s << a.val_;
return s;
}
template <int N>
static auto div() {
static auto value = inv(N);
return value;
}
explicit operator int32_t() const noexcept { return val_; }
explicit operator int64_t() const noexcept { return val_; }
};
} // namespace haar_lib
#line 8 "test/yukicoder/660/main.test.cpp"
namespace hl = haar_lib;
using mint = hl::modint<1000000007>;
const static auto ft = hl::factorial_table<mint>(500000);
int main() {
int N;
std::cin >> N;
std::vector<mint> c(N + 1);
for (int i = 0; i <= N; ++i) {
c[i] = hl::catalan_number<ft>(i);
}
for (int i = 1; i <= N; ++i) {
c[i] += c[i - 1];
}
mint ans = 0;
for (int k = 0; k <= N / 2; ++k) {
ans += ft.C(N + 2 * k, k);
}
for (int k = 0; k < N / 2; ++k) {
ans -= ft.C(N + 2 * k, k) * c[N / 2 - k - 1] * 2;
}
std::cout << ans << std::endl;
return 0;
}
Back to top page
Modint
(Mylib/Number/Mint/mint.cpp)