$\mathrm{Problem’s\ Website}$
$\mathrm{Problem’s \ Description}$
有一个数列,有$m$个元素,每个元素为$1 \thicksim n$,其中有$k$个限制,使第$i$个元素不能取$num$,问所有排列方案的每个元素的乘积和。
$\mathrm{Solution}$
一看这道题,感觉毫无思路,于是我们来推一下式子,我们假设$n=2,m=2,k=0$,设$A$为第一个元素可能的值的集合,$B$为第二个元素可能的值,那我们不难得出
$ans=A_1 \times B_1 + A_1 \times B_2 + A_2 \times B_1 + A_2 \times B_2$
$\Rightarrow \ A_1 \times (B_1 + B_2) \times A_2 \times (B_1 + B_2)$
$\Rightarrow \ (A_1 + A_2) \times (B_1 + B_2)$
当我们推出这个式子时,我们可以已经拿到$70$分的好成绩了,但想要$\mathrm{AC}$还要再进行优化,虽然$n$的范围很大,但是$k$的范围并不大,于是我们可以单独处理$k$,因为如果没有任何限制,那么$A_1 + A_2 \ == \ B_1 + B_2$,所以除了有限制的元素,其他的元素是一样的,所以我们可以直接快速幂求解,然后我们记录一下有限制的元素的编号和限制的数值,单独处理即可$\mathrm{AC}$。
总结一下式子:
$ans=((1 + n) n / 2) ^ {m - cnt} \times \prod\limits^{cnt}_{i=1}{((1+n)n/2) - a[i]}$
$cnt$为去重后限制元素的个数,$a$数组为限制的值的和。
最后温馨提示:取模要注意负数 & 要开$\mathrm{long\ long}$
$\mathrm{Code}$
1 | //Coded by Dy. |
$\mathrm{rp++}$