「题解报告」[POI2008]PER-Permutation点击查看目录目录「题解报告」[POI2008]PER-Permutation思路代码不理解哪里难了，学过扩卢并且推一下式子基本就是两眼切吧。个人感觉顶多上位紫。思路首先设\(f_i\)表示前\(i-1\)位固定，第\(i\)位选一个比原来小的，后面随便排的方案数。显然\((\sum_{i=1}^{n}f_i)+1\)为答案，那么考虑如何快速求出\(f_i\)。考虑用“交换”的思想，即在后\(n-i\)个数中找到比\(a_i\)小的数和它换一下，然后再随便排。然而这里是可重集，所以还要去重乘上\(\dfrac{1}{\prod_{j}(

「题解报告」[POI2008]PER-Permutation点击查看目录目录「题解报告」[POI2008]PER-Permutation思路代码不理解哪里难了，学过扩卢并且推一下式子基本就是两眼切吧。个人感觉顶多上位紫。思路首先设\(f_i\)表示前\(i-1\)位固定，第\(i\)位选一个比原来小的，后面随便排的方案数。显然\((\sum_{i=1}^{n}f_i)+1\)为答案，那么考虑如何快速求出\(f_i\)。考虑用“交换”的思想，即在后\(n-i\)个数中找到比\(a_i\)小的数和它换一下，然后再随便排。然而这里是可重集，所以还要去重乘上\(\dfrac{1}{\prod_{j}(