NC20075. [HNOI2009]有趣的数列
描述
我们称一个长度为2n的数列是有趣的，当且仅当该数列满足以下三个条件：
(1)它是从1到2n共2n个整数的一个排列{ai}；
(2)所有的奇数项满足a1<a3<...<a2n-1，所有的偶数项满足a2<a4<...<a2n；
(3)任意相邻的两项a2i-1与a2i(1<=i<=n)满足奇数项小于偶数项，即：a2i-1<a2i。
现在的任务是：对于给定的n，请求出有多少个不同的长度为2n的有趣的数列。因为最后的答案可能很大，所以只要求输出答案 mod P的值。
输入描述
输入文件只包含用空格隔开的两个整数n和P。
输入数据保证，50%的数据满足n ≤ 1000，100%的数据满足n ≤ 1000000且P ≤ 1000000000。
输出描述
仅含一个整数，表示不同的长度为2n的有趣的数列个数mod P的值。
示例1
输入:
3 10
输出:
5
说明:
对应的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）。C++14(g++5.4) 解法, 执行用时: 144ms, 内存消耗: 16580K, 提交时间: 2019-08-09 13:21:47
#include <bits/stdc++.h>
using namespace std;
int const N = 2e6 + 10;
typedef long long ll;
int tot,n,mod;
int vis[N<<1],prime[N<<1];
int num[N<<1];
void init(){
for(int i=2;i<N;i++){
if(!vis[i]){
vis[i] = i;
prime[tot++] = i;
}
for(int j=0;j<tot&&i*prime[j]<N;j++){
vis[i*prime[j]] = prime[j];
if(i % prime[j] == 0) break;
}
}
}
int main(){
scanf("%d%d",&n,&mod);
init();
for(int i=n+2;i<=2*n;i++){
int t = i;
while(t > 1) num[vis[t]]++, t /= vis[t];
}
for(int i=2;i<=n;i++){
int t = i;
while(t > 1) num[vis[t]]--, t /= vis[t];
}
long long ans = 1;
for(int i=2;i<=2*n;i++){
for(int j=1;j<=num[i];j++)
ans = ans * i % mod;
}
printf("%lld\n",ans);
return 0;
}
C++ 解法, 执行用时: 37ms, 内存消耗: 16512K, 提交时间: 2021-05-21 01:06:59
#include<cstdio>
#define maxn 2000002
using namespace std;
int p[maxn],v[maxn],cnt[maxn];
int qpow(int a,int b,int c){
int i=1;
while(b){
if(b&1)i=i*a%c;
a=a*a%c;
b/=2;
}
return i;
}
int main(){
int n,m,i,j,ans=1;
scanf("%d%d",&n,&m);
for(i=v[1]=2;i<=2*n;i++){
if(!v[i]){
v[i]=i;
p[++p[0]]=i;
}
for(j=1;j<=p[0]&&i*p[j]<=2*n;j++){
v[i*p[j]]=p[j];
if(!(i%p[j]))break;
}
}
for(i=1;i<=n;i++)cnt[i]=-1;
for(i=n+2;i<=2*n;i++)cnt[i]=1;
for(i=2*n;i>1;i--)if(v[i]<i){
cnt[v[i]]+=cnt[i];
cnt[i/v[i]]+=cnt[i];
}
for(i=2;i<=2*n;i++)if(v[i]==i)ans=1ll*ans*qpow(i,cnt[i],m)%m;
printf("%d",ans);
return 0;
}