[ZJOI2010]排列计数

DP 数论

题面

称一个$1,2,...,n$的排列$p_1,p_2...,p_n$是$Magic$的，当且仅当$2\leq i\leq n$时，$p_i>p_{i/2}$。
计算$1,2,...n$的排列中有多少是$Magic$的，答案可能很大，只需输出模$p$以后的值。

• $n\leq10^6,p\leq10^9$

解析

看到题目中的条件，如果你手打过二叉堆模板，就会想起小根堆。
其实就是小根堆。

设$f[i]$表示长度为$i$的排列（小根堆）的答案。
考虑增量转移。
设小根堆根结点左子树大小为$ls$。
那么要从剩下的$i-1$个点中选$ls$个点组成左子树，有$C_{i-1}^{ls}$种方法。
左右两个子树是规模更小的子问题，递归下去就行了。

那么$f[i]=C_{i-1}^{ls}f[ls]f[i-1-ls]$

现在问题是怎么快速求$ls$。
在题目中，小根堆的构建方式是从上往下，一层层地从左往右排数。
那么先搞出大小为$i$的堆排满的层数（为$log_2(i+1)$），剩下的几个数，随便算算即可。

为了节省预处理的时间，可以只预处理模数以内的阶乘，然后卢卡斯一下即可。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;++i)
#define fq(i,a,b) for(re int i=a;i>=b;--i)
using namespace std;
const int N=1e6+100;
int T,n,k,jc[N],inv[N],f[N],mod,lim,lg[N];
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il ll ksm(re ll S,re ll n)
{
  re ll T=S;S=1;
  while(n)
    {
      if(n&1) S=S*T%mod;
      T=T*T%mod;
      n>>=1;
    }
  return S;
}
il ll C(re ll x,re ll y)
{
  if(x<0||y<0||x<y) return 0;
  if(x<mod&&y<mod) return 1ll*jc[x]*inv[y]%mod*inv[x-y]%mod;
  return C(x/mod,y/mod)*C(x%mod,y%mod)%mod;
}
il ll dfs(re int x)
{
  if(~f[x]) return f[x];
  re int ls=x+1-(1<<lg[x+1]);
  if(ls<(1<<lg[x+1]-1)) ls+=(1<<lg[x+1]-1)-1;else ls=(1<<lg[x+1])-1;
  return f[x]=C(x-1,ls)*dfs(ls)%mod*dfs(x-1-ls)%mod;
}
int main()
{
  memset(f,-1,sizeof(f));f[0]=f[1]=1;
  n=gi();mod=gi();
  lim=min(n,mod-1);
  jc[0]=1;fp(i,1,lim) jc[i]=1ll*jc[i-1]*i%mod;
  inv[lim]=ksm(jc[lim],mod-2);
  inv[0]=inv[1]=1;fq(i,lim-1,2) inv[i]=1ll*inv[i+1]*(i+1)%mod;
  fp(i,2,n+1) lg[i]=lg[i>>1]+1;
  printf("%lld\n",dfs(n));
  return 0;
}