传送门：https://atcoder.jp/contests/arc061/tasks/arc061_a
题目大意:给你一个只含 1 ~ 9 的 字符串。你可以在里面插入任意个“+”使得其成为一个合法的算式，问你所有合法 算式 的总和.
方法一:dfs枚举 (n <= 10)
这种方法不介绍了，傻子都会写，当时这道题就是这个数据范围。大概7分钟写完。
方法二： 朴素dp 算子串贡献 (n <= 1e3)
考虑线性dp. 令表示长度为i时的总答案.
我们枚举这个等式的最后一个项是什么，在此基础上算贡献.例如:1234 且 i = 4.
那么等式的最后一项可能是: ... + 3 , ... + 23 , ... + 123. +1234 四种情况。对于这四种情况。我们要特判两种:
234 和 1234. 因为 这两种情况只会出现1次，但 +34会出现4次,+4 会出现 8次。
即：对长度为i的dp.先让他加上 整个数的值，再加上 开头单独数字 + 除开头外整个数的值.因为这两种情况都出现一次.不符合递推规律。如果我们剔除这两种情况，可以统一后续的递推式.
现在我们截取出一段 ... + xyz 了，如何计算它对答案贡献呢？
不难想到, xyz 要乘上 之前那段字符串所能形成的合法式的方案数.也就是xyz在整个合法方案中出现的次数
那有递推式：()
AC代码:https://atcoder.jp/contests/arc061/submissions/17076664
优化dp: n<=5e6 )
其实这一步优化就非常简单了。人类都应该能一眼看出这个递推式能优化吧？我们观察到重复计算的部分，利用各种前缀和优化即可。我原意称之为 dp套dp！
emm，确实没什么好讲的，感觉就mspaint里画画图，举例 123 和 1234 就可以了。细节见代码:
AC代码：https://atcoder.jp/contests/arc061/submissions/17076995
