seuOJ577 - 无聊的猪宝宝

无聊的猪宝宝有一个长度为 $n$ 的整数序列 $a_1,a_2,\cdots,a_n$ 。

它想将其划分成若干段，设为 $[l_1,r_1],[l_2,r_2],\cdots,[l_m,r_m]$ （ $m$ 自行决定），满足：

$l_1=1$ ， $r_m=n$ 。对于任意整数 $i\in[1,m]$ ， $l_i\le r_i$ ，若 $i\ne m$ 则 $r_i+1=l_{i+1}$ 。
以下两个条件中至少有一个成立：
- 条件 A：对于任意整数 $i\in[1,m]$ ，都有 $a_{l_i}\le a_{l_i+1}\le\cdots\le a_{r_i}$ 。
- 条件 B：对于任意整数 $i\in[1,m]$ ，都有 $a_{l_i}\ge a_{l_i+1}\ge\cdots\ge a_{r_i}$ 。

求满足上述要求的划分方案的个数。答案对 $10^9+7$ 取模。

第一行一个整数 $n$ （ $1\le n\le 10^5$ ），表示序列的长度。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$ （ $1\le a_i\le10^9$ ）。

一行一个整数，表示答案对 $10^9+7$ 取模后的结果。

6
1 2 3 2 2 1

可以用两个集合的容斥原理来计算这个样例的答案。

把 $a_1,a_2,\cdots,a_6$ 划分成 $m$ 段，相当于从 $5$ 个邻项之间的间隙中选 $m-1$ 个插入隔板。

要使条件 A 成立，必须且只需在 $a_3$ 与 $a_4$ 之间、 $a_5$ 与 $a_6$ 之间插入隔板，可得方案数为 $2^3=8$ 。

要使条件 B 成立，必须且只需在 $a_1$ 与 $a_2$ 之间、 $a_2$ 与 $a_3$ 之间插入隔板，可得方案数为 $2^3=8$ 。

要使两者同时成立，同理可得方案数为 $2$ 。

所以，答案是 $8+8-2=14$ 。

12
1 1 2 3 2 2 1 9 1000000000 23 24 25