加算操作

zengyeanbolt / 2023-05-03 / 原文

【2022重庆市中考A卷数学选择压轴题】加算操作

题目背景

2022重庆市中考A卷数学选择压轴题。

题目描述

现定义加算操作为对于长度为 $n$ 的只含减法运算的序列 $a_1 -a_2-\cdots -a_{n-1}-a_n$，可以随意在其中两项加入一对括号，比如，对于 $a_1-a_2-a_3-a_4-a_5$，可以进行加算操作变成 $a_1-a_2-(a_3-a_4-a_5)$。

给定一个长度为 $n$ 的序列，可以进行 $m$ 次加算操作（不需要恰好进行 $m$ 次），最终可以得到多少种不同的序列和。

输入格式

第一行两个整数 $n,m$。

第二行输入 $n$ 项，代表序列中每个项的值。

输出格式

输出一行，表示最终可以得到多少种不同的序列和。

样例 #1

样例输入 #1

3 1
3 2 1

样例输出 #1

样例解释 #1

$3-2-1=0$

$3-(2-1)=1$

$(3-2)-1=0$

$(3-2-1)=0$

总共有2种不同的序列和 0、1。

样例 #2

样例输入 #2

4 2
3 2 1 1

样例输出 #2

样例 #3

样例输入 #3

4 2
3 1 2 2

样例输出 #3

样例 #4

样例输入 #4

4 2
-3 1 -2 2

样例输出 #4

样例解释 #4

总共有 3 种不同的序列和 -4、0、-8，可以经过以下操作得到：

$-3-1-(-2)-2=-4$

$-3-1-[(-2)-2]=0$

$-3-[1-(-2)]-2=-8$

提示

对于15%的数据，$1≤n≤15，-10≤a_i≤10，1≤m≤5$。

对于30%的数据，$1≤n≤40，-30≤a_i≤30，1≤m≤10$。

对于70%的数据，$1≤n≤120，-70≤a_i≤70，1≤m≤20$。

额外5%的数据，$1≤n≤200，-200≤a_i≤200，m=0$。

对于全部数据，$1≤n≤200，-200≤a_i≤200，0≤m≤50$。

加算操作题解

首先需要把问题转换一下，发现除了 $a_2$ 前面的减号不可能变成加号以及 $a_1$ 前面始终是加号外，其他各项前面的符号都可以随意改变，且连续的一串加号会花费一次操作。不难设 $f_{i,j,0/1,s}$ 表示现在是第 i 位，包括第 i 位进行了 j 次操作，当前位的符号为正就是 0，为负就是 1，当前所有操作后得到的和是 s。

不难得到：
$$
f_{i,j,0,s}=f_{i-1,j,0,s-a[i]}+f_{i-1,j-1,1,s-a[i]}\
f_{i,j,1,s}=f_{i-1,j,0,s+a[i]}+f_{i-1,j,1,s+a[i]}\
sum=\sum_{i=1}^n|a_i|\
ans=\sum_{i=0}^{m\sum_{j=-sum}}f_{n,i,0,j}+f_{n,i,1,j}
$$
时间复杂度为 $O(nmS)$，其中 $S=na$ ，即 $O(n^2am)$

发现每一位的状态只有 0 和 1，用 bitset 压位得到最终复杂度 $O(\frac{n^2am}{w})$。