P7322 「PMOI-4」排列变换 (学习笔记)

· · 个人记录

考虑每个数对答案的贡献

贡献一定发生于在滑动窗口从左到右时

  1. i进入滑动窗口，最大值变大
  2. i离开滑动窗口，且最大值减小

第二种情况相当于从右往左再滑一遍，答案为第一种*2

考虑何时一个数会成为最大值

首先，共有n-k个位置可进入滑动窗口，i的前面k-1个数均小于i，剩下任意

加上最开始时的答案n!，所以答案为

2*(n-k)C_{i-1}^{k}k!(n-k-1)!+n!=2(n-k)!k!C_{i-1}^{k}+n!