SRM 338 Div1 Medium RandomSwaps

問題

長さarrayLengthの配列がある。ここから無作為に2つの要素を取り出し、交換する動作をswapCount回行う。この後に当初a番目にあった要素がb番目に移動している確率を求めよ。

やりかた

典型的なDP。
dp[0][i]:=（i回スワップした後にbに移動している確率）
dp[1][i]:=（i回スワップした後にb以外に移動している確率）
でDP。

イカソース。

class RandomSwaps {
public:
  double getProbability(int arrayLength, int swapCount, int a, int b){
    memset(dp, 0, sizeof(dp));
    int N = arrayLength;
    if(a == b) dp[0][0] = 1;
    else dp[1][0] = 1;
    for(int i = 0; i < swapCount; i++){
      dp[0][i + 1] = dp[0][i] * (N - 2) / N + dp[1][i] * 2 / N / (N - 1);
      dp[1][i + 1] = dp[0][i] * 2.0 / N     + dp[1][i] * (1.0 - 2.0 / N / (N - 1));
    }
    return dp[0][swapCount];
  }
};

dp[0][i] + dp[1][i] = 1.0なので、どちらかは省略はできます。