SRM575 Div1 Medium

500
http://community.topcoder.com/stat?c=problem_statement&pm=12498&rd=15495

ある位置が部分列に選ばれる確率を計算する。
ある位置の数字が"最終的に"その場所にある確率を計算する。

こういう列の要素のスワップの問題って、"その位置"と"他の位置"に分けて考えるのが定番なの？

class TheSwapsDivOne {
public:
  double find(vector <string> v, int k)
  {
    string seq = accumulate(v.begin(), v.end(), string(""));
    const int N = seq.size();

    double w[N];
    fill(w, w + N, 0);
    double cnt[N];
    fill(cnt, cnt + N, 0);

    double patt = 0;
    for (int i = 0; i < N; ++i) {
      for (int j = i + 1; j <= N; ++j) {
        for (int k = i; k < j; ++k) {
          ++cnt[k];
        }
        ++patt;
      }
    }

    for (int i = 0; i < N; ++i) {
      w[i] = cnt[i] / patt;
    }

    const int K = 1000000 + 2;
    static double dp[K][2];
    const int SAME = 0;
    const int OTHER = 1;

    fill(&dp[0][0], &dp[2 - 1][K - 1] + 1, 0);
    dp[0][SAME] = 1;

    for (int i = 0; i < k; ++i) {
      double whole = N * (N - 1);

      double a = ((N - 1) * (N - 2)) / whole;
      dp[i + 1][SAME] += dp[i][SAME] * a;

      double b = 2.0 / whole;
      dp[i + 1][SAME] += dp[i][OTHER] * b;

      double c = (2.0 * (N - 1)) / whole;
      dp[i + 1][OTHER] += dp[i][SAME] * c;

      double d = 0;
      d += (N - 1.0) * (N - 2.0) / whole;
      d += (2.0 * (N - 2.0)) / whole;
      dp[i + 1][OTHER] += dp[i][OTHER] * d;
    }

    const double W = accumulate(w, w + N, 0.0);
    double exp = 0;
    for (int i = 0; i < N; ++i) {
      double p = seq[i] - '0';
      exp += dp[k][SAME] * w[i] * p;
      exp += dp[k][OTHER] * (W - w[i]) / (N - 1.0) * p;
    }

    return exp;
  }