#2425. 山河重整

山河重整

山河重整

题目描述

NOI 2022 安徽省省队选拔 山河重整(rebuild) 山河重整(rebuild) 【题目描述】 生活在998244353 号小宇宙的艾和兰收到了归零者的讯息,决定响应回归运动。他 们需要把大部分的物质归还给大宇宙,只留下极少的物质用于在新宇宙重建自己的文 明。 艾和兰的文明总共有n 个关键信息,编号为1, 2, . . . , n。他们需要保留的信息是这 些关键信息的一个子集S。对于一个编号为x 的信息,只要S 中一个子集的编号和等 于x,那么他们设计的漂流瓶就可以在新宇宙将x 还原出来。 艾和兰不禁想要思考,他们有多少种选择子集S 的方案,使得关键信息1, 2, . . . , n 均能被还原?艾和兰自然是只用1 微秒就算出了方案数的精确数值,现在他们想让你帮 忙验算。由于方案数可能很大,你只需要输出方案数对M 取模的结果。 【输入格式】 从文件rebuild.in 中读入数据。 一行输入两个正整数N, M。 【输出格式】 输出到文件rebuild.out 中。 输出一行一个整数,表示答案对M 取模的结果。 【样例1 输入】 1 4 1000000007 【样例1 输出】 1 3 【样例1 解释】 总共有以下3 个集合满足条件: • {1, 2, 3} • {1, 2, 4} • {1, 2, 3, 4} 第8 页 共15 页

NOI 2022 安徽省省队选拔 山河重整(rebuild) 【样例2 输入】 1 10 1000000007 【样例2 输出】 1 180 【样例3 输入】 1 1000 65472 【样例3 输出】 1 2136 【样例4 输入】 1 100000 100 【样例4 输出】 1 96 【子任务】 对于100% 的数据,保证1 ≤N ≤5 × 105,2 ≤M ≤1.01 × 109。 测试点编号 N ≤ M ≤ 1,2 20 1.01 × 109 3,4 102 5,6 5, 000 7 3 × 105 127 8 5 × 105 9 3 × 105 1.01 × 109 10 5 × 105 第9 页 共15 页

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

4 1000000007
3

样例 2

10 1000000007
180