主題
題目連結：
題目意譯：
你被給定兩正整數 startPos 和 endPos。一開始，你站在無限延伸的數線上的位置 startPos。在一步之中，你可以往左或往右一單位距離。
給定一正整數 k，回傳從 startPos 以恰好 k 步抵達 endPos 的相異方法數。由於答案可能很大，將其模 10 ^ 9 + 7 後再回傳。
兩種方法如果移動順序不完全一致，則兩者視為相異。
注意到數線包含著負整數。
限制：
1 ≦ startPos, endPos, k ≦ 1000
範例測資：
範例 1：
輸入： startPos = 1, endPos = 2, k = 3
輸出： 3
解釋： 我們可恰好 3 步從位置 1 抵達 2，方法為有三種：
- 1 → 2 → 3 → 2。
- 1 → 2 → 1 → 2。
- 1 → 0 → 1 → 2。
可以證明沒有其他可能的方法存在，所以我們回傳 3。
範例 2：
輸入： startPos = 2, endPos = 5, k = 10
輸出： 0
解釋： 不可能在恰好 10 從位置 2 抵達 5。
解題思維：
令 d = abs(endPos - startPos)，即兩個位置之間的距離值。
如果 k < d 或是 d 與 k 的奇偶性不同（即一奇一偶），則不可能從 startPos 用剛好 k 步走到 endPos。原因很明顯：
k < d 則當然不可能到，因為一步只能動一單位、
k = d 也很顯然，因為剛剛好可以抵達、
而 k > d，則可以先走 d 步到 endPos，然後在 endPos 和 endPos + 1 這兩個位置之間交替來把剩下的步數用掉。因此如果 k 和 d 的奇偶性不同，則最後你會停在 endPos + 1 這個位置上，無法停在 endPos。
假設現在 startPos < endPos（如果 startPos > endPos，則將之後的敘述中的「左」換成「右」、「右」換成「左」），則我們過程中「往右」d + (k - d) ÷ 2 單位（或等價於 (k + d) ÷ 2 單位）、「往左」(k - d) ÷ 2 單位。然後我們把這些「往左」、「往右」各自視為實際存在的物件（左、右箭頭等）。
因此走恰好 k 步到 endPos 的方法數等價於這些左右箭頭的排列組合，其值為
k! ÷ (((k + d) ÷ 2)! × ((k - d) ÷ 2)!)
其中「!」代表階乘運算（Factorial）。不過當然由於過程中需要對 10 ^ 9 + 7 取模，因此需要牽涉到求階乘的模反元素之運算（可以參見這題）。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
