CF1874FJellyfishandOEIS第一次独立切*3500，写篇题解记录一下我们称\([l,r]\)为一个排列，当且仅当\([p_l,p_{l+1},\dots,p_r]\)为\([l,l+1,\dots,r]\)的一个排列。不妨固定\(l\)，我们只需要考虑最小的\(r\)满足\([l,r]\)为一个排列。考虑每个\([l,r]\)所构成的区

JellyfishandOEIS题意题面传送门题解恭恭敬敬给致远磕大头。首先我们将原序列分割成很多块，使得每一块都是相对位置的排列。且这一块内不可分割出另外的块。例如：\([3,1,2][5,4]\)，而\([1,2,3]\)是不合法的，因为他可以被分割为\([1][2][3]\)。在进行这一步操作之后，我们发

把原题做法GF的系数进行OEIS，发现那个三角形就是Catalan数的GF复合上一个\(xy(1-x)\)的形式。更为奇妙的是，OEIS下面竟然给出了一个通项公式，\(T(n,k)=(-1)^{n-k}{k\choosen-k}C_k\)，其中\(C\)是Catalan数列。代入原题的式子，发现答案竟然就是：\[\sum_{i=0}^n(-1)^{n

题目链接不明白出题人的脑回路是不是被宇宙射线改变过/jy。题目给出了若干个区间，要我们计算满足每个区间都不是对应下标的排列的数量，正着计算不满足要求的数量是困难的，我们将其容斥，转化为钦定一些区间要求其必须满足它是对应下标的排列，在下文中，我们称这样的区间为一个约束。我

考虑对\(\summ_i-i+1\)个不可行的集合进行容斥，即钦定一些区间集，要求它们对应的\(p_l,p_{l+1},\cdots,p_r\)必须是\([l,r]\)的排列，计算方案数乘以容斥系数之和。如果容斥的集合中存在相交的区间，那么这个方案数其实不太好计算。不过根据区间的性质，对于\(l_1<l_2\ler_1<r_2