3564. 无聊的数学题

单点时限: 1.0 sec

内存限制: 512 MB

这是一个无聊的数学题。

非形式化地说:从 $0, 1, \ldots, 2^n-1$ 中选出若干个数,使得这些数的异或和为 $k$。求有多少种方案?

形式化地说:现给出 $n, p, k$,输出 ${0, 1, \ldots, 2^n-1}$ 有多少个非空子集异或和恰好为 $k$。输出结果模 $p$ 的值。

输入格式

一行三个整数 $n$, $k$, $p$ ($1 \le n \le 10^{18}$, $0 \le k \le \min(2^n-1, 10^{18})$, $2 \le p \le 10^9$, $p$ 是质数)。

样例

Input
2 3 998244353
Output
4

提示

样例解释:$k=3$,有以下四个方案:${1, 2}$, ${3}$, ${0, 3}$, ${0, 1, 2}$。

在数字逻辑中,异或是对两个运算元的一种逻辑分析类型,符号为 XOR 或 ⊕。与一般的逻辑或 OR 不同,当两两数值相同为否,而数值不同时为真。对于任意两个数的异或:先写出这两个数的二进制表示,然后对于每一位进行异或。在 C 语言中写作 a ^ b

61 人解决,109 人已尝试。

86 份提交通过,共有 668 份提交。

5.1 EMB 奖励。

创建: 2 年,2 月前.

修改: 2 年,2 月前.

最后提交: 8 月前.

来源: 2018 华东师范大学校赛

题目标签