1 年生 (A First Grader)
题意翻译
乐乐刚上九年级,学习了20以内的加减法.
有n个一位数,他在最后两个数间填上`=`,在其他数间填`+`或`-`.
对于每种填法,他都会去验算一下,看看等式是否成立.
在计算过程中,若中间结果大于20,或者小于0(乐乐还没学负数),即使等式成立,他也不会继续算.
他想知道,有多少种等式成立的填法.
题目描述
[problemUrl]: https://atcoder.jp/contests/joi2011yo/tasks/joi2011yo_d
JOI 君は小学 $ 1 $ 年生である.JOI君は教わったばかりの足し算,引き算がとても好きで,数字が並んでいるのを見ると最後の $ 2 $ つの数字の間に `=` を入れ,残りの数字の間に必ず `+` または `-` を入れて等式を作って遊んでいる.例えば `8 3 2 4 8 7 2 4 0 8 8` から,等式 `8+3-2-4+8-7-2-4-0+8=8` を作ることができる.
JOI君は等式を作った後,それが正しい等式になっているかを計算して確かめる.ただし,JOI君はまだ負の数は知らないし,$ 20 $ を超える数の計算はできない.したがって,正しい等式のうち左辺を左から計算したとき計算の途中で現れる数が全て $ 0 $ 以上 $ 20 $ 以下の等式だけがJOI君が確かめられる正しい等式である.例えば,`8+3-2-4-8-7+2+4+0+8=8` は 正しい等式だが,途中に現れる `8+3-2-4-8` が負の数なのでJOI君はこの等式が正しいかどうか確かめることができない.
入力として数字の列が与えられたとき,JOI 君が作り,確かめることができる正しい等式の個数を求めるプログラムを作成せよ.
- - - - - -
输入输出格式
输入格式
入力は $ 2 $ 行からなる.$ 1 $ 行目には並んでいる数字の個数を表す整数 $ N $ ($ 3\ \leqq\ N\ \leqq\ 100 $) が書かれている.$ 2 $ 行目には $ 0 $ 以上 $ 9 $ 以下の整数が $ N $ 個,空白を区切りとして書かれている.
与えられる入力データの $ 60 $ %では,JOI 君が作り,確かめることができる正しい等式の個数は $ 2^{31}-1 $ を超えない.また,与えられる入力データの全てにおいて,JOI 君が作り,確かめることができる正しい等式の個数は $ 2^{63}-1 $ を超えない.
输出格式
JOI 君が作り,確かめることができる正しい等式の個数を表す整数を $ 1 $ 行で出力せよ.
- - - - - -
输入输出样例
输入样例 #1
11
8 3 2 4 8 7 2 4 0 8 8
输出样例 #1
10
输入样例 #2
40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1
输出样例 #2
7069052760
说明
### Sample Explanation 1
入力例 $ 1 $ において,JOI君は $ 10 $ 個の正しい等式 - $ 8+3-2-4+8-7-2-4-0+8=8 $ - $ 8+3-2-4+8-7-2-4+0+8=8 $ - $ 8+3+2+4-8-7+2-4-0+8=8 $ - $ 8+3+2+4-8-7+2-4+0+8=8 $ - $ 8+3+2-4+8-7+2+4-0-8=8 $ - $ 8+3+2-4+8-7+2+4+0-8=8 $ - $ 8-3+2+4-8+7+2+4-0-8=8 $ - $ 8-3+2+4-8+7+2+4+0-8=8 $ - $ 8-3+2-4+8+7+2-4-0-8=8 $ - $ 8-3+2-4+8+7+2-4+0-8=8 $ を作り,確かめることができるので $ 10 $ を出力する. - - - - - -
### Sample Explanation 2
入力例 $ 2 $ において,答えが $ 32 $ bit 符号付き整数の範囲に収まらないことに注意せよ.