← 返回题目列表

Codeforces · 1750/F

F. 多数

中文机器翻译题面 查看原题

每个人都在快乐地编码,直到突然发生电力短缺,最好的竞争性编程网站瘫痪了。幸运的是,一位系统管理员最近购买了一些新设备,其中包括一些UPS。因此,有一些服务器仍然在线,但我们需要所有服务器都正常工作才能保持回合评级。

想象服务器是一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$。如果第 $$$i$$$ 服务器在线,则 $$$s_i = 1$$$,否则 $$$s_i = 0$$$。

系统管理员可以执行以下称为电力传播的操作,该操作包括以下阶段:

- 选择位置 $$$1 \le i < j \le n$$$ 的两台服务器,使两者都在线(即 $$$s_i=s_j=1$$$)。传播仅从在线服务器开始。
- 检查我们是否有足够的力量来进行传播。如果 $$$[i, j]$$$ 范围内打开的服务器数量至少等于 $$$[i, j]$$$ 范围内关闭的服务器数量,我们就认为拥有足够的电量。更正式地说,检查是否 $$$2 \cdot (s_i + s_{i+1} + \ldots + s_j) \ge j - i + 1$$$。
- 如果检查结果为肯定,则打开 $$$[i, j]$$$ 范围内的所有离线服务器。更正式地说,对于从 $$$i$$$ 到 $$$j$$$ 的所有 $$$k$$$,使 $$$s_k := 1$$$ 成立。

如果我们可以使用电力传播操作任意次数(可能是 $$$0$$$)打开所有服务器(即,使 $$$s_i = 1$$$ for $$$1 \le i \le n$$$),那么我们将长度为 $$$n$$$ 的二进制字符串 $$$s$$$ 称为额定值。您的任务是找到长度为 $$$n$$$ 以 $$$m$$$ 为模的额定字符串的数量。

输入

第一行也是唯一一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 5000$$$, $$$10 \le m \le 10^9$$$) — 字符串的长度和所需的模块。

输出

打印单个整数 — 长度为 $$$n$$$ 的额定二进制字符串的数量。由于这个数字可能很大,因此打印它对 $$$m$$$ 取模。

示例

输入 #1

2 100

输出 #1

1

输入 #2

3 10

输出 #2

2

输入 #3

4 3271890

输出 #3

4

输入#4

17 123456

输出#4

32347

注意

在第一个示例中,唯一评级的字符串是 11。因此答案是 $$$1$$$。

在第二个示例中,额定字符串为:

- 111;
- 101,因为我们可以执行 $$$i = 1$$$ 和 $$$j = 3$$$ 的操作。

在第三个示例中,额定字符串为:

- 1001;
- 1111;
- 1011;
- 1101.