《P3200 [HNOI2009] 有趣的数列》
题目描述
我们称一个长度为 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; }