题解 | #加法方案#
加法方案
https://ac.nowcoder.com/acm/contest/65195/C
提供一个第三题的新颖做法。
考虑一个 dp，大眼观察可以发现选的和不选的都是对应的，每一种子序列（除了原串）都会被加两次，那么我们算一遍再 即可。
定义 为前缀的答案。
这个点录入：考虑我们只计算一个串是怎么做的，是乘 再加上
，那么答案就是
加上
。
这个点不录入：。
所以转移就是 f[i]=f[i-1]*11+qmi(2,i-1)*a[i]。
代码量比官方题解少了很多。
查看9道真题和解析
