专栏文章

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

sshaun2000
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min8sppk
此快照首次捕获于
2025/12/01 22:26
3 个月前
此快照最后确认于
2025/12/01 22:26
3 个月前
查看原文
考虑每个数对答案的贡献
贡献一定发生于在滑动窗口从左到右时
  1. i进入滑动窗口，最大值变大
  2. i离开滑动窗口，且最大值减小
第二种情况相当于从右往左再滑一遍，答案为第一种*2
考虑何时一个数会成为最大值
首先，共有n-k个位置可进入滑动窗口，i的前面k-1个数均小于i，剩下任意
加上最开始时的答案n!，所以答案为
2∗(n−k)Ci−1kk!(n−k−1)!+n!=2(n−k)!k!Ci−1k+n!2*(n-k)C_{i-1}^{k}k!(n-k-1)!+n!=2(n-k)!k!C_{i-1}^{k}+n!

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...