P3200 [HNOI2009] 有趣的数列
感性地，我们认为在按照数值从小到大填数时每个时刻所填的奇数位的个数 \(x\) 不小于所填偶数位的个数 \(y\)。我们考虑如何证明这一点。
性质1：每一个偶数位上的数都要大于它前面所有的数。这一点应当是显然的。
性质2：每一个偶数位上的数都不小于它的下标。这点结合一下性质1，容易知道这个数的最小值就是它的下标了。
反证法。假设 \(x<y\)，则最大偶数位的下标是 \(2y\)。也就是说会有 \(2y-1\) 个数会比它小。但是不包含本次填数，之前一共填过了 \(x+y-1\) 个数，由于 \(x<y\) ，所以 \(x+y-1<2y-1\)，也就是说当前没有填满\(1→2y-1\)的区间。又由于我们的填数是单调的，因此无论下来什么时候填，该区间内定会有一个数大于当前所填的数，违反性质1，矛盾，假设不成立。
那么这就是一个裸卡特兰数的问题了。由于模数不是质数，因此我们只能考虑暴力分解质因数来解决，因此所用的式子是
\[Ans_i=\tbinom{n}{r} \] 标签：数列,题解,偶数,P3200,所填,HNOI2009 From： https://www.cnblogs.com/Rock-N-Roll/p/18048988