洛谷P3200 [HNOI2009]有趣的数列 (卡特兰数)

题目链接：P3200 [HNOI2009]有趣的数列

题解：

实我们推几个样例就可以发现，其满足卡特兰序列$(1,1,2,5,\mathrm{14...})$,证明啥的可以去看大佬们的题解，我主要是讲一下取余部分.
我们通常求卡特兰序列都是使用公式$f(n)=\frac{C(2\ast n,n)}{n+1}=\frac{{\prod }_{i=n+2}^{2\ast n}i}{{\prod }_{i=1}^{n}i}$，但是因为$p$并不是质数，所以我们无法同年求逆元来解决除法，为了解决这个问题，我们可以把$\frac{{\prod }_{i=n+2}^{2\ast n}i}{{\prod }_{i=1}^{n}i}$的分母拆分成若干个质数的乘积，分母也拆分成若干个质数的乘积，对于某个质数$pi$若在分子中出现了$x$次，在分母中出现了$y$次，其最终将在f(n)中出现$(x-y)$次，因为卡特兰数是正数，所以而质因子直接是不存在整除关系的,这就保证了$x\ge y$,直接找每个数的质因子复杂度有点高。
我们可以给分母中的元素初始系数为-1(因为在最终答案中是贡献为负数)，给分子初始系数为-1(因为在最终答案中是贡献为正数),利用线性筛(有点像倒着的质数筛)快速求各质数最后的系数，最后因为没有除法，就可以直接快速幂取余了
细节可以看代码和注释：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include 
#include
	#ifndef local
	#define endl '\n'
#endif */
#define mkp make_pair
using namespace std;
using std::bitset;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const ll MAXN=2e6+10;
const ll INF=1e18;
const ll N=2e6+100;
const ll mod=1e9+7;
const ll hash_p1=1610612741;
const ll hash_p2=805306457;
const ll hash_p3=402653189;
//-----------------------------------------------------------------------------------------------------------------*/
// ll head[MAXN],net[MAXN],to[MAXN],edge[MAXN]/*流量*/,cost[MAXN]//费用;
/* 
void add(ll u,ll v,ll w,ll s){
	to[++cnt]=v;net[cnt]=head[u];edge[cnt]=w;cost[cnt]=s;head[u]=cnt;
	to[++cnt]=u;net[cnt]=head[v];edge[cnt]=0;cost[cnt]=-s;head[v]=cnt;
}
struct elemt{
	int p,v;
};
-----------------------------------
求[1,MAXN]组合式和逆元 
ll mi(ll a,ll b){
	ll res=1;
	while(b){
		if(b%2){
			res=res*a%mod;
		}	
		a=a*a%mod;
		b/=2;
	}
	return res;
}
ll fac[MAXN+10],inv[MAXN+10];
void init(){
	fac[0]=1;inv[0]=1;
	for(ll i=1;i<=MAXN;i++){
		fac[i]=(fac[i-1]*i)%mod;
		inv[i]=mi(fac[i],mod-2);
	}
}
ll C(int m,int n){//组合式C(m,n); 
	if(!n){
		return 1;
	}
	if(mmp;
struct comp{
	public:
		bool operator()(elemt v1,elemt v2){
			return v1.v --小顶堆  less --大顶堆  
priority_queue,comp>q;

	set::iterator it=st.begin();
*/
//emplace_back()  等于push_back(),但效率更高,传输pair时emplace_back(i,j)==push_back({i,j}) 
// vector>edge; 二维虚拟储存坐标 
//-----------------------------------------------------------------------------------------------------------------*/
//mt19937 rnd(time(0));//高质量随机化函数，直接调用rnd()即可
//mapmp[N]; 
//emplace_back() 
/*
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
*/
ll mi(ll a,ll b,ll p){
	ll res=1;
	while(b){
		if(b%2){
			res=res*a%p;
		}
		a=a*a%p;
		b/=2;
	}
	return res;
}
vector<int>p;//存质数
int vis[N];
int k[N];//对应贡献的系数
int main(){
/*cout<
/*cout<
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//同步流
	int n,m;
	cin>>n>>m;
	for(int i=2;i<=2*n;i++){//预处理出质数
		if(!vis[i]){
			vis[i]=i;
			p.emplace_back(i);
		}
		for(int j=0;j<p.size()&&i*p[j]<=2*n;j++){
			vis[i*p[j]]=p[j];//确定该合数的最小质数
			if(i%p[j]==0){
				break;
			}
		}
	}
	for(int i=2;i<=n;i++){//因为是分母，所以贡献为-1
		k[i]=-1;
	}
	for(int i=n+2;i<=2*n;i++){//因为是分子，所以贡献为1
		k[i]=1;
	}
	for(int i=2*n;i>1;i--){//将合数贡献的系数拆分到各个质数中
		if(vis[i]!=i){//合数
			k[vis[i]]+=k[i];
			k[i/vis[i]]+=k[i];
		}
	}
	ll ans=1;
	for(int i=2;i<=2*n;i++){
		if(vis[i]==i){//合数的贡献都拆分到到质数中了，这里只需要统计质数就可以
			ans=ans*mi(i,k[i],m)%m;
		}
	}
	cout<<ans<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154