CodeForces - 1312D Count the Arrays(组合数学)
题目链接：点击查看
题目大意：给出一个 n 和 m ，求满足条件的数组有多少个
数组包含 n 个元素 每个元素的取值为 1 ~ m 包含且仅包含一对相同的元素 存在一个位置 pos ，使得 [ 1 , pos ] 内严格递增，[ pos , n ] 内严格递减题目分析：读完题后不难看出是一道排列组合的题目，本着先选数，再排序的原则，我们一步步分析
首先我们需要选出 n 个元素才能构成一个数组，因为需要有一对相同的元素，因此这里我们暂时只需要选出 n - 1 个元素就足够了，共 C( m , n - 1 ) 种情况，因为题目中需要保证在 pos 位置的两侧严格递增或递减，那么说明最大值是唯一的，此时在已经选出的 n - 1 个元素中，减去一个最大值，还剩 n - 2 个元素可以重复一遍，满足题目中的第三个条件，到这一步为止，我们已经处理完了选数的问题，也就是 C( m , n - 1 ) * ( n - 2 ) 种选取方案
接下来需要分析顺序问题，相对于选数问题来说，顺序可能稍微有一丢丢难度，不过一步一步来还是问题不大的，首先我们现在已经选出了 n 个满足前三个条件的元素了，因为满足严格递增和严格递减的限制，所以重复的那个数，以及最大值，这三个数的相对位置都是固定不变的，一定满足最大值位于最中间，而重复的两个值分别位于两侧，其他的 n - 3 个数可能会如何分布呢，无非是在最大值的左侧或右侧两种情况，我们可以发现，如果这 n - 3 个数在左侧或右侧的情况固定下来之后，因为题目中第四个条件的限制，数组的顺序也随之固定下来了，且是唯一的，这样关于顺序的方案数也就呼之欲出了：pow( 2 , n - 3 )
其实看题解的话这个题目的难度并不是很大，我感觉难就难在，考虑顺序的时候，可能会陷入如何分配最大值的位置的陷阱中去，也就是从绝对位置的方向出发，从而越走越偏，其实不然，因为如果考虑绝对位置的话会使题目复杂化，所以我们不妨从相对位置下手，会起到事半功倍的效果
实现代码的话也没什么难度，需要用到的数论知识就是关于逆元的求法了，因为组合数涉及到了取模以及除法，而给出的模数是一个质数，所以直接费马小定理求逆元然后乱搞就好了
代码：
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
作者：Frozen_Guardian
