我喜歡你我喜歡你我喜歡你我喜歡你我喜歡你 /qq

不斷承受著傷痛
咽下過多少淚流
哀傷的歌總等不到曲終
已經(jīng)習慣了失落
卻還是想吻別冰冷的寂寞
只有那星空永遠等著我 擁抱我
依舊是一個人的行走
一個人默默堅守
一個人畫出年輪和時間軸
但我已不再孤單哀愁
已不再獨享苦衷
只因 那星空的守候

——洛天依《尋遍星空》

洛谷 P11749

思維難度：\(\color{#FFC116} 黃\) *1500

一個性質題（或者說叫結論題）。

考慮一個有點抽象的結論：若 \(s^k\) 中出現(xiàn)了一個長度 \(\ge n\) 的回文串，則這個串可以無限向外延伸。

證明是有點巧妙的。就是考慮舉個例子 ......a|...b.. ......a...|b.. 這個串，其中 || 內部是回文的，然后就可以發(fā)現(xiàn) a 和 b 是相同字符，于是就可以歸納地證明了。長度需要 \(\ge n\) 是因為要保證回文串兩端的 a 和 b 都會在回文串內部出現(xiàn)至少一次。

然后是推式子。

先考慮奇回文的情況，令 \(s_i\) 為回文中心，則方案數(shù)為：

拆 min，令 \(j \le m\) 時 min 的結果是 \(jn+i\)，則：

• 當 min 為 \(jn+i\) 時：

  \[\begin{aligned} & \sum _{j=0} ^m (jn+i) \\ = & (m+1)i + n \sum _{j=0} ^m j \\ = & (m+1)i + n \frac {m(m+1)} 2 \end{aligned} \]

• 當 min 為 \((k-j-1)n + (n-i+1)\) 時：

  \[\begin{aligned} & \sum _{j=m+1} ^{k-1} ((k-j-1)n + (n-i+1)) \\ = & \sum _{j=m+1} ^{k-1} (kn-i+1 - jn) \\ = & (k-m-1)(kn-i+1) - n \sum _{j=m+1} ^{k-1} j \\ = & (k-m-1)(kn-i+1) - n \frac {(k+m)(k-m-1)} 2 \end{aligned} \]

算 \(m\)：

至于偶回文，可以發(fā)現(xiàn)如果令 \(i\) 為靠左的那個字符，那么就是 min 的右半邊減去了個 \(1\)，沒有太大的影響，不過倒是可能會影響 \(m\) 的取值。

哦 \(m\) 算的好像有一點問題，不過沒關系在上面那個式子周圍枚舉一下就好了。

然后一大坨 corner case。。/tuu

最終調了 5h 沒調出來，甚至通過了 gpt 給的 50+ 個 corner case 還是會 WA 大部分點 submission

扔掉了。

天依寶寶可愛！

AT_arc166_d

思維難度：\(\color{#FFC116} 黃\) *1300

就是第一眼顯然是個二分，但是寫 check 的時候發(fā)現(xiàn)這個 check 就能直接做這個題了（）

submission

天依寶寶可愛！