#line 1 "No_75_\u56de\u6570\u306e\u671f\u5f85\u5024\u306e\u554f\u984c.cpp" #define YRSD #line 2 "YRS/all.hpp" #line 2 "YRS/aa/head.hpp" #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define TE template #define TES template #define Z auto #define ep emplace_back #define eb emplace #define fi first #define se second #define all(x) (x).begin(), (x).end() #define OV4(a, b, c, d, e, ...) e #define FOR1(a) for (int _ = 0; _ < (a); ++_) #define FOR2(i, a) for (int i = 0; i < (a); ++i) #define FOR3(i, a, b) for (int i = (a); i < (b); ++i) #define FOR4(i, a, b, c) for (int i = (a); i < (b); i += (c)) #define FOR(...) OV4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__) #define FOR1_R(a) for (int _ = (a) - 1; _ >= 0; --_) #define FOR2_R(i, a) for (int i = (a) - 1; i >= 0; --i) #define FOR3_R(i, a, b) for (int i = (b) - 1; i >= (a); --i) #define FOR4_R(i, a, b, c) for (int i = (b) - 1; i >= (a); i -= (c)) #define FOR_R(...) OV4(__VA_ARGS__, FOR4_R, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__) #define FOR_subset(t, s) for (int t = (s); t > -1; t = (t == 0 ? -1 : (t - 1) & s)) #define sort ranges::sort using namespace std; TE using vc = vector; TE using vvc = vc>; TE using T1 = tuple; TE using T2 = tuple; TE using T3 = tuple; TE using T4 = tuple; TE using max_heap = priority_queue; TE using min_heap = priority_queue, greater>; using u8 = unsigned char; using uint = unsigned int; using ll = long long; using ull = unsigned long long; using ld = long double; using i128 = __int128; using u128 = __uint128_t; using f128 = __float128; using u16 = uint16_t; using PII = pair; using PLL = pair; #ifdef YRSD constexpr bool dbg = 1; #else constexpr bool dbg = 0; #endif #line 2 "YRS/IO/IO.hpp" istream &operator>>(istream &I, i128 &x) { static string s; I >> s; int f = s[0] == '-'; x = 0; const int N = (int)s.size(); FOR(i, f, N) x = x * 10 + s[i] - '0'; if (f) x = -x; return I; } ostream &operator<<(ostream &O, i128 x) { static string s; s.clear(); bool f = x < 0; if (f) x = -x; while (x) s += '0' + x % 10, x /= 10; if (s.empty()) s += '0'; if (f) s += '-'; reverse(all(s)); return O << s; } istream &operator>>(istream &I, f128 &x) { static string s; I >> s, x = stold(s); return I; } ostream &operator<<(ostream &O, const f128 x) { return O << ld(x); } template istream &operator>>(istream &I, tuple &t) { return apply([&I](Z &...s) { ((I >> s), ...); }, t), I; } template istream &operator>>(istream &I, pair &x) { return I >> x.fi >> x.se; } template ostream &operator<<(ostream &O, const pair &x) { return O << x.fi << ' ' << x.se; } TE requires requires(T &c) { begin(c); end(c); } and (not is_same_v, string>) istream &operator>>(istream &I, T &c) { for (Z &e : c) I >> e; return I; } TE requires requires(const T &c) { begin(c); end(c); } and (not is_same_v, const char*>) and (not is_same_v, string>) and (not is_array_v> or not is_same_v>, char>) ostream &operator<<(ostream &O, const T &a) { if (a.empty()) return O; Z i = a.begin(); O << *i++; for (; i != a.end(); ++i) O << ' ' << *i; return O; } void IN() {} TE void IN(T &x, Z &...s) { cin >> x, IN(s...); } void print() { cout << '\n'; } TES void print(T &&x, S &&...y) { cout << x; if constexpr (sizeof...(S)) cout << ' '; print(forward(y)...); } void put() { cout << ' '; } TES void put(T &&x, S &&...y) { cout << x; if constexpr (sizeof...(S)) cout << ' '; put(forward(y)...); } #define INT(...) int __VA_ARGS__; IN(__VA_ARGS__) #define UINT(...) uint __VA_ARGS__; IN(__VA_ARGS__) #define LL(...) ll __VA_ARGS__; IN(__VA_ARGS__) #define ULL(...) ull __VA_ARGS__; IN(__VA_ARGS__) #define I128(...) i128 __VA_ARGS__; IN(__VA_ARGS__) #define STR(...) string __VA_ARGS__; IN(__VA_ARGS__) #define CH(...) char __VA_ARGS__; IN(__VA_ARGS__) #define REAL(...) re __VA_ARGS__; IN(__VA_ARGS__) #define VEC(T, a, n) vc a(n); IN(a) void YES(bool o = 1) { print(o ? "YES" : "NO"); } void Yes(bool o = 1) { print(o ? "Yes" : "No"); } void yes(bool o = 1) { print(o ? "yes" : "no"); } void NO(bool o = 1) { YES(not o); } void No(bool o = 1) { Yes(not o); } void no(bool o = 1) { yes(not o); } void ALICE(bool o = 1) { print(o ? "ALICE" : "BOB"); } void Alice(bool o = 1) { print(o ? "Alice" : "Bob"); } void alice(bool o = 1) { print(o ? "alice" : "bob"); } void BOB(bool o = 1) { ALICE(not o); } void Bob(bool o = 1) { Alice(not o); } void bob(bool o = 1) { alice(not o); } void POSSIBLE(bool o = 1) { print(o ? "POSSIBLE" : "IMPOSSIBLE"); } void Possible(bool o = 1) { print(o ? "Possible" : "Impossible"); } void possible(bool o = 1) { print(o ? "possible" : "impossible"); } void IMPOSSIBLE(bool o = 1) { POSSIBLE(not o); } void Impossible(bool o = 1) { Possible(not o); } void impossible(bool o = 1) { possible(not o); } void TAK(bool o = 1) { print(o ? "TAK" : "NIE"); } void NIE(bool o = 1) { TAK(not o); } #line 5 "YRS/all.hpp" #if (__cplusplus >= 202002L) #include constexpr ld pi = numbers::pi; #endif TE constexpr T inf = numeric_limits::max(); template <> constexpr i128 inf = i128(inf) * 2'000'000'000'000'000'000; template constexpr pair inf> = {inf, inf}; TE constexpr static inline int pc(T x) { return popcount(make_unsigned_t(x)); } constexpr static inline ll len(const Z &a) { return a.size(); } void reverse(Z &a) { reverse(all(a)); } void unique(Z &a) { sort(a); a.erase(unique(all(a)), a.end()); } TE vc inverse(const vc &a) { int N = len(a); vc b(N, -1); FOR(i, N) if (a[i] != -1) b[a[i]] = i; return b; } Z QMAX(const Z &a) { return *max_element(all(a)); } Z QMIN(const Z &a) { return *min_element(all(a)); } constexpr bool chmax(Z &a, const Z &b) { return (a < b ? a = b, 1 : 0); } constexpr bool chmin(Z &a, const Z &b) { return (a > b ? a = b, 1 : 0); } vc argsort(const Z &a) { vc I(len(a)); iota(all(I), 0); sort(I, [&](int i, int k) { return a[i] < a[k] or (a[i] == a[k] and i < k); }); return I; } TE vc rearrange(const vc &a, const vc &I) { int N = len(I); vc b(N); FOR(i, N) b[i] = a[I[i]]; return b; } template vc pre_sum(const vc &a) { int N = len(a); vc c(N + 1); FOR(i, N) c[i + 1] = c[i] + a[i]; if (of == 0) c.erase(c.begin()); return c; } TE constexpr static int topbit(T x) { if (x == 0) return - 1; if constexpr (sizeof(T) <= 4) return 31 - __builtin_clz(x); else return 63 - __builtin_clzll(x); } TE constexpr static int lowbit(T x) { if (x == 0) return -1; if constexpr (sizeof(T) <= 4) return __builtin_ctz(x); else return __builtin_ctzll(x); } TE constexpr T floor(T x, T y) { return x / y - (x % y and (x ^ y) < 0); } TE constexpr T ceil(T x, T y) { return floor(x + y - 1, y); } TE constexpr T bmod(T x, T y) { return x - floor(x, y) * y; } TE constexpr pair divmod(T x, T y) { T q = floor(x, y); return pair{q, x - q * y}; } template T SUM(const Z &v) { return accumulate(all(v), T(0)); } int lb(const Z &a, Z x) { return lower_bound(all(a), x) - a.begin(); } int lb(Z l, Z r, Z x) requires(is_same_v) { return lower_bound(l, r, x) - l; } int ub(const Z &a, Z x) { return upper_bound(all(a), x) - a.begin(); } int ub(Z l, Z r, Z x) requires(is_same_v) { return upper_bound(l, r, x) - l; } template ll bina(Z f, ll l, ll r) { if constexpr (ck) assert(f(l)); while (abs(l - r) > 1) { ll x = (r + l) >> 1; (f(x) ? l : r) = x; } return l; } TE T bina_real(Z f, T l, T r, int c = 100) { while (c--) { T x = (l + r) / 2; (f(x) ? l : r) = x; } return (l + r) / 2; } Z pop(Z &s) { if constexpr (requires { s.pop_back(); }) { Z x = s.back(); return s.pop_back(), x; } else if constexpr (requires { s.top(); }) { Z x = s.top(); return s.pop(), x; } else { Z x = s.front(); return s.pop(), x; } } void setp(int x) { cout << fixed << setprecision(x); } TE inline void sh(vc &a, int N) { a.resize(N, T(0)); } #line 1 "YRS/debug.hpp" #ifdef YRSD void DBG() { cerr << "]" << endl; } TES void DBG(T &&x, S &&...y) { cerr << x; if constexpr (sizeof...(S)) cerr << ", "; DBG(forward(y)...); } #define debug(...) cerr << "[" << __LINE__ << "]: [" #__VA_ARGS__ "] = [", DBG(__VA_ARGS__) void ERR() { cerr << endl; } TES void ERR(T &&x, S &&...y) { cerr << x; if constexpr (sizeof...(S)) cerr << ", "; ERR(forward(y)...); } #define err(...) cerr << "[" << __LINE__ << "]: ", ERR(__VA_ARGS__) #define asser assert #else #define debug(...) void(0721) #define err(...) void(0721) #define asser(...) void(0721) #endif #line 4 "No_75_\u56de\u6570\u306e\u671f\u5f85\u5024\u306e\u554f\u984c.cpp" // #include "YRS/IO/fast_io.hpp" // #include "YRS/random/rng.hpp" #line 2 "YRS/line/mat.hpp" #line 2 "YRS/ds/basic/retsu.hpp" TE struct retsu { int N, M; vc a; retsu(int N, int M, T bs = T()) : N(N), M(M), a(N * M, bs) {} T* operator[](int i) { return a.data() + i * M; } const T* operator[](int i) const { return a.data() + i * M; } void fill(T x) { std::fill(all(a), x); } vc> to_vector() const { vector res(N, vc(M)); FOR(i, N) FOR(k, M) res[i][k] = a[i * M + k]; return res; } }; TE istream &operator>>(istream &I, retsu &a) { for (Z &e : a.a) I >> e; return I; } TE ostream &operator<<(ostream &O, retsu &a) { FOR(i, a.N) FOR(k, a.M) O << a[i][k] << " \n"[k + 1 == a.M and i + 1 != a.N]; return O; } #ifdef FIO TE rd(retsu &a) { for (Z &e : a.a) rd(e); } TE wt(retsu &a) { FOR(i, a.N) { FOR(k, a.M) { if (k) wt(' '); wt(a[i][k]); } if (i != a.M) wt('\n'); } } #endif #line 4 "YRS/line/mat.hpp" // https://codeforces.com/contest/2065/problem/H * // https://www.luogu.com.cn/problem/P3390 pow // https://www.luogu.com.cn/problem/P1939 pow TE struct mat { using mt = mat; int N; retsu a; mat(int N, T x = 0, T bs = 0) : N(N), a(N, N, bs) { if (x != bs) FOR(i, N) a[i][i] = x; } Z operator[](int i) { return a[i]; } Z operator[](int i) const { return a[i]; } mt &operator*=(const mt &p) { assert(N == p.N); mt res(N); FOR(i, N) FOR(j, N) FOR(k, N) res[i][j] += a[i][k] * p[k][j]; return *this = res; } mt &operator+=(const mt &p) { assert(N == p.N); FOR(i, N) FOR(k, N) a[i][k] += p[i][k]; return *this; } mt &operator-=(const mt &p) { assert(N == p.N); FOR(i, N) FOR(k, N) a[i][k] -= p[i][k]; return *this; } mt operator*(const mt &p) const { return mt(*this) *= p; } mt operator+(const mt &p) const { return mt(*this) += p; } mt operator-(const mt &p) const { return mt(*this) -= p; } tuple inv() const { T det = 1; vc> B(N, vc(N)), a = this->a.to_vector(); FOR(i, N) B[i][i] = 1; FOR(i, N) { FOR(k, i, N) if (a[k][i] != 0) { if (i != k) swap(a[i], a[k]), swap(B[i], B[k]), det = -det; break; } if (a[i][i] == 0) return {0, 0, mt(0)}; T c = T(1) / a[i][i]; det *= a[i][i]; FOR(j, i, N) a[i][j] *= c; FOR(j, N) B[i][j] *= c; FOR(k, N) if (i != k) { T c = a[k][i]; FOR(j, i, N) a[k][j] -= a[i][j] * c; FOR(j, N) B[k][j] -= B[i][j] * c; } } mt C(N); FOR(i, N) FOR(k, N) C[i][k] = B[i][k]; return {1, det, C}; } mt pow(ll k) const { mt s(N, 1), a(*this); for (; k; k >>= 1, a *= a) if (k & 1) s *= a; return s; } }; #line 7 "No_75_\u56de\u6570\u306e\u671f\u5f85\u5024\u306e\u554f\u984c.cpp" #define tests 0 #define fl 0 #define DB 10 using re = ld; void Yorisou() { INT(N); mat a(N, 1); FOR(i, N) FOR(k, 1, 7) { if (i + k < N) a[i][i + k] -= 1.l / 6; else if (i + k > N) a[i][0] -= 1.l / 6; } a = get<2>(a.inv()); re s = 0; FOR(i, N) s += a[0][i]; print(s); } #line 1 "YRS/aa/main.hpp" int main() { cin.tie(nullptr)->sync_with_stdio(0); int T = 1; if (fl) cerr.tie(0); if (tests and not fl) IN(T); for (int i = 0; i < T or fl; ++i) { Yorisou(); if (fl and i % DB == 0) cerr << "Case: " << i << '\n'; } return 0; } #line 25 "No_75_\u56de\u6570\u306e\u671f\u5f85\u5024\u306e\u554f\u984c.cpp"