A6591 | 「AHOI2022」山河重整
时间限制3s
内存限制1024MB
通过 / 提交0/0
题目描述
生活在 $998244353$ 号小宇宙的艾和兰收到了归零者的讯息，决定响应回归运动。他们需要把大部分的物质归还给大宇宙，只留下极少的物质用于在新宇宙重建自己的文明。
艾和兰的文明总共有 $n$ 个关键信息，编号为 $1, 2, \dots, n$。他们需要保留的信息是这些关键信息的一个子集 $S$。对于一个编号为 $x$ 的信息，只要 $S$ 中一些关键信息的总和等于 $x$，那么他们设计的漂流瓶就可以在新宇宙将 $x$ 还原出来。
艾和兰不禁想要思考，他们有多少种选择子集 $S$ 的方案，使得关键信息 $1,2,\dots, n$ 均能被还原？艾和兰自然是只用 $1$ 微秒就算出了方案数的精确数值，现在他们想让你帮忙验算。由于方案数可能很大，你只需要输出方案数对 $M$ 取模的结果。
艾和兰的文明总共有 $n$ 个关键信息，编号为 $1, 2, \dots, n$。他们需要保留的信息是这些关键信息的一个子集 $S$。对于一个编号为 $x$ 的信息，只要 $S$ 中一些关键信息的总和等于 $x$，那么他们设计的漂流瓶就可以在新宇宙将 $x$ 还原出来。
艾和兰不禁想要思考，他们有多少种选择子集 $S$ 的方案，使得关键信息 $1,2,\dots, n$ 均能被还原？艾和兰自然是只用 $1$ 微秒就算出了方案数的精确数值，现在他们想让你帮忙验算。由于方案数可能很大，你只需要输出方案数对 $M$ 取模的结果。
输入格式
一行输入两个正整数 $N$、$M$。
输出格式
输出一行一个整数，表示答案对 $M$ 取模的结果。
输入输出样例
输入 #1
4 1000000007
输出 #1
3
输入 #2
10 1000000007
输出 #2
180
输入 #3
1000 65472
输出 #3
2136
输入 #4
100000 100
输出 #4
96
对于 $100\%$ 的数据，保证 $1\leq N\leq 5\times 10^5$，$2\leq M\leq 1.01\times 10^9$。
| 测试点编号 | $N \le$ | $M \le$ |
|:-:|:-:|:-:|
| $1 \sim 2$ | $20$ | $1.01 \times {10}^9$ |
| $3 \sim 4$ | $100$ | $1.01 \times {10}^9$ |
| $5 \sim 6$ | $5000$ | $1.01 \times {10}^9$ |
| $7$ | $3 \times {10}^5$ | $127$ |
| $8$ | $5 \times {10}^5$ | $127$ |
| $9$ | $3 \times {10}^5$ | $1.01 \times {10}^9$ |
| $10$ | $5 \times {10}^5$ | $1.01 \times {10}^9$ |
| 测试点编号 | $N \le$ | $M \le$ |
|:-:|:-:|:-:|
| $1 \sim 2$ | $20$ | $1.01 \times {10}^9$ |
| $3 \sim 4$ | $100$ | $1.01 \times {10}^9$ |
| $5 \sim 6$ | $5000$ | $1.01 \times {10}^9$ |
| $7$ | $3 \times {10}^5$ | $127$ |
| $8$ | $5 \times {10}^5$ | $127$ |
| $9$ | $3 \times {10}^5$ | $1.01 \times {10}^9$ |
| $10$ | $5 \times {10}^5$ | $1.01 \times {10}^9$ |
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？