#98: 沒辦法矩陣快速冪qwq


211096@stu.cchs.chc.edu.tw (唐狗針)

學校 : 彰化縣精誠中學
編號 : 872
來源 : [61.223.79.98]
最後登入時間 :
2024-12-01 20:39:24
a284. 康比娜與追求者 -- 排列組合 | From: [61.223.100.167] | 發表日期 : 2024-08-11 17:41

矩陣快速冪會被卡複雜度(n>1e3就會TLE了) ,目沒保證N的範圍,還是乖乖dp吧

每次轉移都從除了自己所在荷葉的所有荷葉的上一秒轉移,最後輸出dp[0][0]就是答案了,也可以加個滾動優化,沒加也會過。還有建議可以對一秒的每個荷葉方法數都記錄起來,轉移時減掉目前荷葉上一秒的方法數就好,時間可以從O(n^2T)變O(NT),我不知道不加這個優化會不會被卡,可能會(?

 
ZeroJudge Forum