#include #define ADD(a, b) a = (a + ll(b)) % mod #define MUL(a, b) a = (a * ll(b)) % mod #define MAX(a, b) a = max(a, b) #define MIN(a, b) a = min(a, b) #define rep(i, a, b) for(int i = int(a); i < int(b); i++) #define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--) #define all(a) (a).begin(), (a).end() #define sz(v) (int)(v).size() #define pb push_back #define sec second #define fst first #define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl; typedef pair ppi; typedef vector vi; typedef vector vl; typedef vector mat; typedef complex comp; void Debug() {cout << '\n'; } templatevoid Debug(FIRST arg, REST... rest){ cout<ostream& operator<<(ostream& out,const vector& v) { out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<ostream& operator<<(ostream& out,const pair& v){ out<<"("<& B) { //bit vectors, S x S + 1 dimentions int S = sz(B); int r = 0; vector used(S, 0); rep(i, 0, S) { int pivot = -1; rep(j, 0, S) { if(B[j][i] & !used[j]) pivot = j; } if(pivot == -1) continue; r++; swap(B[i], B[pivot]); used[i] = true; rep(j, 0, S) { if(i != j && B[j][i]) { rep(k, 0, S + 1) B[j][k] ^= B[i][k]; } } } return r; } vector gauss_jordan(const vector>& A, const vector& b) { //watch out for precision!!!!!!! int n = sz(A); vector> B(n, vector(n + 1)); rep(i, 0, n) rep(j, 0, n) B[i][j] = A[i][j]; rep(i, 0, n) B[i][n] = b[i]; rep(i, 0, n) { int pivot = i; rep(j, i, n) { if(abs(B[j][i]) > abs(B[pivot][i])) pivot = j; } swap(B[i], B[pivot]); if(abs(B[i][i]) < eps) return vector(); rep(j, i + 1, n + 1) B[i][j] /= B[i][i]; rep(j, 0, n) { if(i != j) { rep(k, i + 1, n + 1) B[j][k] -= B[j][i] * B[i][k]; } } } vector x(n); rep(i, 0, n) x[i] = B[i][n]; return x; } ///////////////////////////////////////////////////////////////// int N, M; double C[MAX_N]; double dp[MAX_N]; void solve() { cin >> N >> M; rep(i, 1, N - 1) cin >> C[i]; vector> A(N, vector(N, 0.0)); vector b(N, 0.0); rep(i, 0, N) { A[i][i] = 1.0; rep(j, 1, M + 1) { if(i + j != N - 1) { b[i] += 1.0 / M * C[(i + j) % N]; A[i][(i + j) % N] -= 1.0 / M; } } } b = gauss_jordan(A, b); // debug(b); rer(i, N - 1, 0) { if(i + M >= N - 1) dp[i] = 0; else { double tmp = 0; rep(j, 1, M + 1) { tmp += 1.0 / M * (dp[i + j] + C[i + j]); } dp[i] = min(tmp, b[i]); rep(j, 1, M + 1) { MIN(dp[i], b[i + j] + C[i + j]); } } } cout << dp[0] << "\n"; } int main() { #ifndef LOCAL ios::sync_with_stdio(false); cin.tie(0); #endif cout << fixed; cout.precision(20); srand((unsigned int)time(NULL)); #ifdef LOCAL //freopen("in.txt", "wt", stdout); //for tester freopen("in.txt", "rt", stdin); #endif solve(); #ifdef LOCAL cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; #endif return 0; }