P2606 [ZJOI2010]排列计数

题目描述

称一个\(1,2,...,N\)的排列\(P_1,P_2...,P_n\)是\(Magic\)的，当且仅当对所以的\(2<=i<=N\)，有\(P_i>P_{\lfloor i/2 \rfloor}\). 计算\(1,2,...N\)的排列中有多少是\(Magic\)的，答案可能很大，只能输出模\(P\)以后的值

输入输出格式

输入格式：

输入文件的第一行包含两个整数\(n\)和\(p\)，含义如上所述。

输出格式：

输出文件中仅包含一个整数，表示计算\(1,2,...,n-1,n\)的排列中， \(Magic\)排列的个数模\(p\)的值。

说明

\(100\%\)的数据中，\(1 \le N \le 10^6\), \(P \le 10^9\)，\(p\)是一个质数。

---

想了好久啊QAQ

发现按照大小关系构成的一个树形结构就是二叉堆

节点编号为位置的小根堆

要给堆的每个节点不重复都放\(1\)~\(n\)的数，问方案数

到这里就比较容易了

\(dp_i=dp_{ls} \times dp_{rs} \times C_{siz_i-1}^{siz_i-1-siz_{ls}}\)

意义也比较明了了

这里要用lucas处理一下，因为\(p\)可能小于\(n\)

然而\(n|p\)时就比较麻烦了，要用扩展\(lucas\)（我太懒了没写，这样只能过洛谷但过不了bzoj

---

Code:

#include <cstdio>

#define ll long long

#define ls id<<1

#define rs id<<1|1

const int N=1e6+10;

ll n,p,u,fac[N],inv[N];

ll quickpow(ll d,ll k)

{

    ll f=1;

    while(k)

    {

        if(k&1) f=f*d%p;

        d=d*d%p;

        k>>=1;

    }

    return f;

}

void init()

{

    u=(p<n?p:n);

    inv[0]=fac[0]=1;

    for(ll i=1;i<=u;i++)

        fac[i]=fac[i-1]*i%p;

    inv[u]=quickpow(fac[u],p-2);

    for(ll i=u-1;i;i--)

        inv[i]=inv[i+1]*(i+1)%p;

}

ll lucas(ll a,ll b)

{

    if(a<b) return 0;

    if(a<=u) return fac[a]*inv[b]%p*inv[a-b]%p;

    return lucas(a/p,b/p)*lucas(a%p,b%p)%p;

}

ll siz[N<<2];

ll dfs(int id)

{

    if(id>n) return 1ll;

    siz[id]=1;

    ll ans=dfs(ls)*dfs(rs)%p;

    siz[id]+=siz[ls]+siz[rs];

    return ans*lucas(siz[id]-1,siz[id]-1-siz[ls])%p;

}

int main()

{

    scanf("%lld%lld",&n,&p);

    init();

    printf("%lld\n",dfs(1));

    return 0;

}

---

2018.9.23