#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long LL;
typedef long double LD;
typedef complex<LD> CMP;
template<typename T>
vector<T> MATMUL(const vector< vector<T> >& a, const vector<T>& v)
{
int N = a.size();
vector<T> u(N);
for(int i=0; i<N; ++i)
for(int j=0; j<N; ++j)
u[i] += a[i][j]*v[j];
return u;
}
template<typename T>
vector< vector<T> > MATMUL(const vector< vector<T> >& a, const vector< vector<T> >& b)
{
int N = a.size();
vector< vector<T> > c(N, vector<T>(N));
for(int i=0; i<N; ++i)
for(int j=0; j<N; ++j)
for(int k=0; k<N; ++k)
c[i][j] += a[i][k]*b[k][j];
return c;
}
template<typename T>
vector<T> MATPOWMUL(vector< vector<T> > a, LL e, vector<T> v)
{
for(; e; e>>=1, a=MATMUL(a,a))
if(e&1)
v = MATMUL(a, v);
return v;
}
class TheSwapsDivOne { public:
double find(vector <string> sequence, int k)
{
const string S = accumulate(sequence.begin(), sequence.end(), string());
const int N = S.size();
// pos[p] = prob that position p is chosen.
vector<double> pos(N);
const double tot_range = (1+N)*N/2;
for(int p=0; p<N; ++p)
pos[p] = (p+1)*(N-p) / tot_range;
double totpos = accumulate(pos.begin(), pos.end(), 0.0);
double e = 0.0;
double pStay = calc_stay(N, k);
cerr<<pStay<<endl;
for(int p=0; p<N; ++p)
e += (S[p]-'0') * (pStay*pos[p] + (1-pStay)*(totpos-pos[p])/(N-1));
return e;
}
double calc_stay(int N, int k)
{
vector<double> v(2);
v[0]=1, v[1]=0;
vector<vector<double> > m(2, vector<double>(2));
double tot = N*(N-1)/2;
m[0][0] = 1 - (N-1)/tot;
m[0][1] = 1 - m[0][0];
m[1][0] = 1 / tot;
m[1][1] = 1 - m[1][0];
v = MATPOWMUL(m, k, v);
return v[0];
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const double& Expected, const double& Received) {
bool ok = (abs(Expected - Received) < 1e-9);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, TheSwapsDivOne().find(sequence, k));}
int main(){
CASE(0)
string sequence_[] = {"4", "77"};
vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof(*sequence_));
int k = 1;
double _ = 10.0;
END
CASE(1)
string sequence_[] = {"4", "77"};
vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof(*sequence_));
int k = 47;
double _ = 10.0;
END
CASE(2)
string sequence_[] = {"1", "1", "1", "1", "1", "1", "1"};
vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof(*sequence_));
int k = 1000000;
double _ = 3.0;
END
CASE(3)
string sequence_[] = {"572685085149095989026478064633266980348504469", "19720257361", "9", "69"};
vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof(*sequence_));
int k = 7;
double _ = 98.3238536775161;
END
CASE(4)
string sequence_[] = {"99119031434359106923816542810422135284590023481","18592326554385368171814861100277565528949239971","40347349899810715843953168648000263567310239924","38545780837311608418115423439501497402166989198","17285424781630234102349525011866340121513596937","99906102414517713148119423844384448210489647741","35143608617481431646437962753059300256206057014","32908347198481001587230423329525311296062283449","30955119911124654515507927745137969614038628659","05701821365741853514177287867868710603678841591","02951150544773501047638874470324652244274992240","66282387551352683966197052118658947485438694285","20252536028765020128833989964714452226508085010","80811331214834847334896900780427326512035360569","64027316291431464504713820313500109516764149897","48129573886929653773255932612216530466998301529","61692290484824339963810865408046132323155270926","20734322892232348414644895848499866768508454499","73977753818895603473393877456222096050605590631","75488083687667238723185124957724344916122502718","49308072322388038375901976579828643039912008068","49852892852425127382418689330961253679008410178","83755665062925303754162008026780205838121715045","71099919823637402309900038552838815087602284423","31494518631250555726432280524959027009811573208","94732518702631054441238939970137000403860659619","10438030120829399294297675572336596166498575107","95527243526745917048414629189698324008548561395","15132318439173982784310911106626381351036355555","05188145876757583124059940284920599124018514160","27896629348785393154614917085869574420611784052","88948023776542624752651009036945985038145092379","77491411686241001644232460531296311373251479662","70651631378830281367796703432742410612411377119","81356659097328268106177924003156451351223361290","57824086176360950782192786893941656905433490072","46805400665194951531366038022986309479083989964","66221676730070159290160046394594552489155178118","43413084875075661605155886091832959565937975007","16576558699206159813455421805523400639947166856","86296226099954462872106169149247652374572253816","20491754476476154924134977170527318962516951048","48015624509000271533893818471120349856582210629","39124424833845839884810813169030467125026545695","06179865905679773500000446518009139186221751475","50299762028484386451798250206098404849305241667","17612303343616139783490972262772438676524824068"};
vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof(*sequence_));
int k = 1000000;
double _ = -1.0;
END
CASE(5)
string sequence_[] = {"71976811258237929702845263495922601783919868641","02251802204323958045597357456923113495221557803","90095020220279834521539403624903937967725913407","50053460399206979462458264772306292666423647685","02572846359464506709668041986008820985078749456","63651195290257557859053784453335417054877378801","88071504446176013413511927775188191764379674623","29974854837574431313734534729345259190024602997","55014957157257843589686675744902604078720333508","01131988958096366504666993633754134352692269267","51752858242869007758022337290690356607077821800","21095486538572029728876557551700273163478568908","26768584712609422632927787476248052685871245841","30476162031128267909969986318200112332997060127","67147231545693336082449853378272619777539526890","77325751151483739979126189680785999306688546541","60696196844453533885255920392566069304416588788","40448439503868890128193004467326572316344483756","38794956784623535641434020544271114018904283039","04259378746619199033735315818389500832702792548","14749921924200367925539596250117026415125437361","27571950348568199963970732499050942346365404137","20426040040465751262062508541139520659336559386","55174667536504554080965535926587381147358222766","91929788953883088854601418426423178327841570217","59380787526604353267171849869050674394208302221","26674907125183934287726716511384835000891155717","62239098887645197764145691025786798119751608655","92218110071216479433249224067456563435001106633","54941333895778833504791076934725843041038752979","44933730489344462698957437896769769665685685859","71451690730171207333637871178287883931766109666","01233816901291564380352253472638207947970645289","12022772227294854058522895631361139206099215743","14277758640213194050151726109721453213417484968","66733582405484779688190261796445525047628795445","28448651340492606982737723760081282553763549534","21540709018694807057292761057907753900925612265","07308657638866103434359099058610811770204658380","32455397123941974928264127618703584263392274381","55395352504201503474443238244337603595878619533","00381935524390094046906802274067171473367145593","86620399556019143023852411146726967997538868505","30161314840498627367845419554474800263207588594","67504258995889458279205655740089172159291177169","38484488894772590350380196849005813762369148153","90833154310182723669587328317813416374891018446"};
vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof(*sequence_));
int k = 1000000;
double _ = -1.0;
END
CASE(0)
string sequence_[] = {"1", "2"};
vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof(*sequence_));
int k = 1;
double _ = 2.0;
END
CASE(0)
string sequence_[] = {"1", "2"};
vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof(*sequence_));
int k = 2;
double _ = 2.0;
END
}
// END CUT HERE