【題目敘述】https://leetcode.com/contest/biweekly-contest-20/problems/count-all-valid-pickup-and-delivery-options/
【解題想法】模逆元
- 可能的排列組合為 (2n)! / (2^n)
- 2 的模逆元為 5e8 + 4。
- ( 5e8 + 4 ) * 2 = (1e9 + 7 + 1)
class Solution {
public:
int countOrders(int n) {
int mod = 1e9+7;
// (2n)! / (2^n)
// inv[2] = 5e8 + 4
long long ret = 1;
for (int i = 1; i<=n; i++){
ret *= (2*i)*(2*i-1);
ret %= mod;
ret *= 500000004;
ret %= mod;
}
return ret;
}
};