結果
問題 | No.906 Y字グラフ |
ユーザー |
|
提出日時 | 2019-10-11 21:52:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 70 ms / 2,000 ms |
コード長 | 4,034 bytes |
コンパイル時間 | 2,406 ms |
コンパイル使用メモリ | 194,348 KB |
最終ジャッジ日時 | 2025-01-07 21:37:49 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))#define ALL(x) std::begin(x), std::end(x)using namespace std;inline constexpr int32_t modpow(uint_fast64_t x, uint64_t k, int32_t MOD) {assert (0 <= x and x < MOD);uint_fast64_t y = 1;for (; k; k >>= 1) {if (k & 1) (y *= x) %= MOD;(x *= x) %= MOD;}assert (0 <= y and y < MOD);return y;}inline int32_t modinv(int32_t value, int32_t MOD) {assert (0 <= value and value < MOD);assert (value != 0);int64_t a = value, b = MOD;int64_t x = 0, y = 1;for (int64_t u = 1, v = 0; a; ) {int64_t q = b / a;x -= q * u; std::swap(x, u);y -= q * v; std::swap(y, v);b -= q * a; std::swap(b, a);}assert (value * x + MOD * y == b and b == 1);if (x < 0) x += MOD;assert (0 <= x and x < MOD);return x;}template <int32_t MOD>struct mint {int32_t value;mint() : value() {}mint(int64_t value_) : value(value_ < 0 ? value_ % MOD + MOD : value_ >= MOD ? value_ % MOD : value_) {}mint(int32_t value_, std::nullptr_t) : value(value_) {}explicit operator bool() const { return value; }inline constexpr mint<MOD> operator + (mint<MOD> other) const { return mint<MOD>(*this) += other; }inline constexpr mint<MOD> operator - (mint<MOD> other) const { return mint<MOD>(*this) -= other; }inline constexpr mint<MOD> operator * (mint<MOD> other) const { return mint<MOD>(*this) *= other; }inline constexpr mint<MOD> & operator += (mint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this;}inline constexpr mint<MOD> & operator -= (mint<MOD> other) { this->value -= other.value; if (this->value < 0) this->value += MOD; return *this;}inline constexpr mint<MOD> & operator *= (mint<MOD> other) { this->value = (uint_fast64_t)this->value * other.value % MOD; return *this; }inline constexpr mint<MOD> operator - () const { return mint<MOD>(this->value ? MOD - this->value : 0, nullptr); }inline constexpr mint<MOD> pow(uint64_t k) const { return mint<MOD>(modpow(value, k, MOD), nullptr); }inline mint<MOD> inv() const { return mint<MOD>(modinv(value, MOD), nullptr); }inline constexpr mint<MOD> operator / (mint<MOD> other) const { return *this * other.inv(); }inline constexpr mint<MOD> operator /= (mint<MOD> other) { return *this *= other.inv(); }inline constexpr bool operator == (mint<MOD> other) const { return value == other.value; }inline constexpr bool operator != (mint<MOD> other) const { return value != other.value; }};template <int32_t MOD> mint<MOD> operator * (int64_t value, mint<MOD> n) { return mint<MOD>(value) * n; }template <int32_t MOD> std::istream & operator >> (std::istream & in, mint<MOD> & n) { int64_t value; in >> value; n = value; return in; }template <int32_t MOD> std::ostream & operator << (std::ostream & out, mint<MOD> n) { return out << n.value; }/*** @note O(r)*/template <int32_t MOD>mint<MOD> simple_choose(int64_t n, int32_t r) {assert (0 <= r and r <= n);mint<MOD> num = 1;mint<MOD> den = 1;REP (i, r) {num *= n - i;den *= i + 1;}return num / den;}constexpr int MOD = 1e9 + 7;mint<MOD> solve(int64_t n) {int64_t k = n - 4;mint<MOD> unsorted = simple_choose<MOD>(k + 2, 2);mint<MOD> all_same = (k % 3 == 0 ? 1 : 0);mint<MOD> two_same = mint<MOD>(k / 2 + 1) - all_same; // sortedmint<MOD> distinct = (unsorted - all_same - 3 * two_same) / 6;return all_same + two_same + distinct;}int main() {int64_t n; cin >> n;cout << solve(n) << endl;return 0;}