問題一覧 > 通常問題

No.2171 OR Assignment

レベル : / 実行時間制限 : 1ケース 3.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 31
作問者 : tute7627tute7627 / テスター : PCTprobabilityPCTprobability
3 ProblemId : 8861 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-12-20 20:37:51

問題文

長さ $N$ の非負整数列 $A = (A_1, A_2,\dots,A_N)$ が与えられます。

あなたは以下の操作を $0$ 回以上の任意の回数行うことができます。

  • ある整数 $i\ (2 \le i \le N)$ を選択し、$A_{i}$ を $A_i$ と $A_{i-1}$ の bitwise OR で置き換える。

操作後の数列 $A$ としてあり得るものの数を $998244353$ で割ったあまりを求めてください。

入力

$N$
$A_1\ A_2\ \dots \ A_N$

  • $1 \le N \le 2 \times 10^5$
  • $0 \le A_i < 2^{30}$
  • 入力はすべて整数である。

出力

操作後の数列 $A$ としてあり得るものの数を $998244353$ で割ったあまりを出力してください。 最後に改行してください。

サンプル

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

例えば $i = 3$ として操作を行うと数列は $(1,3,3)$ となります。 操作によって $(1,3,2)$ と $(1,3,3)$ 以外の数列にすることはできません。

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

サンプル3
入力
10
440 50 1018 120 821 845 412 60 411 1011
出力
884

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