[luogu1485 HNOI2009] 有趣的数列 (组合数学卡特兰数)

Solution

卡特兰数排队问题的简单变化答案为\(C_{2n}^n \pmod p\)

由于没有逆元，只好用分解质因数,易证可以整除

Code

//By Menteur_Hxy

#include <ctime>

#include <cmath>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define Re register

#define Ms(a,b) memset(a,(b),sizeof(a))

#define Fo(i,a,b) for(Re int i=(a),_=(b);i<=_;i++)

#define Ro(i,a,b) for(Re int i=(b),_=(a);i>=_;i--)

using namespace std;

typedef long long LL;

inline int read() {

    int x=0,f=1;char c=getchar();

    while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}

    while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();

    return x*f;

}

const int N=2e6+10;

int tot,ans=1,n,MOD;

bool vis[N];

int pri[N],d[N];

void init(int Lim) {

	Fo(i,2,Lim) {

		if(!vis[i]) pri[++tot]=i;

		for(Re int j=1;i*pri[j]<=Lim&&j<=tot;j++) {

			vis[i*pri[j]]=1;

			if(i%pri[j]==0) break;

		}

	}

}

void Divid(int x,int w) {

	for(Re int i=1;i<=tot&&pri[i]*pri[i]<=x;i++)

		while(x%pri[i]==0) x/=pri[i],d[pri[i]]+=w;

	if(x>1) d[x]+=w;//!!!

}

LL qpow(LL a,int b) {LL t=1;for(;b;b>>=1,a=a*a%MOD)if(b&1)t=t*a%MOD;return t;}

int main() {

	n=read(),MOD=read();init(n+n);Divid(n+1,-1);

	Fo(i,n+1,n+n) Divid(i,1); Fo(i,1,n) Divid(i,-1);

	Fo(i,1,n+n) ans=1ll*ans*qpow(i,d[i])%MOD;

	printf("%d",ans);

	return 0;

}

巴特西

[luogu1485 HNOI2009] 有趣的数列 (组合数学卡特兰数)

Solution

Code

最新文章

热门文章

巴特西

[luogu1485 HNOI2009] 有趣的数列 (组合数学 卡特兰数)

Solution

Code

最新文章

热门文章

[luogu1485 HNOI2009] 有趣的数列 (组合数学卡特兰数)