【題解】LeetCode 1359. Count All Valid Pickup and Delivery Options

【題目敘述】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;
    }
};
分享本文 Share with friends