普及23题解_牛客博客

读入的时候遍历检查一遍，看有多少个字符 $s$ .

暴力模拟即可。即 $i$ 从第 $n$ 项到第 $0$ 项，每次 $ans = ans * x + a_i$ 。就可求出 $f(x)$ 。复杂度 $O(nm)$ 。

考虑倒推。如果当前最后一步向右走那么就相当于把这个字符插入到最前面，如果是向左走就相当于插入到最后面。直接用一个 $deque$ 维护一下即可。

考虑按照 $b_i$ 从小往大排序，考虑 $dp_i$ 表示前 $i$ 个数，第 $i$ 个数必须选最多能选多少个。转移为：

$dp[i] = \max \limits_{j < i, gcd(b[i], b[j]) > 1} dp[j] + 1$

考虑如何优化转移，我们维护 $mx[z]$ 表示：

$mx[z] = \max \limits_{z | b[j], j < i} dp[j] + 1$

那么，

$dp[i] = \max \limits_{d | b[i], d > 1} mx[d]$

考虑 $mx$ 和 $dp$ 都可以在 $O(\sigma(n))$ 的时间内求得。

考虑 $\sigma(1) + \sigma(2) + ... + \sigma(n) = n / 1 + n / 2 + ... n / n = O(nlogn)$ 。

所以时间复杂度是 $O(nlogn)$ 的。