推 DJYOMIYAHINA: 大師== 10/27 12:15
推 dont: 大師 10/27 12:35
推 sixB: 你真的好厲害 10/27 12:50
推 JerryChungYC: 大師 10/27 12:58
推 sixB: id正確 矩陣大師 10/27 13:00
推 sustainer123: 大神 10/27 13:12
推 oin1104: 大師 10/27 13:30
https://i.imgur.com/Q6LZOOi.png
Q1:
n<=100, 暴力硬做
Q2/Q4:
矩陣乘法練習
令 x 為 a-z 的個數(size: [26,1]) 可以先求出轉移矩陣 A (size: [26,26])
經過一次 transformation 後變為 Ax 為新的 a-z 的個數
則只要用快速冪求出 A^t x 就可以了
Q2可以用 DP 做 O(|s| + t) 的也會過
Q3:
nums[i] <= 200, 所以可以令 DP[x][y] 為 gcd 分別為 x, y 的數量
最後求 DP[1][1] + DP[2][2] + ... + DP[200][200]
吃了一次 TLE 因為覺得 gcd 至少 O(log n) 結果還蠻慢的
改成 preprocess 完所有 gcd(x, y) 就過了
Q3 一開始一直在想要怎麼利用 gcd 想不出來就先去做 Q4
回頭才發現單純用 DP 就行了
唯一用到 gcd 的性質是 gcd(x,y) <= min(x,y) for x,y != 0
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.230.16.58 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1730002495.A.3F7.html