問題一覧 > 通常問題

No.2237 Xor Sum Hoge

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 41
作問者 : 👑 potato167 / テスター : noya2
お気に入りにしたユーザー ProblemId : 9239 / 自分の提出
問題文最終更新日: 2023-03-02 18:12:13
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 379 (順位表) の他の問題:

Note

The time limit for this problem is $10$ seconds.

Problem Statement

You are given a positive integer $N$ and non-negative integers $B,C$.

Find the number, modulo $998244353$, of non-negative integer sequences $A=(A_{1},A_{2},...,A_{N})$ of length $N$ that satisfy all of the following conditions.

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

Here, $\oplus$ denotes the bitwise exclusive OR.

What is bitwise exclusive OR?

The bitwise exclusive OR of non-negative integers $X,Y$, denoted $X\oplus Y$, is defined as follows.

  • The $2^{k}$'s place $(0\le k)$ of $X\oplus Y$ in binary is $1$ if the $2^{k}$'s places of $X,Y$ in binary differ, and $0$ otherwise.

For example, $3\oplus 5=6$. (In binary, $011\oplus 101=110$.)

Input

$N$ $B$ $C$
  • All inputs are integers.
  • $1\leq N \leq 6\times 10^{4}$
  • $0\leq B < 2^{60}$
  • $0\leq C < 2^{60}$

Output

Output the answer modulo $998244353$.

Sample

Sample 1
Input
4 5 3
Output
16

The possible $A$ are $A=(0,1,1,3),(1,1,1,2)$ and their permutations, so since $12+4=16$, there are $16$ ways.

Sample 2
Input
13 12 11
Output
0

There are cases where no possible $A$ exists.

Sample 3
Input
924 2001 167
Output
660470654

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