Pro：
https://codeforces.com/gym/102900/problem/E
给定\(n,k\)
统计长度为n的
满足对于任意\(i>k\) , \(a_i>min(a_{i-1},a_{i-2}......a_{i-k})\)
的排列方案数
\(n,k<=10^7\)
Sol：
考虑从小到大填入数字
填完\(1\)后，\(2\)只能填在1后面的k个位置之中
同理，3只能填在1或2后面的k个位置之中
继续下去
发现每一个数字都只能填在
所有比它小的数字所占位置的后面连续k个位置组成的连续段
然后填入它后，又可以使这个连续段变长。
这个过程显然可以通过一个\(dp\)来计算
\(dp[n][m]\)表示填到数字\(n\)，当前连续段的长度为\(m\)的方案数
转移考虑使可行连续段长度+1,+2,+3.....+k或-1
用一个前缀和优化即可做到O(n^2)
继续想下去
可以一个更优秀的转移方式
即dp[n]表示当前位置最靠后的数字写在n这个位置的方案数
每次向后转移下一个最后的位置在哪里
然后同时快速计算填写中间空隙的方案数
式子推一下大概张这个样子
用一个前缀和优化即可做到O(n)
ICPC2020上海 E题 The Journey of Geor Autumn
原文：https://www.cnblogs.com/Creed-qwq/p/14159804.html