確率が整数でいいのなら
>>57の方法が一番現実的だと思う
一度表さえ作ってしまえばO(1)で実行出来る