Hackerrank Summing Pieces-贡献法

传送门

题目大意：

给你一个数列a 把这个数列分成若干个子串 求出所有分法的权值和（权值和的计算方式为：Σ每个子串的长度*每个子串的权值和）（$n\leq10^6$）