题目内容

有一个神话传说，说在很久以前，红色的守护者曾经来到人间，为了保护人们免受邪恶的侵害，他留下了一个强大的魔法。这个魔法被传说中的红宝石所承载，只有能够创造出特定数量回文子串的字符串才能够揭示出它的秘密。

题目思路

简单构造题。

1.考虑放连续的一段相同字母，回文子串个数是$C(n+1,2)$ 。

2.我们只需要按照r,d,e,r,d,e,...这样的顺序来放置连续的段，那么每个段之间就是独立的，即不会产生跨段的回文子串.

3.由于字符串长度有限制，$x$ 又比较大，所以我们可以采取贪心的策略，每次放尽量长的相同段(这个过程可以二分),使得最终构造出来的段尽量小。