#PQJ2818x16220. QOJ 2818_16220
QOJ 2818_16220
我们称一个长度为 2 𝑛 的数列是有趣的,当且仅当该数列满足以下三个条件:
它是从 1 到 2 𝑛 共 2 𝑛 个整数的一个排列 𝑎 𝑖 ; 所有的奇数项满足 𝑎 1 < 𝑎 3 < ⋯ < 𝑎 2 𝑛 − 1 ,所有的偶数项满足 𝑎 2 < 𝑎 4 < ⋯ < 𝑎 2 𝑛 ; 任意相邻的两项 𝑎 2 𝑖 − 1 与 𝑎 2 𝑖 ( 1 ≤ 𝑖 ≤ 𝑛 )满足奇数项小于偶数项,即: 𝑎 2 𝑖 − 1 < 𝑎 2 𝑖 。
现在的任务是:对于给定的 𝑛 ,求出有多少个不同的长度为 2 𝑛 的有趣的数列。因为最后的答案可能很大,所以只要求输出答案 mod 𝑃 的值。
输入格式
输入文件只包含用空格隔开的两个整数 𝑛 和 𝑃 。输入数据保证: 50% 的数据满足 𝑛 ≤ 1000 ,100% 的数据满足 𝑛 ≤ 1000000 且 𝑃 ≤ 1000000000 。
输出格式
输出仅包含一个整数,表示不同的长度为 2 𝑛 的有趣的数列个数 mod 𝑃 的值。
样例数据 input.txt 3 10 output.txt 5 输入输出样例说明
对应的 5 个有趣的数列分别为 ( 1 , 2 , 3 , 4 , 5 , 6 ) , ( 1 , 2 , 3 , 5 , 4 , 6 ) , ( 1 , 3 , 2 , 4 , 5 , 6 ) , ( 1 , 3 , 2 , 5 , 4 , 6 ) , ( 1 , 4 , 2 , 5 , 3 , 6 ) 。