seuOJ519 - Nanami and the Last Enigma (hard version)

题目描述

简单版和困难版的唯一区别在于对于 n,∑∣a∣,xn,\sum |a|,x 的限制不同。

最终，Nanami 还是来到了医院。

医院的病房排列成了一个长度为 nn 的序列，同时每间病房上都写着一个数字 aa。Nanami给了你一个整数 xx，你需要把医院的病房划分成不相交的 kk 段。称这 kk 段为 [[l1,r1],[l2,r2],…,[lk,rk]][[l_1,r_1],[l_2,r_2],\dots,[l_k,r_k]]，划分需要满足 l1=1,rk=n,li≤ri,ri=li+1−1(i<k)l_1=1,r_k=n,l_i\le r_i,r_i=l_{i+1}-1(i<k)。

请你求出 ∑idx=1k∑i=lidxridx∑j=iridx[(∑s=ijas)=x]\sum_{idx=1}^k\sum_{i={l_{idx}}}^{r_{idx}}\sum_{j=i}^{r_{idx}}[(\sum_{s=i}^{j}a_s)=x] 的最小值，即划分的每段的子段的和为 xx 的数量的和的最小值。

[expr][expr] 代表表达式 exprexpr 的布尔值，即如果 exprexpr 为真，则 [expr]=1[expr]=1；否则，[expr]=0[expr]=0。

一个序列 a1,a2,…,ana_1,a_2,\dots,a_n 的子段是指存在两个下标 l,rl,r 满足 1≤l≤r≤n1\le l\le r\le n，那么 [al,al+1,…,ar][a_l,a_{l+1},\dots,a_r] 就是该序列的一个子段，∑i=lrai\sum_{i=l}^{r}a_i 就是这个子段的和。

输入格式

第一行，两个整数 n,k,x(1≤n≤105;1≤k≤min⁡(20,n);∣x∣≤107)n,k,x(1\le n\le 10^5;1\le k\le\min(20,n);|x|\le 10^7)，分别代表序列的长度、划分序列的段数与整数 xx 的值。

第二行，一个长度为 nn 的序列 aa，其中 ∣ai∣≤105|a_i|\le 10^5。

困难版的额外限制：保证 ∑i=1n∣ai∣≤107\sum_{i=1}^n |a_i|\le 10^7。

输出格式

输出一个整数，代表在所有的划分方案中，划分的每段的子段的和为 xx 的数量的和的最小值。

样例

输入样例

4 2 2
2 2 -2 0

输出样例

2

输入样例

9 3 0
0 -1 -1 1 -1 1 1 -1 -1

输出样例

3

输入样例

1 1 3000
3000

输出样例

1

输入样例

6 2 -2
2 3 2 -1 0 3

输出样例

0

提示

在第一组样例中，采取如下的划分方式 [[1,1],[2,4]][[1,1],[2,4]]，答案为 1+1=21+1=2。

在第二组样例中，采取如下的划分方式 [[1,5],[6,7],[8,9]][[1,5],[6,7],[8,9]]，答案为 3+0+0=33+0+0=3。