抚州市网站建设_网站建设公司_Photoshop_seo优化

题目描述

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

• 它是从 1∼2n 共 2n 个整数的一个排列 {an​}n=12n​；

• 所有的奇数项满足 a1​<a3​<⋯<a2n−1​，所有的偶数项满足 a2​<a4​<⋯<a2n​；

• 任意相邻的两项 a2i−1​ 与 a2i​ 满足：a2i−1​<a2i​。

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

输入格式

一行两个正整数 n,p。

输出格式

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

输入输出样例

输入 #1复制

3 10

输出 #1复制

5

说明/提示

【数据范围】
对于 50% 的数据，1≤n≤1000；
对于 100% 的数据，1≤n≤106，1≤p≤109。

【样例解释】
对应的 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)。

代码实现：

#include <cstdio> using namespace std; const int N = 2e6 + 5; int v[N], pr[N], c = 0; // 补充快速读入函数 inline int read() { int x = 0; char c = getchar(); while (c < '0' || c > '9') c = getchar(); while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x; } // 补充快速输出函数 inline void writeln(int x) { if (x == 0) { putchar('0'); putchar('\n'); return; } char s[10]; int len = 0; while (x) s[len++] = x % 10 + '0', x /= 10; for (int i = len - 1; i >= 0; i--) putchar(s[i]); putchar('\n'); } inline void sieve(int n) { v[1] = 0; for (int i = 2; i <= n; i++) { if (!v[i]) pr[++c] = i, v[i] = i; for (int j = 1; j <= c && pr[j] * i <= n; j++) { v[pr[j] * i] = pr[j]; if (i % pr[j] == 0) break; } } } inline int qp(int a, int b, int mod) { int res = 1; for (; b; b >>= 1, a = 1ll * a * a % mod) if (b & 1) res = 1ll * res * a % mod; return res; } inline int cnt_p(int n, int p) { int res = 0; while (n) { res += n / p; n /= p; } return res; } int n, r[N], p, ans = 1; signed main(void) { n = read(), p = read(); sieve(2 * n); for (int i = 1; i <= c; i++) r[i] = cnt_p(2 * n, pr[i]) - cnt_p(n, pr[i]) - cnt_p(n + 1, pr[i]); for (int i = 1; i <= c; i++) ans = 1ll * ans * qp(pr[i], r[i], p) % p; writeln(ans); return 0; }