LeetCode 2550. Count Collisions of Monkeys on a Polygon
周賽330。雖然我有做出來,但這題放在Q2是真的過分,而且描述/答案似乎也有點問題,不知道會不會rejudge。
題目Permalink
有一個擁有n個頂點的多邊形,頂點由順時鐘方向分別記為為0~n-1,且每個頂點上都有正好一隻猴子。
下為6頂點的示意圖:
每個猴子會同時向相鄰的頂點移動,對於頂點i來說,其相鄰頂點可以是:
- (i + 1) % n,也就是順時鐘方向
- 或是(i - 1 + n) % n,也就是逆時鐘方向
移動之後,如果有至少兩隻猴子停在同一個頂點上,則代表發生衝突。
求有多少移動方式擁有至少一次衝突。答案很大,模10^9+7後回傳。
注意:每個猴子只能移動一次。
解法Permalink
看了好幾次大神講題解,最受用的一句話叫做:正難則反。
猴子有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才對。