洛谷8月月赛Div1.C

infinities · 2021-08-20 21:54:58 · 题解

upd:修改最后一个式子的一个小错误

挖掘一下题意。

就是给定一个长度为 k 的滑动窗口在长度为 n 的排列上滑，问滑动窗口中的 \max 变化了多少次。（滑动窗口不懂的可以理解成序列中连续 k 个数。这里之所以不写不同数的个数而是变化次数，是因为题目求的是排列，而排列满足所有数各不相同，所以变化次数加 1 就等于不同 \max 个数）

可以发现，因为枚举全排列中的每一个 i 都可以变成 n-i+1（n! 个排列仍然完整），所以我们计算答案，求 \min 和 \max 其实是等价的。（当 \max 做也可以，不过我觉得当 \min 做比较好推式子，以下都当成 \min 做）

接着考虑在什么情况下，滑动窗口在排列上从左往右滑动 1 长度的时候，答案会增加 1（即 \min 值发生变化）。

因为向右滑动 1 长度的情况下，只有窗口最左的数会出窗口，而右边紧邻的那个数会进入窗口，所以我们实际上只需要对于每个窗口看最左边的数是否是窗口滑动之前的最小值，以及新加入的最右边的数是否是窗口滑动之后新的最小值即可。

对于最左边的数是窗口滑动之前是窗口最小值，进行一波推式子之后，可以发现它对答案的贡献有：

其中从左往右，求和符合是枚举这个最小值的大小，组合数是令窗口中剩余的 k-1 个数大于最小值的值的个数，两个阶乘分别是窗口外面的数任意排列和窗口内部除去最小值外任意排列，最后一个 n-k 是计算排列中窗口可以在的位置有 n-k 个。（其实总窗口有 n-k+1 个，就是最左边那个无法移动了）

然后对于新进入的最右边的数是新的窗口最小值，式子是可以类比的：

含义是类似的，只不过计算的是新加进去最右边那个数。

当然，只将这两部分加起来还有一些问题，实际上我们还会算重一部分，既满足最左边是窗口最小值，又满足新加入的是窗口的新最小值（且小于最左边的，或者你可以强制令最右边的是最小的，最左边的小于最右边的，实际上两种方法的式子是一样的），这部分答案需要减掉：

前面同样是类似的，最后的 i-1 是最右边小于最左边的个数，或者你也可以理解成是最左边小于最右边的个数。

注意最后还需要加上每个排列都缺少的 1 答案，也就是总答案加上 n!，因为我们最开始忽略了这部分。

于是简单线性预处理一下组合数，套一下式子就可以了。

核心代码：

    for(int i = 1; i <= n - k; i++){//枚举只到n-k是因为i再大答案就都是0了
        ans += C(n - i, k - 1) * (n - k) % mod * A[n - k] % mod * A[k - 1] % mod;//A是阶乘
        ans %= mod;
        ans += A[n - k - 1] * C(n - i, k) % mod * (n - k) % mod * A[k] % mod;
        ans %= mod;
        ans -= C(n - i, k - 1) * (n - k) % mod * A[n - k - 1] % mod * (i - 1) % mod * A[k - 1] % mod;
        ans %= mod; 
    }
    cout << ((A[n] + ans + mod) % mod + mod) % mod;