[ZJOI2010]排列计数
题目描述
称一个 \(1 \sim n\) 的排列 \(p_1,p_2, \dots ,p_n\) 是 Magic 的，当且仅当
\[\forall i \in [2,n],p_i > p_{\lfloor i/2 \rfloor}
\]
计算 \(1 \sim n\) 的排列中有多少是 Magic 的，答案可能很大，只能输出模 \(m\) 以后的值。
输入格式
一行两个整数 \(n,m\)，含义如上所述。
输出格式
输出文件中仅包含一个整数，表示 \(1\sim n\) 的排列中， Magic 排列的个数模 \(m\) 的值。
样例 #1
样例输入 #1
20 23
样例输出 #1
16
提示
【数据范围】
对于 \(100\%\) 的数据，\(1\le n \le 10^6\), \(1\le m \le 10^9\)，\(m\) 是一个质数。
用数组下标表示每一个点从而构成一个小根堆( \(i << 1\) 和 \(i << 1 | 1\) 表示左右儿子)
从而易得第 \(i\) 个点的方案数为 \(f[father] = C^{size[lson]}_{size[i]-1}f[lson]f[rson]\)
其中\(size[i]\) 表示以 \(i\) 为根节点的子树大小
$C^{size[lson]}_{size[i]-1}$ 表示从 $size[i]-1$ (除了最小点做根节点)选 $size[lson]$ 个点做左子树剩下的点做右子树