This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
長さ$arrayLength$の配列の要素を$swapCount$回swapする．初めに$a$番目にあったものが$b$番目にいる確立を求める．
$$
dp[i][j] := i回swapした時にb番目にいる確立
$$
一回のswapの選択肢は$\displaystyle \frac{n*(n-1)}{2}$通りある．swap後に$b$番目にいる場合は，元々$b$番目にいてswapに$b$番目が選ばれない場合と，他の場所にいてその場所と$b$番目をswapする場合である．swap後に$b$番目にいない場合は，元々$b$番目にいて他の場所にswapされる場合と，他の場所にいてその場所と$b$番目がswapされない場合である．
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
using namespace std ;
typedef long long ll ;
typedef pair < int , int > P ;
double dp [ 100005 ][ 2 ];
class RandomSwaps {
public :
double getProbability ( int arrayLength , int swapCount , int a , int b ) {
int n = arrayLength ;
int cnt = swapCount ;
memset ( dp , 0 , sizeof ( dp ));
dp [ 0 ][ a == b ] = 1 ;
double N = ( n * ( n - 1 )) / 2 ;
rep ( i , cnt ) {
dp [ i + 1 ][ 1 ] = dp [ i ][ 1 ] * ( 1 - ( n - 1 ) / N ) + dp [ i ][ 0 ] * ( 1.0 / N );
dp [ i + 1 ][ 0 ] = dp [ i ][ 1 ] * (( n - 1 ) / N ) + dp [ i ][ 0 ] * ( 1 - 1.0 / N );
}
return dp [ cnt ][ 1 ];
}
};