目录
- CF2201A2 Lost Civilization (Hard Version)
- 题目描述
作者水平有限，不会做1700……
CF2201A2 Lost Civilization (Hard Version)
题目描述
我们定义生成 \(m+k\) 个整数序列的算法如下：
- 首先，输入一个长度为 \(m\) 的整数序列 \(x\)。如果 \(k=0\)，立即终止并返回序列 \(x\)。
- 然后，选择任意一个下标 \(1 \le i \le |x|\)，并在 \(x_i\) 之后插入一个值为 \(x_i+1\) 的元素。
- 如果 \(x\) 恰好包含 \(m+k\) 个整数，终止并返回序列 \(x\)。否则，返回执行第二步。
Alice 知道远古文明曾用这种算法来安全地隐藏他们的秘密。Alice 很想知道他们藏的知识，但根据输出推测输入并不容易。
对于长度为 \(n\) 的整数序列 \(b\)，我们定义 \(f(b)\) 为能够作为该算法输入生成 \(b\) 的最短序列的长度。
给定一个长度为 \(n\) 的整数序列 \(a\)，请计算如下的和：
\[\sum_{l=1}^n {\sum_{r=l}^n {f([a_l,a_{l+1},\ldots,a_r])}}
\]
也就是说，你需要计算 \(a\) 的所有子区间 \(c\) 的 \(f(c)\) 之和。
\(^{\text{∗}}\) 序列 \(a\) 是序列 \(b\) 的子区间，指从 \(b\) 中仅删去若干（可以为零或全部）开头和若干（可以为零或全部）结尾的元素即可得到 \(a\)。若删除元素的位置不同，两个子区间视为不同。