提供一个第三题的新颖做法。

考虑一个 dp，大眼观察可以发现选的和不选的都是对应的，每一种子序列（除了原串）都会被加两次，那么我们算一遍再 即可。

定义 为前缀的答案。

这个点录入：考虑我们只计算一个串是怎么做的，是乘 再加上 ，那么答案就是 加上 。

这个点不录入：。

所以转移就是 f[i]=f[i-1]*11+qmi(2,i-1)*a[i]。

代码量比官方题解少了很多。

record