题面很短 Short
题面
对于串 $s$ , 每次操作得到 $s^\prime = s + \operatorname{rev}(s)$ , $\operatorname{rev}(s)$ 表示 $s$ 的反串 .
给定串 $t$ , 求最小的 $s$ .
解题思路
签到题 .
二分加上暴力判断 , 复杂度 $O(T n \log n)$ .
题面不长
题面
求有多少个非空的可重集满足 :
- 所有元素均为 $[1 , n]$ 中的正整数 .
- 元素的重数不超过 $k$ , 一个元素的重数指该元素在可重集中出现的次数 .
- 所有元素的平均数为 $x$ .
解题思路
把集合中每个数减去 $x$ , 则集合的和为 0 是原集合平均数为 $x$ 的充要条件 .
只需要求出 $f_{i , j}$ 表示用 $[1 , i]$ 中的数凑出 $j$ 的方案数 . $f_{i , j} = \sum\limits_{0 \le x \le k} f_{i - 1 , }$ , 维护每个模 $i$ 的同余类的前缀和 .
复杂度 $O(n^3 k)$ .