T6 Maximum Element (CF886E)

· · 个人记录

T6 Maximum Element (CF886E)

又一道超水黑题

CF传送门

洛谷传送门

题意简述

从前有一个叫 Petya 的神仙，嫌自己的序列求 max 太慢了，于是将序列求 max 的代码改成了下面这个样子：

(太长了缩了一下QwQ)

int fast_max(int n,int a[]){
    int ans=0,offset=0;
    for(int i=0;i<n;++i)
        if(ans<a[i]) ans=a[i],offset=0;
        else{
            offset++;
            if(offset==k)return ans;
        }
    return ans;
}

废话不多说，求有多少长度为 n 的排列，这个函数会返回错误的结果(即返回值不是n)。答案对 1e9+7 取模

数据范围
1 \leq n,k \leq 10^6

不保证 n > k

题解

思路

直接考虑出错的情况太难啦

不妨从反面考虑，正确的情况有多少

其实就是函数在 n 之前都没有退出（只要到了 n，返回值一定是正确的）

这样就可以枚举 n 的位置来计算了

还差一个问题，选出一些数放到 n 的前面，怎么计算不退出的情况数呢？

（这个问题只和元素间的相对大小有关，不妨把它们归结到 i 的排列上来（是一样的）(如果你看不懂上面这段话请当我什么都没说)）

总而言之，是个很明显的dp了

考虑 dp[i] ，表示 i 的排列中函数能够运行完(即中途没有退出) 的方案总数

考虑最大值 max (其实就是 i 但为了不混淆)的位置。显然如果 max 在 [1,i-k] 的话，最后 k 个数肯定都比 max 要小，那肯定就退出了（在最后一个退出也算退出）

反之，只要 max 在 [i-k+1,i] 中，就只需要 max 的前面没有退出就一定不会退出

所以用 j 来枚举 max 的位置

\sum\limits_{j=i-k+1}^i dp[j-1]

别忘了要先从i-1个数中选出j-1个数排到max前面 C^{j-1}_{i-1}

max后面的数是可以随便放的 A^{i-j}_{i-j}=(i-j)!

dp[i]=\sum\limits_{j=i-k+1}^i dp[j-1]C^{j-1}_{i-1} (i-j)!

答案计算就很简单了

ans=n!-\sum\limits_{i=1}^n dp[i-1]C^{n-i}_{n-1}(n-i)!

很遗憾 O(n^2) 过不去

我们来把这个式子打开优化

dp[i] =\sum\limits_{j=i-k+1}^i dp[j-1] C^{j-1}_{i-1} (i-j)! =\sum\limits_{j=i-k+1}^i dp[j-1] \frac{(i-1)!}{(j-1)!(i-j)!}(i-j)! =\sum\limits_{j=i-k+1}^i dp[j-1] \frac{(i-1)!}{(j-1)!} =(i-1) !\sum\limits_{j=i-k+1}^i \frac{dp[j-1]}{(j-1)!} =(i-1) !\sum\limits_{j=i-k}^{i-1} \frac{dp[j]}{j!}

很惊奇地发现 j 可以单独拎出来！

于是前缀和优化

O(n)

当然ans的计算也可以这样优化（不过没什么必要只是为了好写）

ans =n!-\sum\limits_{i=1}^n dp[i-1]C^{n-i}_{n-1}(n-i)! =n!-\sum\limits_{i=1}^n dp[i-1]\frac{(n-1)!}{(i-1)!}

做法

预处理阶乘逆元什么的

已经说得很清楚了吧？

注意事项

· 依旧是开long long

· 记得特判 n<=k

· 注意初始化和特判

AC代码

#include<bits/stdc++.h>
using namespace std;
const long long N=1000005;
long long mod=1e9+7;
long long f[N],s[N],ans=0;
long long mul[N],inv[N];
long long ksm(long long a,long long x){
    long long tot=1;
    while(x){
        if(x&1) tot=tot*a%mod;
        a=a*a%mod,x>>=1;
    }
    return tot;
}
int main(){
    long long n,k; 
    scanf("%lld%lld",&n,&k);
    if(n<=k) {printf("0");return 0;}//特判 
    mul[1]=1;
    for(long long i=2;i<=n;i++) mul[i]=mul[i-1]*i%mod;
    inv[n]=ksm(mul[n],mod-2);
    for(long long i=n-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;//快速处理逆元 

    for(long long i=1;i<=k;i++) f[i]=mul[i],s[i]=(s[i-1]+f[i]*inv[i]%mod)%mod;
    //当i<=k时，所有情况都不会退出 
    for(long long i=k+1;i<=n;i++){
        f[i]=mul[i-1]*((s[i-1]+mod-s[i-k-1])%mod)%mod;//dp 
        s[i]=(s[i-1]+f[i]*inv[i]%mod)%mod;//(f[i]/i)前缀和 
    }

    ans=mul[n-1];//n=1时，就是(n-1)!种，不可不计算
    for(long long i=2;i<=n;i++)
        ans=(ans+f[i-1]*mul[n-1]%mod*inv[i-1]%mod)%mod;//计算答案 
    printf("%lld",(mul[n]+mod-ans)%mod);//取补集 
}