No.1825 Except One
タグ : / 解いたユーザー数 95
作問者 :
Shirotsume
/ テスター :
とりゐ
問題文
長さ $M$ の数列 $X = (X_1, X_2, \dots, X_M)$ に対して以下の操作を考えます。
- $1 \leq i \leq M$ を満たす整数 $i$ を選ぶ。 $X_i$ を除く $X$ の要素すべてを $-1$ する。
長さ $2$ 以上の数列 $X$ に対して操作を好きな回数行うことで $X$ の要素すべてを $0$ にできるとき、 $X$ は良い数列であるとします。
長さ $N$ の数列 $A = (A_1, A_2, \dots, A_N)$ が与えられます。数列 $A$ から任意の要素を順番を変えずに取り出し、数列を作る方法は全部で $2^N$ 通りありますが、そのうち取り出してできた数列が良い数列であるものはいくつありますか？
制約
- 入力は全て整数
- $2 \leq N \leq 50$
- $0 \leq A_i \leq 100$ $(1 \leq i \leq N)$
入力
入力は以下の形式で標準入力から与えられる。$N$ $A_1$ $A_2$ $\dots$ $A_N$
出力
答えを出力せよ。最後に改行すること。
サンプル
サンプル1
入力
3 3 1 4
出力
4
できる数列の長さが $2$ 未満である取り出し方は、良い数列にはなりません。
長さが $2$ 以上になる取り出し方は、 $(3, 1, 4), (3, 1), (1, 4), (3, 4)$ の $4$ つです。
これらは全て良い数列です。例えば、 $(3, 1, 4)$ は以下のように操作すれば全ての要素が $0$ になります。
- $i = 1$ とする。 $1$ 番目の要素を除く要素すべてを $-1$ すると、 $(3, 0, 3)$ となる。
- $i = 2$ とする。 $2$ 番目の要素を除く要素すべてを $-1$ すると、 $(2, 0, 2)$ となる。
- $i = 2$ とする。 $2$ 番目の要素を除く要素すべてを $-1$ すると、 $(1, 0, 1)$ となる。
- $i = 2$ とする。 $2$ 番目の要素を除く要素すべてを $-1$ すると、 $(0, 0, 0)$ となる。
サンプル2
入力
3 1 1 4
出力
3
$A = (1, 1, 4)$ から長さが $2$ 以上となるように要素を取り出す方法は、 $(1, 1, 4), (1, 1), (1, 4), (1, 4)$ の $4$ つです。
このうち、 $(1, 1)$ と $(1, 4)$ と $(1, 4)$ の $3$ つは良い数列です。列として同じであっても、要素の選び方が異なるなら別に数えることに注意してください。
$(1, 1, 4)$ はどのように操作しても全ての要素を $0$ にできないので、これは良い数列ではありません。
サンプル3
入力
5 0 0 0 0 0
出力
26
すべての長さ $2$ 以上の部分列が良い数列になります。
サンプル4
入力
50 25 74 40 41 82 15 49 97 63 4 39 0 42 90 100 65 68 48 42 61 9 28 39 97 97 81 93 21 8 32 55 42 21 11 59 66 3 80 9 78 17 52 32 16 89 28 81 20 70 78
出力
52063
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。