LeetCode 2550. Count Collisions of Monkeys on a Polygon

January 29, 2023

周賽330。雖然我有做出來，但這題放在Q2是真的過分，而且描述/答案似乎也有點問題，不知道會不會rejudge。

題目

有一個擁有n個頂點的多邊形，頂點由順時鐘方向分別記為為0~n-1，且每個頂點上都有正好一隻猴子。

下為6頂點的示意圖：

每個猴子會同時向相鄰的頂點移動，對於頂點i來說，其相鄰頂點可以是：

(i + 1) % n，也就是順時鐘方向
或是(i - 1 + n) % n，也就是逆時鐘方向

移動之後，如果有至少兩隻猴子停在同一個頂點上，則代表發生衝突。

求有多少移動方式擁有至少一次衝突。答案很大，模10^9+7後回傳。

注意：每個猴子只能移動一次。

解法

看了好幾次大神講題解，最受用的一句話叫做：正難則反。

猴子有10^9隻，要窮舉出全部的移動方式總共是2^(10^9)，根本不可能。但是不會衝突的方式只有兩種：全順時鐘或是全逆時鐘。
所有移動方式 = 有衝突 + 沒衝突，那麼只要求出總數扣掉2後再求一次餘數就是答案。

第二個考點在於如何計算2^(10^9)？使用快速冪將次方運算降低到log n。

時間複雜度O(log n)。空間複雜度O(1)。

class Solution:
    def monkeyMove(self, n: int) -> int:
        MOD=10**9+7
        tot=pow(2,n,MOD)
        return (tot-2)%MOD

自己手寫快速冪。

class Solution:
    def monkeyMove(self, n: int) -> int:
        MOD=10**9+7
        
        tot=1
        base=2
        exp=n
        while exp>0:
            if exp&1:
                tot=(tot*base)%MOD
            exp//=2
            base=(base*base)%MOD

        return (tot-2)%MOD

最後討論一下題目描述的問題：

移動之後，如果有至少兩隻猴子停在同一個頂點上，則代表發生衝突

試想有四隻猴子[1,2,3,4]，其中1和2對換，3和4對換，同樣不會發生衝突。所以會多出兩種不衝突的方式，共四種。
只有三隻猴子，[1,2,3]，則無法兩兩交換，所以一樣維持兩種不衝突的方式。
如果真正按照描述的方式來解釋的話，偶數答案應該是tot-4，而奇數答案是tot-2才對。

mocowcow

題目

解法