版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

仓库源文，站点原文

title: "题解 - [Luogu P3200] [HNOI2009] 有趣的数列" categories:

• 算法竞赛
• 题解 tags:
• 算法竞赛
• 题解
• 洛谷
• 省选
• HNOI
• 递推
• 数学
• 数论
• 素数/质数
• 筛法
• Euler筛
• 组合数学
• Catalan数 date: 2021-11-03 17:56:45

题目链接

原始题面

题目描述

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

• 它是从 $1 \sim 2n$ 共 $2n$ 个整数的一个排列 ${an}{n=1}^{2n}$;
• 所有的奇数项满足 $a_1<a3< \dots < a{2n-1}$, 所有的偶数项满足 $a_2<a4< \dots <a{2n}$;
• 任意相邻的两项 $a{2i-1}$ 与 $a{2i}$ 满足: $a{2i-1}<a{2i}$

对于给定的 $n$, 请求出有多少个不同的长度为 $2n$ 的有趣的数列. 因为最后的答案可能很大, 所以只要求输出答案对 $p$ 取模

输入输出格式

输入格式

一行两个正整数 $n,p$

输出格式

输出一行一个整数表示答案

输入输出样例

输入样例 #1

3 10

输出样例 #1

5

说明

【数据范围】

对于 $50\%$ 的数据, $1\le n \le 1000$;

对于 $100\%$ 的数据, $1\le n \le 10^6$, $1\le p \le 10^9$

【样例解释】

对应的 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)

题意简述

求

$$ H_{n-1}\bmod p={ \binom{2n}{n}\over n+1}\bmod p $$

解题思路

首先筛出所有素数, 然后计算答案唯一分解式的各个幂次即可

注意到 $(ab)^c=a^cb^c$, 故这些幂次可以逆序线性递推得到

复杂度

$O(n)$

代码参考