#P2606. [ZJOI2010] 排列计数

    ID: 1614 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp数论数学2010各省省选浙江组合数学

[ZJOI2010] 排列计数

题目描述

称一个 1n1 \sim n 的排列 p1,p2,,pnp_1,p_2, \dots ,p_n 是 Magic 的,当且仅当

i[2,n],pi>pi/2\forall i \in [2,n],p_i > p_{\lfloor i/2 \rfloor}

计算 1n1 \sim n 的排列中有多少是 Magic 的,答案可能很大,只能输出模 mm 以后的值。

输入格式

一行两个整数 n,mn,m,含义如上所述。

输出格式

输出文件中仅包含一个整数,表示 1n1\sim n 的排列中, Magic 排列的个数模 mm 的值。

20 23 
16

提示

【数据范围】
对于 100%100\% 的数据,1n1061\le n \le 10^6, 1m1091\le m \le 10^9mm 是一个质数。