luogu 3200 [HNOI2009]有趣的数列 卡特兰数+质因数分解

打个表发现我们要求的就是卡特兰数的第 n 项，即 $\frac{C_{2n}^{n}}{n+1}$.

对组合数的阶乘展开，然后暴力分解质因子并开桶统计一下即可.

code:

#include <bits/stdc++.h>

#define N 100040

#define setIO(s) freopen(s".in","r",stdin)

using namespace std;

int nex[N],vis[27];

char str[N];

int main()

{

	// setIO("input");

	int n,i,j;

	scanf("%d",&n);

	nex[0]=-1;

	for(i=1;i<=n;++i)

	{

		scanf("%d",&nex[i]), nex[i]=i-nex[i];

		if(nex[i]) str[i]=str[nex[i]];

		else

		{

			for(j=nex[i-1];~j;j=nex[j]) vis[str[j+1]-'a']=i;

			for(j=0;j<26;++j) if(vis[j]!=i) break;

			str[i]=j+'a';

		}

	}

	printf("%s\n",str+1);

	return 0;

}