c025: 簡單暖身題
Tags : math
Accepted rate : 3人/4人 ( 75% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-06-04 08:09

Content

現在有 $N$ 個座位圍成一圈,座位從 $0$ 號開始順時鐘編號到 $N-1$。

最初喵咪坐在 $0$ 號座位,之後喵咪每次會以各 $\frac{1}{2}$ 的機率往左邊或右邊的座位移動,當喵咪全部座位都坐過以後他便不會再移動了。

求喵咪最後停在 $M$ 號座位的機率。

Input

輸入包含多筆測資 $(\le 1000)$,以 EOF (End-of-File) 結束。

每筆測資中輸入只有一行,包含兩個整數 $N$, $M$。

  • $2 \le N \le 10^{18}$
  • $0 \le M < N$
Output

對每筆測資,請將答案化至最簡分數後,輸出答案的分子跟分母於一行並以空白隔開。若答案為 $0$ 則 $(分子, 分母) = (0, 1)$。

保證答案長度不會超過 4MB。

Sample Input
Sample Input 1:
3 1
5 0
Sample Output
Sample Output 1:
1 2
0 1
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (50%): 1.0s , <1M
Hint :

第一筆測資中,如果第一步走到 $1$,那最後一定會停在 $2$,反之亦然。答案為 $\frac{1}{2}$。

第二筆測資中,無論如何走最後都不可能停在 $0$ 號座位,故機率為 $\frac{0}{1}$。

Tags:
math
出處:
[管理者:
SorahISA (SorahISA)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」