1樓：Mivik
題主提到的洛谷出題人過來答一波（）
當時出題時和某位答主的想法大致一樣，也就是列舉週期集合並計算其貢獻。但是當時出題人太菜只會 暴力列舉週期集合因此設的 ，對於這個問題和暴力並沒有本質區別。我們現在的問題是如何快速地列舉出所有的週期集合。
實際上，根據 Periodicity Lemma 我們可以考慮列舉乙個最小的週期 ，無論 是否為小週期每次我們都能將列舉的長度折半。實踐證明這樣的列舉方式的時間複雜度是和總本質不同的週期集合數目成正比的。
列舉完週期集合後，我們可以在數目的平方的時間複雜度內計算出每一種週期集合的方案數，然後推乙個生成函式得到對於多個 來說長度為 的包含該子串的字串的數目。目前可以做到 。
實際上如果觀察推導過程會發現當 大小固定時答案是乙個關於 （字符集大小）的 次多項式，這裡 給出了 時多項式的係數，係數由低到高。
此外，有位答主提到 OEIS 上沒有，我就投 OEIS 上了：OEIS
詳細解釋我放部落格鏈結了。
字串的期望本質不同子串個數
2樓：金髮妹子
考慮這樣乙個子問題：給出 ， 和字符集大小 。求出有多少對字串 滿足：
是 的子串
顯然，如果這個子問題能做。只需要列舉 ，分別計算一下即可。
這個也是乙個經典問題，具體是什麼是無關緊要的，只和 有關。只需要列舉出 ，就可以計算 的方案數，同時可以 dp 出 的方案數。前者是個簡單的容斥，後者就是個普通的 dp。
可以發現，當 的時候，本質不同的 大概是三千左右。
因此這個題在 的時候還是可以做的。
PS：這個子問題是這個題 Substring Pairs。
C語言，用陣列定義乙個字串，那這個字串是怎麼儲存在這個陣列中的呢？
the gc 對於scanf的 s的解釋如下 Matches a sequence of non white space characters the nextpointer must be a pointer to the initial element of acharacter array t...
如何通過只翻轉乙個字串的子串對該字串進行排序？
老版題是NP很多人已經給出參考文獻了。新版題是裸dp 設len是字串strls的長度，那麼定義dp len 1 2 表示直到長度x 0 x len 最後一位strls x 1 不翻轉 翻轉 0 1 所需的最小翻轉次數。 yaoyao 反轉兩個字元的子串不就是交換兩個字元的位置嗎？這是氣泡排序呀 喵的...
python如何統計乙個字串中各字元的數量？
Shreck Ye 其實因為字符集是已知而且連續的，直接按字元編碼對映到乙個記憶體陣列裡面效率要比字典更高。不過既然是Python，變數都是用字典存的，效率似乎就無所謂了，更重要的是怎麼寫更簡單更快。這裡用字典也更方便簡單，參照高讚答案用collections.Counter一行就可以解決更好。 2...