题目描述

给定一个长度为 $n$ 的整数数组 $a=[a_1,a_2,\ldots,a_n]$，统计从中选出长度恰为 $k$ 的交替子序列的方案数。

定义

• 子序列：从数组中选出若干下标 $1 \le i_1 < i_2 < \cdots < i_k \le n$，形成序列 $[a_{i_1},a_{i_2},\ldots,a_{i_k}]$。
• 交替（符号相反）：对任意相邻对 $(a_{i},a_{i_{i+1}})$ 都满足$a_i * a_{i+1} < 0$。即相邻元素的符号严格相反。

输入格式

• 第一行包含两个整数 $n,k$。
• 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个整数，表示满足条件的长度为 $k$ 的交替子序列的方案数。

数据范围

• $1 \le n \le 30$
• $1 \le k \le n$
• $-100 \le a_i \le 100 且 a_i \neq 0$

样例 1

输入

5 3
3 -1 2 -2 4

输出

5

说明 满足条件的长度为 $3$ 的交替子序列共有 $5$ 个： $[3,-1,2]$, $[3,-1,4]$, $[3,-2,4]$, $[-1,2,-2]$, $[2,-2,4]$。

样例 2

输入

3 2
1 1 -1

输出

2

说明 长度为 $2$ 的交替子序列必须相邻乘积 $<0$。 有两个 $[1,-1]$ 合法

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写