問題一覧 > 通常問題

No.1958 Bit Game

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 93
作問者 : PCTprobabilityPCTprobability / テスター : tute7627tute7627
1 ProblemId : 7829 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-27 21:23:59

問題文

整数列 $A=(A_1,A_2,\dots,A_X),B=(B_1,B_2,\dots,B_Y)$ が与えられます。

始め整数 $P=0$ があり、PCT 君と tute さんは以下の操作を $N$ 回繰り返します。

  • まず、PCT 君が $A$ から要素を一様ランダムに $1$ 個選ぶ。選んだ要素を $Q$ とし、$P$ を $P\ \mathrm{or}\ Q$ で置き換える。
  • 次に、tute さんが $B$ から要素を一様ランダムに $1$ 個選ぶ。選んだ要素を $R$ とし、$P$ を $P\ \mathrm{and}\ R$ で置き換える。

$N$ 回の操作としてあり得るものは $(XY)^N$ 個あります。その全てに対して操作終了時の $P$ の総和 $\bmod 998244353$ を求めてください。

ただし、問題文の $\mathrm{or}$ とはビットごとの論理和で、$\mathrm{and}$ とはビットごとの論理積です。

入力

$N\ X\ Y$
$A_1\ A_2\ \dots\ A_{X}$
$B_1\ B_2\ \dots\ B_{Y}$

  • 入力は全て整数である。
  • $1 \le N \le 2 \times 10^5$
  • $1 \le X,Y \le 2^{18}$
  • $0 \le A_i,B_j < 2^{18}$

出力

答えを $1$ 行に出力してください。

サンプル

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

操作は $1$ 回のみ行います。 PCT 君が $1$ を、tute 君が $2$ を選んだ場合操作終了時の $P$ は $0$ です。 PCT 君が $1$ を、tute 君が $3$ を選んだ場合操作終了時の $P$ は $1$ です。 より、解は $0+1=1$ です。

サンプル2
入力
5 4 3
1 2 3 4
5 6 7
出力
1130844

サンプル3
入力
527 5 5
0 1 2 3 4
5 6 7 8 9
出力
248270434

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