cojs 香蕉 解題報告

啦啦啦，今天的考試題

不過原來考試題的n<=10w

由于我有更好的做法，所以我就改成20億辣

本來先說一說考試題的正解做法的

但是復雜度是O(nlogm)，實在是太渣了

所以還是說一說我的做法吧

首先假定都會寫裸的DP

我們考慮A,B，如果B不能轉移到A，當且僅當A不等于B且A%B=0

很容易發現當A是素數時，A只不能從1那里轉移過來，也就是說素數的轉移都是一樣的

換句話說，在狀態里當長度一定時以每個素數結尾的方案一定是一樣的

這就給了我們一些啟發，很容易得到結論若兩個數的唯一分解式的指數排序后指數序列完全一樣

則這兩個數的轉移一定相同，具體證明可以使用數學歸納法

(我離考試結束快15分鐘的時候才證明了這個結論，結果沒時間寫了，真是悲桑）

我們定義轉移相同的數為一個等價類，可以知道m=100000時有160個等價類

這樣我們就可以構造一個160*160的矩陣，把轉移暴力搞出來之后矩陣乘法加速DP

時間復雜度O(160^3logn)，這樣寫的話在cojs上交會小小的T幾個點

雖然時間復雜度分析下來是可以跑的過的

但是我們要進行跟時間復雜度同階的模操作，這樣會大大減慢程序運算速度

之后我們進行一些分析，998244353這個模數<=2^30，相乘<=2^60

如果我們開unsigned long long，那么我們理論上可以進行16次加法之后再做模運算

實際程序實現我采用了每加10次取一次模的方法，這樣取模的次數大大縮小了

就可以在cojs上通過了

(雖然卡常數很不厚道，但是鑒于這道題的思路是我從頭到尾YY出來的，包括對于常數的優化

所以就這樣出在cojs上吧）