暑假集训Day18 J (Catalan数+单调队列)

本文主要是介绍暑假集训Day18 J (Catalan数+单调队列)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接在这里：Problem - J - Codeforces

这是一个Catalan数的应用，关于Catalan数的推导以及其他应用可以看这个博客：(7条消息) n个节点的二叉树有多少种形态（Catalan数）_garrulousabyss的博客-CSDN博客_n个节点的二叉树有多少种

回到这题，我们每次需要把最小的数统计出来，然后一步步的递归下去。

这是官方题解：

 这里学会了一种方法，当统计一段区间里一个数的个数且这个区间与该数的大小有关的时候，可以考虑单调队列的解法。

有一个要注意的地方，在数列的末尾要加一个-1，保证数列的每个数最后都能从单调队列里面取出来。

参考博客：(7条消息) CF gym102501 J. Counting Trees(Catalan数、dfs/单调队列)_小鱼yn的博客-CSDN博客

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 typedef long long LL;
 4 const int MAX=1e6+5;
 5 const int MOD=1000000007;
 6 LL n,m,a[MAX],jie[MAX<<1],q[MAX],cnt[MAX],ans;
 7 void init(){
 8     LL i,j;jie[0]=1;
 9     for (i=1;i<=2*n;i++) jie[i]=i*jie[i-1]%MOD;
10 }
11 LL ksm(LL x,LL y){
12     LL an=1;
13     while (y){
14         if (y&1) an=an*x%MOD;
15         x=x*x%MOD;
16         y>>=1;
17     }
18     return an;
19 }
20 int main(){
21     freopen ("j.in","r",stdin);
22     freopen ("j.out","w",stdout);
23     LL i,j;
24     scanf("%lld",&n);
25     for (i=1;i<=n;i++)
26         scanf("%lld",a+i);
27     a[n+1]=-1;
28     init();
29     LL head,tail;
30     head=1,tail=0;ans=1;
31     memset(cnt,0,sizeof(cnt));
32     for (i=1;i<=n+1;i++){
33         while (head<=tail && a[i]<q[tail]){
34             m=cnt[tail];
35             ans=ans*jie[2*m]%MOD*ksm(jie[m],MOD-2)%MOD*ksm(jie[m+1],MOD-2)%MOD;
36             tail--;
37         }
38         if (head<=tail && a[i]==q[tail])
39             cnt[tail]++;
40         else{
41             tail++;q[tail]=a[i];
42             cnt[tail]=1;
43         }
44     }
45     printf("%lld",ans);
46     return 0;
47 }

这篇关于暑假集训Day18 J (Catalan数+单调队列)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！