#P2606. [ZJOI2010] 排列计数
[ZJOI2010] 排列计数
题目描述
称一个 的排列 是 Magic 的,当且仅当
计算 的排列中有多少是 Magic 的,答案可能很大,只能输出模 以后的值。
输入格式
一行两个整数 ,含义如上所述。
输出格式
输出文件中仅包含一个整数,表示 的排列中, Magic 排列的个数模 的值。
20 23
16
提示
【数据范围】
对于 的数据,, , 是一个质数。
称一个 1∼n 的排列 p1,p2,…,pn 是 Magic 的,当且仅当
∀i∈[2,n],pi>p⌊i/2⌋计算 1∼n 的排列中有多少是 Magic 的,答案可能很大,只能输出模 m 以后的值。
一行两个整数 n,m,含义如上所述。
输出文件中仅包含一个整数,表示 1∼n 的排列中, Magic 排列的个数模 m 的值。
20 23
16
【数据范围】
对于 100% 的数据,1≤n≤106, 1≤m≤109,m 是一个质数。