Codeforces889C. Maximum Element

$n \leq 2000000$的排列，问有多少满足：存在个$i$，使得$p_i \neq n$，且$p_j<p_i,j \in [i+1,i+K]$，$K \leq 2000000$是给定常数。膜$1e9+7$。

排列题还是比较菜。。

这次的切入点依然是排列题的经典套路--考虑将$n$加入$n-1$的合法排列，从而建立递推关系。

先从答案要求入手，假如把$n$插进位置$i$，那么$i$之前的序列必须已经合法，否则要么接下来一个数是$n$，后面$K$个数一定$<n$，不合法，要么这序列根本就不合法，就gg。也就是说，$n$之前的数字的大小关系已经确定了。确定大小关系的情况可以开始递推：$D(i)$表示$i$在位置$i$时，剩下$i-1$个数乱排时的合法排列数——$n$（注意，这里真的是$n$）在位置$i$时，前$i-1$个数一旦确定，他们的大小关系必须如同$D(i)$的方案，然后其他的数乱排列。因此最终答案为$\sum_{i=1}^{n}D(i)\frac{(n-1)!}{(i-1)!}$。搞定。

注意这里通过大小关系把$n$变成更小的东西。

现在试着求$D(i)$。首先$i<=K$时$D(i)=0$这实际上排除了一重条件$p_i \neq n$，因为此时造成$p_j<p_i,j \in [i+1,i+K]$的只有非$n$的数。好那就来看看剩下最大的$n-1$。当$n-1$放在前$i-K-1$个位置时，它就是符合条件的$i$。当它放在$i-K$往后的位置时，又来！此时$n-1$后边是不可能有非法$i$了，但前面一定有，大小关系又是$D$！于是有$D(n)=(n-K-1)(n-2)!+\sum_{i=n-K}^{n-1}D(i)*\frac{(n-2)!}{(i-1)!}$，把$(n-2)!$提到前面，记个前缀和即可。

 //#include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<cstdio>

 //#include<queue>

 //#include<time.h>

 //#include<complex>

 #include<algorithm>

 #include<stdlib.h>

 using namespace std;

 int n,K;

 #define maxn 2000011

 const int mod=1e9+;

 int fac[maxn],inv[maxn];

 int powmod(int a,int b)

 {

     int ans=;

     while (b)

     {

         if (b&) ans=1ll*a*ans%mod;

         a=1ll*a*a%mod; b>>=;

     }

     return ans;

 }

 int sum[maxn],f[maxn];

 int main()

 {

     scanf("%d%d",&n,&K);

     fac[]=; for (int i=;i<=n;i++) fac[i]=fac[i-]*1ll*i%mod;

     inv[n]=powmod(fac[n],mod-); for (int i=n;i>=;i--) inv[i-]=1ll*inv[i]*i%mod;

     for (int i=;i<=K;i++) f[i]=sum[i]=;

     for (int i=K+;i<=n;i++)

     {

         f[i]=(1ll*(i-K-)*fac[i-]%mod+1ll*fac[i-]*(sum[i-]+mod-sum[i-K-])%mod)%mod;

         sum[i]=(sum[i-]+1ll*f[i]*inv[i-])%mod;

     }

     int ans=;

     for (int i=;i<=n;i++) ans=(ans+1ll*(sum[i]-sum[i-]+mod)*fac[n-])%mod;

     printf("%d\n",ans);

     return ;

 }

巴特西

Codeforces889C. Maximum Element

最新文章

热门文章