Public Judge

pjudge

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100 Hackable ✓

# 21695. 【NOIP Round #3】异或序列

Statistics

题目描述

我们说一个长为 $m$ 的正整数序列 $[a_1,\dots,a_m]$ 是好的,当且仅当它满足以下性质:

  1. $m\ne 0$,也就是序列非空。
  2. $a_i>a_{i-1}\ (2\le i\le m)$,也就是序列严格递增。
  3. $1\le a_i\le n\ (1\le i\le m)$,也就是序列的元素都是 $\le n$ 的正整数。
  4. $a_i\operatorname{xor}a_{i+1}\operatorname{xor}a_{i+2}\ne 0\ (1\le i\le m-2)$,也就是序列任意连续三项异或和都不是 $0$。

给定 $n$,请你数一数总共有多少个不同的好的序列。两个序列不同,当且仅当它们长度不同或者长度相同但是某个位置上的数不同。答案对 $mod$ 取模。

输入格式

输入一行两个正整数 $n,mod$。

输出格式

输出一个非负整数表示答案。

样例输入输出

样例输入 1

1 123456789

样例输出 1

1

样例输入 2

2 100000000

样例输出 2

3

样例 2 解释

满足条件的序列有 $[1],[2],[1,2]$ 三种。

样例输入 3

3 666666666

样例输出 3

6

样例 3 解释

满足条件的序列有 $[1],[2],[3],[1,2],[2,3],[1,3]$ 六种。

样例输入 4

5 987654321

样例输出 4

26

样例输入 5

322 998244353

样例输出 5

782852421

数据范围

本题 $10$ 个测试点,每个测试点 $10$ 分。对于所有测试点,$1\le n\le 10^6$,$10^8\le mod\le 10^9$。详细数据范围如下表。

测试点编号 $n\le $
$1$ $5$
$2$ $10$
$3$ $100$
$4$ $500$
$5$ $2000$
$6$ $5000$
$7$ $5\times 10^4$
$8$ $2\times 10^5$
$9,10$ $10^6$

时间限制:$1\texttt{s}$

空间限制:$1024\texttt{MB}$