做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU 牛客网

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 签到 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 2941. -- 「一本通 6.6 练习 10」有趣的数列

2941: 「一本通 6.6 练习 10」有趣的数列

时间限制: 1 Sec  内存限制: 512 MB
提交: 0  解决: 0
[上一题][提交][讨论版][状态][下一题]

题目描述

我们称一个长度为 2n2n2n 的数列是有趣的,当且仅当该数列满足以下三个条件:

  1. 它是从 1112n2n2n2n2n2n 个整数的一个排列 {ai}{a_i}{ai}
  2. 所有的奇数项满足 a1<a3<⋯<a2n−1a_1lt a_3lt cdots lt a_{2n-1}a1<a3<<a2n1,所有的偶数项满足 a2<a4<⋯<a2na_2lt a_4lt cdots lt a_{2n}a2<a4<<a2n
  3. 任意相邻的两项 a2i−1a_{2i-1}a2i1a2i(1≤i≤n)a_{2i}(1le ile n)a2i(1in) 满足奇数项小于偶数项,即:a2i−1<a2ia_{2i-1}lt a_{2i}a2i1<a2i

任务是:对于给定的 nnn,请求出有多少个不同的长度为 2n2n2n 的有趣的数列。因为最后的答案可能很大,所以只要求输出答案 modP 的值。

输入

只包含用空格隔开的两个整数 nnnPPP

输出

仅含一个整数,表示不同的长度为 2n2n2n 的有趣的数列个数 modP 的值。

提示

样例输入

3 10

样例输出

5

样例说明

对应的 555 个有趣的数列分别为 {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}{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}{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}

对于 50%50\%50% 的数据,n≤1000,P≤106nle 1000,Ple 10^6n1000,P106
对于全部数据,1≤n≤106,2≤P≤1091le nle 10^6,2le Ple 10^91n106,2P109

标签

[上一题][提交][讨论版][状态][下一题]