Dew有一个长为n的集合S。有一天，他想选k个不同的元素出来做游戏。
但是Dew只有两只手，所以他只能先选出k个元素，然后拿出这k个元素中最小的两个。
事实上，Dew更喜欢这k个元素中第二小的那个，因此他会记一个集合T的第二小值为g(T)。此时Dew可以获得c^g(T)!的得分，其中c是一个常数，!表示阶乘。
现在你需要求出Dew从集合S中选出k个元素后，他的期望得分对998244353取模的结果。
•题目描述
Dew有一个长为n的集合S。有一天，他想选k个不同的元素出来做游戏。
但是Dew只有两只手，所以他只能先选出k个元素，然后拿出这k个元素中最小的两个。
事实上，Dew更喜欢这k个元素中第二小的那个，因此他会记一个集合T的第二小值为g(T)。此时Dew可以获得c^g(T)!的得分，其中c是一个常数，!表示阶乘。
现在你需要求出Dew从集合S中选出k个元素后，他的期望得分对998244353取模的结果。输入
输入共两行。
第一行三个正整数n,k,c，分别表示集合S的大小，Dew要选的元素个数，和常数c。
第二行n个互不相同的正整数ai，表示集合S中的元素。保证。
输出
输出一行一个非负整数，表示 Dew 的期望得分对998244353取模的结果。样例输入
5 3 2 1 2 3 4 5样例输出
803628674
•思路
有n个数a1,a2,a3,a4,....(升序排列)，从中选出k个，
总的情况数是C(n,k)种，
其中a2是第二小数的有C(n-2,k-2)个，a2是第二小，肯定得选a1,a2，再从剩下的(n-2)个里选出(k-2)个
其中a3是第二小数的有2*C(n-3,k-2)个,a3是第二小，肯定得选且只能选a1,a2中的一个即两种情况，再从剩下的(n-3)个里选出(k-2)个
其中a4是第二小数的有3*C(n-4,k-2)个,a4是第二小，肯定得选且只能选a1,a2,a3中的一个即三种情况，再从剩下的(n-4)个里选出(k-2)个
...
得到选每个数的情况是
所以被选择的期望
然后再乘以阶乘，最终结果为
•细节处理
除法取模：
指数取模：
•代码
UPC Contest RankList – 2019年第二阶段我要变强个人训练赛第十六场
原文：https://www.cnblogs.com/MMMinoz/p/11200121.html
