#include #define REP_(i, a_, b_, a, b, ...) \ for (int i = (a), END_##i = (b); i < END_##i; ++i) #define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) #define ALL(x) std::begin(x), std::end(x) using i64 = long long; using Real = double; template inline bool chmax(T &a, U b) { return a < b and ((a = std::move(b)), true); } template inline bool chmin(T &a, U b) { return a > b and ((a = std::move(b)), true); } template inline int ssize(const T &a) { return (int) a.size(); } template inline std::ostream &print_one(const T &x, char endc) { if constexpr (std::is_same_v) { return std::cout << (x ? "Yes" : "No") << endc; } else { return std::cout << x << endc; } } template inline std::ostream &print(const T &x) { return print_one(x, '\n'); } template std::ostream &print(const T &head, Ts... tail) { return print_one(head, ' '), print(tail...); } inline std::ostream &print() { return std::cout << '\n'; } template std::ostream &print_seq(const Container &a, std::string_view sep = " ", std::string_view ends = "\n", std::ostream &os = std::cout) { auto b = std::begin(a), e = std::end(a); for (auto it = std::begin(a); it != e; ++it) { if (it != b) os << sep; os << *it; } return os << ends; } template struct is_iterable : std::false_type {}; template struct is_iterable())), decltype(std::end(std::declval()))>> : std::true_type { }; template::value && !std::is_same::value>> std::ostream &operator<<(std::ostream &os, const T &a) { return print_seq(a, ", ", "", (os << "{")) << "}"; } struct CastInput { template operator T() const { T x; std::cin >> x; return x; } struct Sized { std::size_t n; template operator T() const { T x(n); for (auto &e: x) std::cin >> e; return x; } }; Sized operator()(std::size_t n) const { return {n}; } } const in; inline void check(bool cond, const char *message = "!ERROR!") { if (not cond) throw std::runtime_error(message); } #ifdef MY_DEBUG #include "debug_dump.hpp" #else #define DUMP(...) #define cerr if(false)std::cerr #endif using namespace std; namespace FastFourierTransform { struct C { Real x, y; C() : x(0), y(0) {} C(Real x, Real y) : x(x), y(y) {} inline C operator+(const C &c) const { return C(x + c.x, y + c.y); } inline C operator-(const C &c) const { return C(x - c.x, y - c.y); } inline C operator*(const C &c) const { return C(x * c.x - y * c.y, x * c.y + y * c.x); } inline C conj() const { return C(x, -y); } }; const Real PI = acosl(-1); int base = 1; vector rts = {{0, 0}, {1, 0}}; vector rev = {0, 1}; void ensure_base(int nbase) { if (nbase <= base) return; rev.resize(1 << nbase); rts.resize(1 << nbase); for (int i = 0; i < (1 << nbase); i++) { rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1)); } while (base < nbase) { Real angle = PI * 2.0 / (1 << (base + 1)); for (int i = 1 << (base - 1); i < (1 << base); i++) { rts[i << 1] = rts[i]; Real angle_i = angle * (2 * i + 1 - (1 << base)); rts[(i << 1) + 1] = C(cos(angle_i), sin(angle_i)); } ++base; } } void fft(vector &a, int n) { assert((n & (n - 1)) == 0); int zeros = __builtin_ctz(n); ensure_base(zeros); int shift = base - zeros; for (int i = 0; i < n; i++) { if (i < (rev[i] >> shift)) { swap(a[i], a[rev[i] >> shift]); } } for (int k = 1; k < n; k <<= 1) { for (int i = 0; i < n; i += 2 * k) { for (int j = 0; j < k; j++) { C z = a[i + j + k] * rts[j + k]; a[i + j + k] = a[i + j] - z; a[i + j] = a[i + j] + z; } } } } vector multiply(const vector &a, const vector &b) { int need = (int) a.size() + (int) b.size() - 1; int nbase = 1; while ((1 << nbase) < need) nbase++; ensure_base(nbase); int sz = 1 << nbase; vector fa(sz); for (int i = 0; i < sz; i++) { Real x = (i < (int) a.size() ? a[i] : 0); Real y = (i < (int) b.size() ? b[i] : 0); fa[i] = C(x, y); } fft(fa, sz); C r(0, -0.25 / (sz >> 1)), s(0, 1), t(0.5, 0); for (int i = 0; i <= (sz >> 1); i++) { int j = (sz - i) & (sz - 1); C z = (fa[j] * fa[j] - (fa[i] * fa[i]).conj()) * r; fa[j] = (fa[i] * fa[i] - (fa[j] * fa[j]).conj()) * r; fa[i] = z; } for (int i = 0; i < (sz >> 1); i++) { C A0 = (fa[i] + fa[i + (sz >> 1)]) * t; C A1 = (fa[i] - fa[i + (sz >> 1)]) * t * rts[(sz >> 1) + i]; fa[i] = A0 + A1 * s; } fft(fa, sz >> 1); vector ret(need); for (int i = 0; i < need; i++) { ret[i] = (i & 1) ? fa[i >> 1].y : fa[i >> 1].x; } return ret; } } template struct FloatMult { using value_type = Real; static constexpr int dmax() { return DMAX; } static std::vector multiply(const std::vector &x, const std::vector &y) { auto res = FastFourierTransform::multiply(x, y); if (int(res.size()) > DMAX + 1) res.resize(DMAX + 1); // shrink return res; } static std::vector invert(const std::vector &x) { assert(false); // not implemented } }; template struct NaiveMult { using value_type = T; static constexpr int dmax() { return DMAX; } static std::vector multiply(const std::vector &x, const std::vector &y) { const int n = std::min(x.size() + y.size() - 1, DMAX + 1); const int mi = std::min(x.size(), n); std::vector res(n); for (int i = 0; i < mi; ++i) { for (int j = 0; j < int(y.size()); ++j) { if (i + j >= n) break; res[i + j] += x[i] * y[j]; } } return res; } static std::vector invert(const std::vector &x) { std::vector res(DMAX + 1); res[0] = x[0].inv(); for (int i = 1; i <= DMAX; ++i) { T s = 0; const int mj = std::min(i + 1, x.size()); for (int j = 1; j < mj; ++j) { s += x[j] * res[i - j]; } res[i] = -res[0] * s; } return res; } }; // Formal Power Series (dense format). template struct DenseFPS { using T = typename Mult::value_type; static constexpr int dmax() { return Mult::dmax(); } // Coefficients of terms from x^0 to x^DMAX. std::vector coeff_; DenseFPS() : coeff_(1, 0) {} // = 0 * x^0 explicit DenseFPS(std::vector c) : coeff_(std::move(c)) { while (size() > dmax() + 1) coeff_.pop_back(); assert(size() > 0); } DenseFPS(std::initializer_list init) : coeff_(init.begin(), init.end()) { while (size() > dmax() + 1) coeff_.pop_back(); assert(size() > 0); } DenseFPS(const DenseFPS &other) : coeff_(other.coeff_) {} DenseFPS(DenseFPS &&other) : coeff_(std::move(other.coeff_)) {} DenseFPS &operator=(const DenseFPS &other) { coeff_ = other.coeff_; return *this; } DenseFPS &operator=(DenseFPS &&other) { coeff_ = std::move(other.coeff_); return *this; } // size <= dmax + 1 inline int size() const { return static_cast(coeff_.size()); } // Returns the coefficient of x^k. inline T operator[](int k) const { return (k >= size()) ? 0 : coeff_[k]; } DenseFPS &operator+=(const T &scalar) { coeff_[0] += scalar; return *this; } friend DenseFPS operator+(const DenseFPS &f, const T &scalar) { return DenseFPS(f) += scalar; } DenseFPS &operator+=(const DenseFPS &other) { if (size() < other.size()) coeff_.resize(other.size()); for (int i = 0; i < other.size(); ++i) coeff_[i] += other[i]; return *this; } friend DenseFPS operator+(const DenseFPS &f, const DenseFPS &g) { return DenseFPS(f) += g; } DenseFPS &operator-=(const DenseFPS &other) { if (size() < other.size()) coeff_.resize(other.size()); for (int i = 0; i < other.size(); ++i) coeff_[i] -= other[i]; return *this; } friend DenseFPS operator-(const DenseFPS &f, const DenseFPS &g) { return DenseFPS(f) -= g; } DenseFPS operator-() const { return *this * -1; } DenseFPS &operator*=(const T &scalar) { for (auto &x: coeff_) x *= scalar; return *this; } friend DenseFPS operator*(const DenseFPS &f, const T &scalar) { return DenseFPS(f) *= scalar; } friend DenseFPS operator*(const T &scalar, const DenseFPS &g) { return DenseFPS{scalar} *= g; } DenseFPS &operator*=(const DenseFPS &other) { return *this = DenseFPS(Mult::multiply(std::move(this->coeff_), other.coeff_)); } friend DenseFPS operator*(const DenseFPS &f, const DenseFPS &g) { return DenseFPS(Mult::multiply(f.coeff_, g.coeff_)); } DenseFPS &operator/=(const T &scalar) { for (auto &x: coeff_) x /= scalar; return *this; } friend DenseFPS operator/(const DenseFPS &f, const T &scalar) { return DenseFPS(f) /= scalar; } friend DenseFPS operator/(const T &scalar, const DenseFPS &g) { return DenseFPS{scalar} /= g; } DenseFPS &operator/=(const DenseFPS &other) { return *this *= DenseFPS(Mult::invert(other.coeff_)); } friend DenseFPS operator/(const DenseFPS &f, const DenseFPS &g) { return f * DenseFPS(Mult::invert(g.coeff_)); } DenseFPS pow(i64 t) const { assert(t >= 0); DenseFPS res = {1}, base = *this; while (t) { if (t & 1) res *= base; base *= base; t >>= 1; } return res; } // Multiplies by (1 + c * x^k). void multiply2_inplace(int k, int c) { assert(k > 0); if (size() <= dmax()) { coeff_.resize(min(size() + k, dmax() + 1), 0); } for (int i = size() - 1; i >= k; --i) { coeff_[i] += coeff_[i - k] * c; } } // Multiplies by (1 + c * x^k). DenseFPS multiply2(int k, int c) const { DenseFPS res = *this; res.multiply2_inplace(k, c); return res; } // Divides by (1 + c * x^k). void divide2_inplace(int k, int c) { assert(k > 0); for (int i = k; i < size(); ++i) { coeff_[i] -= coeff_[i - k] * c; } } // Divides by (1 + c * x^k). DenseFPS divide2(int k, int c) const { DenseFPS res = *this; res.divide2_inplace(k, c); return res; } }; constexpr int D = 60; using DF = DenseFPS>; auto solve() { int n = in, K = in; const Real d6 = 1 / 6.0; const Real d3 = 1 / 3.0; DF a = {0, d6, d6, d6, d6, d6, d6}; DF b = {0, 0, 0, 0, d3, d3, d3}; DF f = a.pow(n - K) * b.pow(K); DF g = a.pow(n); g.divide2_inplace(1, -1); // cumsum Real ans = 0; for (int i = 1; i <= D; ++i) { ans += f[i] * g[i - 1]; } return ans; } int main() { ios_base::sync_with_stdio(false), cin.tie(nullptr); cout << std::fixed << std::setprecision(18); const int T = 1;//in; REP(t, T) { auto ans = solve(); print(ans); } }