fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <string>
  5. #include <algorithm>
  6. #include <map>
  7. using namespace std;
  8.  
  9. typedef double LF;
  10. int N, K, cnt, inv[10000];
  11. string S[10000], init;
  12. map <string,int> M;
  13. LF prob, dp[1000][4];
  14.  
  15. int comp(string x) {
  16.   int ret = 0;
  17.   for (int i=0;i<N;++i)
  18.     for (int j=i+1;j<N;++j)
  19.       if (x[i] > x[j]) ret++;
  20.   return ret;
  21. }
  22.  
  23. LF cal(int x,int k) {
  24.   if (dp[x][k] != 0.0) return dp[x][k];
  25.   if (k == 0) dp[x][k] = inv[x];
  26.   else {
  27.     for (int i=0;i<N;++i)
  28.       for (int j=i;j<N;++j) {
  29.         string s = S[x];
  30.         reverse(s.begin()+i,s.begin()+j+1);
  31.         dp[x][k] += prob * cal(M[s],k-1);
  32.       }
  33.   }
  34. //  printf("dp(%s, %d) = %.9lf\n",S[x].c_str(),k,dp[x][k]);
  35.   return dp[x][k];
  36. }
  37.  
  38. int main () {
  39.   scanf("%d%d",&N,&K);
  40.   for (int i=0;i<N;++i) {
  41.     int t;
  42.     scanf("%d",&t);
  43.     init += ('0' + t);
  44.   }
  45.   prob = 2.0 / (LF)(N * (N+1));
  46.   string tmp = "";
  47.   for (int i=1;i<=N;++i) tmp += ('0' + i);
  48.   do {
  49.     M[tmp] = ++cnt;
  50.     S[cnt] = tmp;
  51.   } while (next_permutation(tmp.begin(),tmp.end()));
  52.   for (int i=1;i<=cnt;++i) inv[i] = comp(S[i]);
  53.   //for (int i=1;i<=cnt;++i) cout << S[i] << ": " << inv[i] << endl;
  54.   //cout << init << endl;
  55.   printf("%.12lf\n",cal(M[init],K));
  56. }
Success #stdin #stdout 0s 3348KB
comments (?)
stdin
copy 
3 4
1 3 2
stdout
copy 
2.458333333333
https://ideone.com/x0oF5P
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!