题解 CF57C 【Array】

Prurite · 2018-07-24 09:37:00 · 题解

这道题是一道很精妙的组合数学。

总思想：转化

首先，因为不增和不降是相对称的，所以我们只用从一个角度入手进行计算。 因为题目中保证了原序列只有 1-n 这些数，且它们的顺序是固定的， 所以我们可以用一个集合 S=\{ x_1, x_2, \ldots, x_i \} 来唯一地表示这个序列 （ x_i 表示序列中数字 i 的数量）。 所以 x_1+x_2+...+x_n = n . 因为 S 和原序列存在对应关系， 所以我们只需求出有多少种不同的 S 就能知道有多少种不同的序列。 【第一次转化】

因为 \sum\limits_{i=1}^n x_i=n， 所以问题又可以转化为有 n 个 1 ，在中间插入 n-1 个隔板的方案数。 （每相邻两个隔板间的 1 的个数就是对应的 x_i 的值。） 比如，对于下面这种方案 | 1 1 || 1 |，有 n=3, x_1=2, x_2=0, x_3=1 . 当然实际计算的时候为了简明就 不计两端的隔板 。 【第二次转化】
对于这个问题，可以这么理解： 假设一共有 2n-1 个位置，其中有 n 个位置放1，另外 n-1 个位置放隔板。 这里就显然有 C_{2n-1}^n 种方法放 1 （从 2n-1 个位置里选 n 个位置的方案数）

我们再回到原问题。 由上得到单独的不升/不降序列就有 C_{2n-1}^n 种不同的序列， 那两种情况合并就有 2C_{2n-1}^n 种。 注意如 1 1 1 1 这种全部相同的情况（共有 n 种）被考虑了两次，还要除去。 最终答案为 2C_{2n-1}^n-n . 注意因为涉及到除法取模需要使用逆元。

思路明确了代码就很简单了，此处就不贴出来了。