Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-05-01SRM336,SRM337,SRM338 (Practice)

SRM 338 RandomSwaps

|  SRM 338 RandomSwaps - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 338 RandomSwaps - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7289

  • 確率
public class RandomSwaps {

	public double getProbability(int al, int swapCount, int a, int b) {
		long total = (al * (al-1) / 2);
		double base = 1.0d / total;
		
		double nottouch = 1.0d * ((al - 1) * (al - 2) / 2) / total;
		
		double ok = (a == b) ? 1.0d : 0.0d;
		double ng = 1.0d - ok;
		for (int i = 0 ; i < swapCount ; i++) {
			double nok = ng * base + ok * nottouch;
			double nng = 1.0d - nok;
			ok = nok;
			ng = nng;
		}
		return ok;
	}
}