問題
http://topcoder.bgcoder.com/print.php?id=1540
ある文字列の長さarrayLengthが与えられ、その文字列の任意の２つを選んでswapすることをswapCount数繰り返す。
swapが全て終わったとき、a番目の文字とb番目の文字が一致している確率を求める。
解き方
a==bのとき、次にa==bとなる確率は
n-1C2 / nC2 = (n-2)/n
a!=bのとき、次にa==bとなる確率は
1/nC2 = 2/n(n-1)
これをswap回数分繰り返したものが答えになる。
コード
sing namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class RandomSwaps {
public:
double getProbability(int arrayLength, int swapCount, int a, int b) {
double p= (a==b) ? 1.0 : 0.0;
double N=arrayLength;
FORE(i,0,swapCount){
p= p*(N-2)/N + (1-p)*2.0/(N*(N-1));
}
return p;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class RandomSwaps {
public:
double getProbability(int arrayLength, int swapCount, int a, int b) {
double p= (a==b) ? 1.0 : 0.0;
double N=arrayLength;
FORE(i,0,swapCount){
p= p*(N-2)/N + (1-p)*2.0/(N*(N-1));
}
return p;
}
};