给你一个数 \(n\) ，让你从 \(n\) 中取出若干数合并成 \(x\) ，剩下数合并成 \(y\) ，求对于所有取法 \(x+y\) 的和
例如 \(12345\) 可以拿出 \(24\) ，剩下 \(135\) ，此时会对答案产生 \(24 + 135\) 的贡献。而 \(42,153\) 或 \(23, 15\) 是不合法的
\(n \leq 10^{10^5}\)
显然 \(\sum x + y = \sum x + \sum y\) ，因此我们单独考虑 \(n\) 中选若干个数合并成的所有 \(x\) 的和，记作 \(cnt\) ，答案即为 \(2cnt\)
这里其实不算是动态规划。设 \(f_i\) 表示第 \(i\) 个位置强制取，剩下的随意的方案数。容易发现：
\[\begin{align} f_i &= a_i 2^{n-i-1} \sum_{j=0}^{i-1} \binom{i-1}{j} 10^j \\ &= a_i 2^{n-i-1} \sum_{j=0}^{i-1} \binom{i-1}{j} 10^j 1^{i-j} \\ &= a_i 2^{n-i-1} (10 + 1)^{i-1} \\ \end{align} \]其中 \(2^{n-i-1}\) 表示 \(i\) 这位之后随便取得方案数， \(\sum_{j=0}^{i-1} \binom{i-1}{j} 10^j\) 表示前 \(i-1\) 个数中取 \(j\) 个时的方案数 \(+\) 产生的贡献
\(cnt = \sum_{i=1}^{n} f_i\)
复杂度 \(O(n \log n)\) ，瓶颈快速幂
标签：10,第四场,sum,T3,牛客,135,binom,align From： https://www.cnblogs.com/fox-konata/p/17757009.html