蓝桥杯2018年第九届真题-堆的计数(递推)

解题思路:
采用递推的思想，利用dp[i]记录i排列时可以构造出合法的堆的情况数，由于堆只要求数字的相对大小，故不相等的n个数字可以构造出堆的个数是一致的，同时最小的数字一定在堆顶，(因为如果最小的数字不在堆顶，堆顶的数字就会比它大，堆不合法),对于n个数字的堆，我们这样构造，将最小数字放在堆顶，由于是完全二叉树，剩下n-1个数字可以计算出左右子树的数字个数，记左子树当前需要k个数字，基于上面说的，我们随意的选择k个数字，其构造出的左子树堆个数都是一致，剩下的作为右子树堆个数，依据乘法原理则有dp[i]=dp[k]*dp[i-1-k]*c(i,k)。

利用费马小定理优先处理出阶乘和其逆元，然后利用费马小定理计算c(i,k)。

注意事项:
递推边界，模运算，逆元使用快速幂。复杂度O(nlogn),主要在于逆元的计算。
参考代码:

#include<bits/stdc++.h>
using namespace std;
#define maxx 310000
#define mod 1000000009
#define int long long
int jc[maxx];
int jcf[maxx];
int n,x1,x2;
int dp[maxx];
int poww(int i,int j) //快速幂
{
  if(j==0) return 1;
  if(j==1) return i%mod;
  int q=poww(i,j/2);
  if(j%2==0) return (q*q)%mod;
  else return ((q*q)%mod*i%mod)%mod;
}
void starting()
{
  jc[0]=jcf[0]=1;
  for(int i=1;i<=n;++i) jc[i]=(jc[i-1]*i)%mod;
  for(int i=1;i<=n;++i) jcf[i]=(jcf[i-1]*poww(i,mod-2))%mod;
}
int C(int i,int j) //计算组合数
{
  int q=(jc[i]*jcf[j])%mod;
  return (q*jcf[i-j])%mod;
}
signed main()
{
  cin>>n;
  starting();
  dp[0]=dp[1]=1;
  for(int i=2;i<=n;++i)
  {
    int zs=pow(2,(int)log2(i))-1;
    int sy=i-zs;
    x1=x2=(zs-1)/2;
    x1+=min((zs+1)/2,sy);
    x2+=max((int)0,sy-(zs+1)/2);
    dp[i]=((dp[x1]*dp[x2])%mod*C(i-1,x1))%mod;
  }
 cout<<dp[n];
}