题目链接

BZOJ2111

题目概括

给定$n$,求$[1,n]$的排列有多少满足$p_{\lfloor \frac i2 \rfloor} \le p_i$
答案对给定$p$取模。
数据范围 $n\leq 10^6,p\leq 10^9$

思路要点

计数 DP 好题

首先需要有抽象思维,将原来的问题抽象成$[1,n]$的排列将其塞入一个小根堆中的方案数。(oeis 上也是这样对这个数列进行描述的)

这样的转化是一个双射,因为一个本质不同的小根堆的广搜遍历就唯一对应答案所求的的数列。

考虑一个节点$u$,可以三条性质:

  • $u$是这棵子树中最小的。(小根堆性质)
  • 当前$u$不需要考虑和父亲的关系,因为考虑父亲的时候考虑了和$u$的关系。(只需要考虑当前的关系,也就是$i$和$i\times 2,i\times 2+1$的关系)
  • $u$的两个子树相互独立。

我们现在假设的情况一个独立的状态。简单的说,就是除了$u$的子树还未放好,其他都已经放好的合法状态。

显然,现在需要放置的数一定比$u$要大,也就意味着现在根节点已经被确定了,左右子树内就可以随便放了,这里计算的是组合数,因为我们还没有考虑子树内部的限制,只是确定了那些元素在左边,那些元素在右边。

上述我们计算的每个独立节点的方案数,总的方案数就是其乘积

$$ Ans=\prod_{i=1}^{n}{size[i]-1\choose size[leftson]} $$

因为$p$不一定大于$n$,所以需要用卢卡斯定理来求组合数。

时间复杂度 $O(nLogn)$

代码

#include <bits/stdc++.h>
using namespace std;
template <class T>
void chkmax(T& x, T y) {
  x = x > y ? x : y;
}
template <class T>
void chkmin(T& x, T y) {
  x = x < y ? x : y;
}
template <class T>
void read(T& x) {
  x = 0; char ch = 0; int f = 1;
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
  x *= f;
}
template <class T>
void write(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + 48);
}
template <class T>
void writeln(T x) {
  write(x), puts("");
}
const int N = 1e6 + 5; 
int n, mod;
int fac[N], ifac[N], siz[N];
int power(int x, int y) {
  int res = 1; 
  for (; y; y >>= 1, x = (long long)x * x % mod) 
    if (y & 1) res = (long long)res * x % mod; 
  return res;
}
void pre(int n) {
  fac[0] = 1; 
  for (int i = 1; i <= n; i++) {
    fac[i] = (long long)fac[i - 1] * i % mod; 
  }
  ifac[n] = power(fac[n], mod - 2);
  for (int i = n - 1; i >= 0; i--) {
    ifac[i] = (long long)ifac[i + 1] * (i + 1) % mod; 
  }
}
int C(int n, int m) {
  if (m > n) {
    return 0;
  }
  return (long long)fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
int lucas(int n, int m) {
  if (m == 0) {
    return 1; 
  } else if (n < m) {
    return 0;
  } else {
    return (long long)lucas(n / mod, m / mod) * C(n % mod, m % mod) % mod;
  }
}
int main() {
  read(n), read(mod);
  pre(min(n, mod - 1));
  for (int i = 1; i <= n; i++) {
    siz[i] = 1; 
  }
  for (int i = n; i >= 2; i--) {
    siz[i / 2] += siz[i];
  }
  int ans = 1; 
  for (int i = 1; i <= n / 2; i++) {
    ans = 1ll * ans * lucas(siz[i] - 1, siz[i * 2]) % mod;
  }
  writeln(ans);
  return 0; 
}
/*
  * 1. check the range of array
  * 2. whether your valiable will overflow
  * 3. special case? (n = 1)
  * 4. stay calm and think carefully
*/
最后修改:2020 年 03 月 11 日 09 : 47 AM
如果觉得我的文章对你有用,请随意赞赏