编辑器

直方图中最大的矩形

火车进出栈

思路

可以看作是求N阶卡特兰数,公式$\frac{C^n_{2n}}{n+1}=\frac{(2n)!}{n!^2*n+1}=\frac{(n+1)*(n+3)*...*2n}{(n+1)!}$

如果直接用高精度压位会超时

所以我们可以将($2n$)!分解质因数,减去$n!^2*(n+1)$的质因数.但时间复杂度比较高,接近$O(n^2)$,怎么办呢

我们可以想到n!中p的质因子有$\frac{n}{p}+\frac{n}{p^2}+...\frac{n}{p^k}$ 这样我们可以用如下代码分解质因数

int get(int n,int p)
{
	int sum=0;
	while(n)
	{
		sum+=n/p;
		n/=p;
	}
	return sum;
}

最后用高精度压位把这些质因数乘起来就行了(qwq)

代码

#include<bits/stdc++.h>
using namespace std;
const long long bits=1000000000;
int flag[120010],zs[120010],idx=0,cnt_zs[120010];
vector<long long> mul(vector<long long> A,int b)
{
	vector<long long> res;
	long long t=0;
	for(int i=0;i<A.size()||t;i++)
	{
		if(i<A.size()) t=t+A[i]*b;
		res.push_back(t%bits);
		t/=bits;
	}
	while(res.back()==0&&res.size()>1) res.pop_back();
	return res;
}
int get(int n,int p)
{
	int sum=0;
	while(n)
	{
		sum+=n/p;
		n/=p;
	}
	return sum;
}
void catlan(int n)
{
	vector<long long> A;
	A.push_back(1);             
	for(int i=2;i<=2*n;i++) 
	{
		if(!flag[i])
		{
			zs[++idx]=i;
			for(int j=2*i;j<=2*n;j+=i) flag[j]=1;
		}
	}
	for(int i=1;i<=idx;i++) cnt_zs[zs[i]]+=get(2*n,zs[i])-2*get(n,zs[i]);
	int x=n+1;
	for(int i=2;i<=x;i++)
	{
		while(x%i==0)
		{
			cnt_zs[i]--;
			x/=i;
		}
	}
	for(int i=1;i<=idx;i++) for(int j=1;j<=cnt_zs[zs[i]];j++) A=mul(A,zs[i]);
	reverse(A.begin(),A.end());
	for(int i=0;i<A.size();i++) 
	{
		int j=0,zhi=bits/10;
		while(A[i]<zhi&&i)
		{
			zhi/=10;
			j++;
		}
		while(j--) printf("%lld",0);
		printf("%lld",A[i]);
	}
}
int main()
{
	int n,a;
	scanf("%d",&n);
	catlan(n);
}

这是我写的最长的一篇总结