問題一覧 > 通常問題

No.2237 Xor Sum Hoge

レベル : / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 39
作問者 : 👑 potato167potato167 / テスター : noya2noya2
3 ProblemId : 9239 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-03-02 18:12:13

注意

この問題の実行時間制限は $10$ 秒です。

問題文

正整数 $N$ と、非負整数 $B,C$ が与えられます。

以下の条件をすべて満たす、長さ $N$ の非負整数列 $A=(A_{1},A_{2},...,A_{N})$ の個数を $998244353$ で割ったあまりを求めてください。

  • $A_{1} + A_{2} + \cdots + A_{N}=B$
  • $A_{1}\oplus A_{2}\oplus \cdots \oplus A_{N}=C$

ここで、 $\oplus$ はビットごとの排他的論理和を表します。

ビットごとの排他的論理和とは?

非負整数 $X,Y$ のビットごとの排他的論理和、 $X\oplus Y$ は以下のように定義されます。

  • $X\oplus Y$ を二進表記したときの $2^{k}$の位 $(0\le k)$ は、 $X,Y$ を二進表記したときの $2^{k}$ の位が異なるなら $1$ 、そうでないなら $0$ とする。

例えば、 $3\oplus 5=6$ となります。(二進表記すると $011\oplus 101=110$ )

入力

$N$ $B$ $C$
  • 入力はすべて整数
  • $1\leq N \leq 6\times 10^{4}$
  • $0\leq B < 2^{60}$
  • $0\leq C < 2^{60}$

出力

答えを $998244353$ で割ったあまりを出力してください。

サンプル

サンプル1
入力
4 5 3
出力
16

$A$ として考えられるのは、 $A=(0,1,1,3),(1,1,1,2)$ とそれらの順番を入れ替えたものなので、 $12+4=16$ より、 $16$ 通りです。

サンプル2
入力
13 12 11
出力
0

$A$ として考えられるものが存在しないケースもあります。

サンプル3
入力
924 2001 167
出力
660470654

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