問題一覧 > 通常問題

No.1444 !Andd

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 43
作問者 : ir_1st_vilir_1st_vil / テスター : iaNTUiaNTU
0 ProblemId : 5808 / 出題時の順位表
問題文最終更新日: 2021-03-21 19:28:20

作問者より

この問題はF問題(Andd)を強化したものです。

問題文

長さ $N$ の非負整数列 $A$ と変数 $X=1$ があります。Vil君はこれから $i=1,2,\dots,N$ についてこの順に以下の操作を行います。

  • $X$ を $X \times A_i$ または $X\ \mathrm{AND}\ A_i$ に変化させる

ここで、$\mathrm{AND}$ はビットごとの論理積を表します。

各 $i(1 \le i \le N)$ について $i$ 回目の操作後の $X$ としてあり得る値が何種類あるか求めてください。

入力

$N$
$A_1\ A_2\ \dots\ A_N$
  • 入力はすべて整数
  • $1 \le N \le 2 \times 10^4$
  • $0 \le A_i < 2^{10}$

出力

$N$ 行出力してください。

$i(1 \le i \le N)$ 行目には $i$ 回目の操作後の $X$ としてあり得る値の種類数を出力し、最後に改行してください。

なお、制約の条件下で答えは全て $2^{31}$ 未満になることが証明できます。

サンプル

サンプル1
入力
2
1 4
出力
1
2

$1$ 回目の操作後の $X$ としてあり得るのは $1$ のみです。

$2$ 回目の操作後の $X$ としてあり得るのは $0,4$ の $2$ 種類です。

サンプル2
入力
4
30 29 16 26
出力
2
3
4
5

サンプル3
入力
10
26 7 10 0 10 30 21 30 31 20
出力
2
3
4
1
1
1
1
1
1
1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。