No.2237 Xor Sum Hoge
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2