7bc22ef7ab 2013-04-12 kinaba: #include <iostream> 7bc22ef7ab 2013-04-12 kinaba: #include <sstream> 7bc22ef7ab 2013-04-12 kinaba: #include <iomanip> 7bc22ef7ab 2013-04-12 kinaba: #include <vector> 7bc22ef7ab 2013-04-12 kinaba: #include <string> 7bc22ef7ab 2013-04-12 kinaba: #include <map> 7bc22ef7ab 2013-04-12 kinaba: #include <set> 7bc22ef7ab 2013-04-12 kinaba: #include <algorithm> 7bc22ef7ab 2013-04-12 kinaba: #include <numeric> 7bc22ef7ab 2013-04-12 kinaba: #include <iterator> 7bc22ef7ab 2013-04-12 kinaba: #include <functional> 7bc22ef7ab 2013-04-12 kinaba: #include <complex> 7bc22ef7ab 2013-04-12 kinaba: #include <queue> 7bc22ef7ab 2013-04-12 kinaba: #include <stack> 7bc22ef7ab 2013-04-12 kinaba: #include <cmath> 7bc22ef7ab 2013-04-12 kinaba: #include <cassert> 7bc22ef7ab 2013-04-12 kinaba: using namespace std; 7bc22ef7ab 2013-04-12 kinaba: typedef long long LL; 7bc22ef7ab 2013-04-12 kinaba: typedef long double LD; 7bc22ef7ab 2013-04-12 kinaba: typedef complex<LD> CMP; 7bc22ef7ab 2013-04-12 kinaba: 7bc22ef7ab 2013-04-12 kinaba: template<typename T> 7bc22ef7ab 2013-04-12 kinaba: vector<T> MATMUL(const vector< vector<T> >& a, const vector<T>& v) 7bc22ef7ab 2013-04-12 kinaba: { 7bc22ef7ab 2013-04-12 kinaba: int N = a.size(); 7bc22ef7ab 2013-04-12 kinaba: vector<T> u(N); 7bc22ef7ab 2013-04-12 kinaba: for(int i=0; i<N; ++i) 7bc22ef7ab 2013-04-12 kinaba: for(int j=0; j<N; ++j) 7bc22ef7ab 2013-04-12 kinaba: u[i] += a[i][j]*v[j]; 7bc22ef7ab 2013-04-12 kinaba: return u; 7bc22ef7ab 2013-04-12 kinaba: } 7bc22ef7ab 2013-04-12 kinaba: 7bc22ef7ab 2013-04-12 kinaba: template<typename T> 7bc22ef7ab 2013-04-12 kinaba: vector< vector<T> > MATMUL(const vector< vector<T> >& a, const vector< vector<T> >& b) 7bc22ef7ab 2013-04-12 kinaba: { 7bc22ef7ab 2013-04-12 kinaba: int N = a.size(); 7bc22ef7ab 2013-04-12 kinaba: vector< vector<T> > c(N, vector<T>(N)); 7bc22ef7ab 2013-04-12 kinaba: for(int i=0; i<N; ++i) 7bc22ef7ab 2013-04-12 kinaba: for(int j=0; j<N; ++j) 7bc22ef7ab 2013-04-12 kinaba: for(int k=0; k<N; ++k) 7bc22ef7ab 2013-04-12 kinaba: c[i][j] += a[i][k]*b[k][j]; 7bc22ef7ab 2013-04-12 kinaba: return c; 7bc22ef7ab 2013-04-12 kinaba: } 7bc22ef7ab 2013-04-12 kinaba: 7bc22ef7ab 2013-04-12 kinaba: template<typename T> 7bc22ef7ab 2013-04-12 kinaba: vector<T> MATPOWMUL(vector< vector<T> > a, LL e, vector<T> v) 7bc22ef7ab 2013-04-12 kinaba: { 7bc22ef7ab 2013-04-12 kinaba: for(; e; e>>=1, a=MATMUL(a,a)) 7bc22ef7ab 2013-04-12 kinaba: if(e&1) 7bc22ef7ab 2013-04-12 kinaba: v = MATMUL(a, v); 7bc22ef7ab 2013-04-12 kinaba: return v; 7bc22ef7ab 2013-04-12 kinaba: } 7bc22ef7ab 2013-04-12 kinaba: 7bc22ef7ab 2013-04-12 kinaba: class TheSwapsDivOne { public: 7bc22ef7ab 2013-04-12 kinaba: double find(vector <string> sequence, int k) 7bc22ef7ab 2013-04-12 kinaba: { 7bc22ef7ab 2013-04-12 kinaba: const string S = accumulate(sequence.begin(), sequence.end(), string()); 7bc22ef7ab 2013-04-12 kinaba: const int N = S.size(); 7bc22ef7ab 2013-04-12 kinaba: 7bc22ef7ab 2013-04-12 kinaba: // pos[p] = prob that position p is chosen. 7bc22ef7ab 2013-04-12 kinaba: vector<double> pos(N); 7bc22ef7ab 2013-04-12 kinaba: const double tot_range = (1+N)*N/2; 7bc22ef7ab 2013-04-12 kinaba: for(int p=0; p<N; ++p) 7bc22ef7ab 2013-04-12 kinaba: pos[p] = (p+1)*(N-p) / tot_range; 7bc22ef7ab 2013-04-12 kinaba: double totpos = accumulate(pos.begin(), pos.end(), 0.0); 7bc22ef7ab 2013-04-12 kinaba: 7bc22ef7ab 2013-04-12 kinaba: double e = 0.0; 7bc22ef7ab 2013-04-12 kinaba: 7bc22ef7ab 2013-04-12 kinaba: double pStay = calc_stay(N, k); 7bc22ef7ab 2013-04-12 kinaba: cerr<<pStay<<endl; 7bc22ef7ab 2013-04-12 kinaba: for(int p=0; p<N; ++p) 7bc22ef7ab 2013-04-12 kinaba: e += (S[p]-'0') * (pStay*pos[p] + (1-pStay)*(totpos-pos[p])/(N-1)); 7bc22ef7ab 2013-04-12 kinaba: return e; 7bc22ef7ab 2013-04-12 kinaba: } 7bc22ef7ab 2013-04-12 kinaba: 7bc22ef7ab 2013-04-12 kinaba: double calc_stay(int N, int k) 7bc22ef7ab 2013-04-12 kinaba: { 7bc22ef7ab 2013-04-12 kinaba: vector<double> v(2); 7bc22ef7ab 2013-04-12 kinaba: v[0]=1, v[1]=0; 7bc22ef7ab 2013-04-12 kinaba: 7bc22ef7ab 2013-04-12 kinaba: vector<vector<double> > m(2, vector<double>(2)); 7bc22ef7ab 2013-04-12 kinaba: double tot = N*(N-1)/2; 7bc22ef7ab 2013-04-12 kinaba: m[0][0] = 1 - (N-1)/tot; 7bc22ef7ab 2013-04-12 kinaba: m[0][1] = 1 - m[0][0]; 7bc22ef7ab 2013-04-12 kinaba: m[1][0] = 1 / tot; 7bc22ef7ab 2013-04-12 kinaba: m[1][1] = 1 - m[1][0]; 7bc22ef7ab 2013-04-12 kinaba: 7bc22ef7ab 2013-04-12 kinaba: v = MATPOWMUL(m, k, v); 7bc22ef7ab 2013-04-12 kinaba: return v[0]; 7bc22ef7ab 2013-04-12 kinaba: } 7bc22ef7ab 2013-04-12 kinaba: }; 7bc22ef7ab 2013-04-12 kinaba: 7bc22ef7ab 2013-04-12 kinaba: // BEGIN CUT HERE 7bc22ef7ab 2013-04-12 kinaba: #include <ctime> 7bc22ef7ab 2013-04-12 kinaba: double start_time; string timer() 7bc22ef7ab 2013-04-12 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 7bc22ef7ab 2013-04-12 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 7bc22ef7ab 2013-04-12 kinaba: { os << "{ "; 7bc22ef7ab 2013-04-12 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 7bc22ef7ab 2013-04-12 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 7bc22ef7ab 2013-04-12 kinaba: void verify_case(const double& Expected, const double& Received) { 7bc22ef7ab 2013-04-12 kinaba: bool ok = (abs(Expected - Received) < 1e-9); 7bc22ef7ab 2013-04-12 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 7bc22ef7ab 2013-04-12 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 7bc22ef7ab 2013-04-12 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 7bc22ef7ab 2013-04-12 kinaba: #define END verify_case(_, TheSwapsDivOne().find(sequence, k));} 7bc22ef7ab 2013-04-12 kinaba: int main(){ 7bc22ef7ab 2013-04-12 kinaba: 7bc22ef7ab 2013-04-12 kinaba: CASE(0) 7bc22ef7ab 2013-04-12 kinaba: string sequence_[] = {"4", "77"}; 7bc22ef7ab 2013-04-12 kinaba: vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof(*sequence_)); 7bc22ef7ab 2013-04-12 kinaba: int k = 1; 7bc22ef7ab 2013-04-12 kinaba: double _ = 10.0; 7bc22ef7ab 2013-04-12 kinaba: END 7bc22ef7ab 2013-04-12 kinaba: CASE(1) 7bc22ef7ab 2013-04-12 kinaba: string sequence_[] = {"4", "77"}; 7bc22ef7ab 2013-04-12 kinaba: vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof(*sequence_)); 7bc22ef7ab 2013-04-12 kinaba: int k = 47; 7bc22ef7ab 2013-04-12 kinaba: double _ = 10.0; 7bc22ef7ab 2013-04-12 kinaba: END 7bc22ef7ab 2013-04-12 kinaba: CASE(2) 7bc22ef7ab 2013-04-12 kinaba: string sequence_[] = {"1", "1", "1", "1", "1", "1", "1"}; 7bc22ef7ab 2013-04-12 kinaba: vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof(*sequence_)); 7bc22ef7ab 2013-04-12 kinaba: int k = 1000000; 7bc22ef7ab 2013-04-12 kinaba: double _ = 3.0; 7bc22ef7ab 2013-04-12 kinaba: END 7bc22ef7ab 2013-04-12 kinaba: CASE(3) 7bc22ef7ab 2013-04-12 kinaba: string sequence_[] = {"572685085149095989026478064633266980348504469", "19720257361", "9", "69"}; 7bc22ef7ab 2013-04-12 kinaba: vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof(*sequence_)); 7bc22ef7ab 2013-04-12 kinaba: int k = 7; 7bc22ef7ab 2013-04-12 kinaba: double _ = 98.3238536775161; 7bc22ef7ab 2013-04-12 kinaba: END 7bc22ef7ab 2013-04-12 kinaba: CASE(4) 7bc22ef7ab 2013-04-12 kinaba: 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"}; 7bc22ef7ab 2013-04-12 kinaba: vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof(*sequence_)); 7bc22ef7ab 2013-04-12 kinaba: int k = 1000000; 7bc22ef7ab 2013-04-12 kinaba: double _ = -1.0; 7bc22ef7ab 2013-04-12 kinaba: END 7bc22ef7ab 2013-04-12 kinaba: CASE(5) 7bc22ef7ab 2013-04-12 kinaba: 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"}; 7bc22ef7ab 2013-04-12 kinaba: vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof(*sequence_)); 7bc22ef7ab 2013-04-12 kinaba: int k = 1000000; 7bc22ef7ab 2013-04-12 kinaba: double _ = -1.0; 7bc22ef7ab 2013-04-12 kinaba: END 7bc22ef7ab 2013-04-12 kinaba: CASE(0) 7bc22ef7ab 2013-04-12 kinaba: string sequence_[] = {"1", "2"}; 7bc22ef7ab 2013-04-12 kinaba: vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof(*sequence_)); 7bc22ef7ab 2013-04-12 kinaba: int k = 1; 7bc22ef7ab 2013-04-12 kinaba: double _ = 2.0; 7bc22ef7ab 2013-04-12 kinaba: END 7bc22ef7ab 2013-04-12 kinaba: CASE(0) 7bc22ef7ab 2013-04-12 kinaba: string sequence_[] = {"1", "2"}; 7bc22ef7ab 2013-04-12 kinaba: vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof(*sequence_)); 7bc22ef7ab 2013-04-12 kinaba: int k = 2; 7bc22ef7ab 2013-04-12 kinaba: double _ = 2.0; 7bc22ef7ab 2013-04-12 kinaba: END 7bc22ef7ab 2013-04-12 kinaba: 7bc22ef7ab 2013-04-12 kinaba: } 7bc22ef7ab 2013-04-12 kinaba: // END CUT HERE