Codeforces Round #445 Div. 1 C Maximum Element (dp + 组合数学)

题目链接：

http://codeforces.com/contest/889/problem/C

题意：

给你 (n)和 (k)。

让你找一种全排列长度为(n)的 (p)，满足存在下标 (i)，(p_i)大于所有 (p_j)，(jepsilon[1,i-1])同时大于所有(p_i)，(jepsilon[i+1,i+k])。问你满足这样条件的排列有多少种？

题解：

设(dp[i])表示以 (i) 结尾的，满足题目要求的(1) ~ (i)排列。

显然。

如果，(i<=k+1)，则(dp[i]=0)。

因为我们考虑 (i-1) 在这个排列当中的位置。当 (i-1) 和 (i) 之间的数字超过 (k)个时，显然成立，此时共有 ((i-k-1)*(i-2)!) 种序列。

否则，(i-1) 的下标(j >= i-k), 把排列的前 (j) 个数字离散化为都由(1) ~ (j) 组合之后，这些数字组成的排列一定是以 (j) 结尾，满足题目要求的排列，共有(dp[j])个，因为后面的数字少于 (k)个，不可能满足题目要求。(dp[j]) 是离散化之后的结果，离散化之前的结果共有(dp[j]*C(i-2,j-1)*(i-j-1)!=dp[j]*frac{(i-2)!}{(j-1)!})个。可以理解为：先在剩下的 (i-2) 个数当中取 (j-1) 个排在下标为$ 1~j-1的$位置，下标 (j) 之后到最后一个元素之前的位置随意排列)。

所以,两种情况加起来就是：

(dp[i]=(i-k-1)*(i-2)!+sum_{j=i-k}^{i-1}dp[j]*frac{(i-2)!}{(j-1)!})。

但是这样直接计算要 (O(n^2))。

提取一下((i-2)!)，变成：

(dp[i]=(i-k-1)*(i-2)!+(i-2)!*sum_{j=i-k}^{i-1}frac{dp[j]}{(j-1)!})

(= (i-2)!*[(i-k-1)+sum_{j=i-k}^{i-1}frac{dp[j]}{(j-1)!}])

后面一项 (frac{dp[j]}{(j-1)!}) 就可以利用前缀和求出。阶乘的乘除可以利用逆元求出。直接算就是O(n)。

(dp[n])是以 (n) 结尾的排列个数。我们把 (n) 排在不同的位置 (h)，把(n)下标之前的数离散化到(1) ~ (h-1)，跟上面的一样，所以最终答案为:

(sum_{h=1}^{n}dp[h]*frac{(n-1)!}{(h-1)!})。

总复杂度：(O(n))

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1000010;
ll inv[maxn],fac[maxn],dp[maxn],sum[maxn];
const int mod =1e9+7;

ll qpower(ll a,ll b){
  ll res = 1;
  while(b)
  {
    if(b&1)res = res*a%mod;
    b>>=1;
    a= a*a%mod;
  }
  return res;
}

int main(int argc, char const *argv[]) {
  ll n,k;
  ll ans = 0;
  cin>>n>>k;
  if(k+1>=n){
    printf("0
");
    exit(0);
  }
  fac[0] = 1;
  for (int i = 1; i <=n; i++) {
    fac[i] = (fac[i-1] * i) %mod;
  }
  inv[n] = qpower(fac[n],mod-2);
  for(int i=n-1;i>=0;i--){
    inv[i] = inv[i+1] *(i+1);
    inv[i] %= mod;
  }
  memset(dp,0,sizeof(dp));
  memset(sum,0,sizeof(sum));

  for(int i=k+2;i<=n;i++){
    dp[i] = (i-k-1 + (sum[i-1] - sum[i-k-1] +mod)%mod)%mod;
    dp[i] = (dp[i] * fac[i-2]) % mod;
    sum[i] = sum[i-1] + (dp[i] * inv[i-1])%mod;
    sum[i] %= mod;
    ans += (((dp[i] * fac[n-1]) % mod) * inv[i-1])%mod;
    ans %= mod;
  }
  cout<<ans<<endl;
  return 0;
}

ADDITION：

当然也可以把不符合题目条件的先算出来，然后用 (n!)减去不符合条件的个数，即为答案。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1000005;
ll inv[maxn],fac[maxn],dp[maxn],sum[maxn];
const int mod =1e9+7;

ll qpower(ll a,ll b){
  ll res = 1;
  while(b)
  {
    if(b&1)res = res*a%mod;
    b>>=1;
    a= a*a%mod;
  }
  return res;
}
int main(int argc, char const *argv[]) {
  ll n,k;
  cin>>n>>k;
  if(k+1>=n)
  {
    printf("0
");
    exit(0);
  }
  fac[0] = 1;
  for(int i=1;i<=n;i++){
    fac[i] = fac[i-1]*i%mod;
  }
  inv[n] = qpower(fac[n],mod-2);
  for(int i=n-1;i>=0;i--){
    inv[i] = inv[i+1] * (i+1) %mod;
  }
  dp[1] = sum[1] = 1;
  ll ans = fac[n-1];
  for(int i=2;i<=n;i++){
    dp[i] = (sum[i-1] - sum[max(0LL,i-k-1)]) *fac[i-2] %mod;
    sum[i] = (sum[i-1] + dp[i] * inv[i-1]) % mod;
    ans = (ans + dp[i] * fac[n-1] %mod * inv[i-1])%mod;
  }
  cout<<(fac[n]-ans+mod)%mod<<endl;
  return 0;
}