我们称一个长度为
2
n
2n
2n 的数列是有趣的,当且仅当该数列满足以下三个条件:
它是从
1
∼
2
n
1 \sim 2n
1∼2n 共
2
n
2n
2n 个整数的一个排列
{
a
n
}
n
=
1
2
n
\{a_n\}_{n=1}^{2n}
{an}n=12n;
所有的奇数项满足
a
1
<
a
3
<
⋯
<
a
2
n
−
1
a_1<a_3< \dots < a_{2n-1}
a1<a3<⋯<a2n−1,所有的偶数项满足
a
2
<
a
4
<
⋯
<
a
2
n
a_2<a_4< \dots <a_{2n}
a2<a4<⋯<a2n;
任意相邻的两项
a
2
i
−
1
a_{2i-1}
a2i−1 与
a
2
i
a_{2i}
a2i 满足:
a
2
i
−
1
<
a
2
i
a_{2i-1}<a_{2i}
a2i−1<a2i。
对于给定的
n
n
n,请求出有多少个不同的长度为
2
n
2n
2n 的有趣的数列。
因为最后的答案可能很大,所以只要求输出答案对
p
p
p 取模。
一行两个正整数
n
,
p
n,p
n,p
输出一行一个整数表示答案。
3 10
5
【数据范围】
对于
50
%
50\%
50% 的数据,
1
≤
n
≤
1000
1\le n \le 1000
1≤n≤1000;
对于
100
%
100\%
100% 的数据,
1
≤
n
≤
1
0
6
1\le n \le 10^6
1≤n≤106,
1
≤
p
≤
1
0
9
1\le p \le 10^9
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 <bits/stdc++.h>
#define LL long long
using namespace std;
LL n, p, ans = 1, k;
int vis[2000005];
LL qmi(LL a, LL b, LL p)
{
LL res = 1;
while (b)
{
if (b & 1)
res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
void c(LL x, LL p, LL f)
{
while (x)
k += f * x / p, x /= p;
}
int main()
{
cin >> n >> p;
for (LL i(2); i <= 2 * n; ++i)
{
if (vis[i])
continue;
k = 0;
c(2 * n, i, 1);
c(n + 1, i, -1);
c(n, i, -1);
ans = ans * qmi(i, k, p) % p;
for (LL j(2 * i); j <= 2 * n; j += i)
vis[j] = 1;
}
cout << ans;
return 0;
}
(现在使用,人人均可获得300元大奖)
手机扫一扫
移动阅读更方便
你可能感兴趣的文章