305636: CF1067A. Array Without Local Maximums
Memory Limit:512 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Array Without Local Maximums
题意翻译
## 题目描述 $Ivan$偶然发现一个旧的生日礼物。礼物是一个含有$n$个元素的数组,每个元素都介于$1$和$200$之间。但是现在数组已经很旧了,有的数字难以看清。他记得对于所有元素,它的相邻元素中至少有一个不小于它。也就是说: $a_1\le a_2,a_n\le a_{n-1}$且$a_i\le \max \left( a_{i-1},a_{i+1} \right) $对于任意$i\in \left[ 2,n-1 \right] $都成立。 $Ivan$想知道有多少种方案能够还原这个数组。当然,还原后要保证每个元素仍然介于$1$和$200$之间。输出方案数对$998244353$取模的结果。 ## 输入输出格式 ### 输入格式 第一行一个整数$n\left( 2\le n\le 10^5 \right)$,表示数组大小。 第二行$n$个整数,表示数组中的元素(保证每个元素都介于$1$和$200$之间)。若$a_i=-1$表示这个数已经看不清了。 ### 输出格式 方案数对$998244353$取模的结果。 ## 说明 第一个样例,$a_2$只能为$2$。 第二个样例,$a_1=a_2$,所以有$200$中可能。题目描述
Ivan unexpectedly saw a present from one of his previous birthdays. It is array of $ n $ numbers from $ 1 $ to $ 200 $ . Array is old and some numbers are hard to read. Ivan remembers that for all elements at least one of its neighbours ls not less than it, more formally: $ a_{1} \le a_{2} $ , $ a_{n} \le a_{n-1} $ and $ a_{i} \le max(a_{i-1}, \,\, a_{i+1}) $ for all $ i $ from $ 2 $ to $ n-1 $ . Ivan does not remember the array and asks to find the number of ways to restore it. Restored elements also should be integers from $ 1 $ to $ 200 $ . Since the number of ways can be big, print it modulo $ 998244353 $ .输入输出格式
输入格式
First line of input contains one integer $ n $ ( $ 2 \le n \le 10^{5} $ ) — size of the array. Second line of input contains $ n $ integers $ a_{i} $ — elements of array. Either $ a_{i} = -1 $ or $ 1 \le a_{i} \le 200 $ . $ a_{i} = -1 $ means that $ i $ -th element can't be read.
输出格式
Print number of ways to restore the array modulo $ 998244353 $ .
输入输出样例
输入样例 #1
3
1 -1 2
输出样例 #1
1
输入样例 #2
2
-1 -1
输出样例 #2
200