洛谷P2606 [ZJOI2010]排列计数 题解

题目链接：P2606 [ZJOI2010]排列计数

题意：

称一个 \(1 \sim n\) 的排列 \(p_1,p_2, \dots ,p_n\) 是 Magic 的，当且仅当 \[ \forall i \in [2,n], p_{\lfloor i/2 \rfloor} < p_i \] 计算 \(1 \sim n\) 的排列中有多少是 Magic 的，答案可能很大，只能输出模 \(m\) 以后的值。

对于 \(100\%\) 的数据，\(1\le n \le 10^6,~1\le m \le 10^9\)，\(m\) 是一个质数。

给张图。

题目就是问 \(n\) 个结点的完全二叉树有多少种满足小根堆性质

设 \(f_i\) 表示以 \(i\) 为根的子树的答案， \(s_i\) 表示原树中以 \(i\) 为根的子树有多少个结点

考虑转移。根一定要放这个子树中最小的，其他的就挑 \(s_{2i}\) 个放左子树就好了，则 \[ f_i = f_{2i} \times f_{2i + 1} \times \dbinom{s_i-1}{s_{2i}} \] 因为没有保证 \(n<m\) ，因此考虑Lucas定理

时间复杂度 \(O(\epsilon n \log n)\)，\(\epsilon = \log_m{n}\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(1e6+15))

int n,mod,sz[N<<1],f[N<<1],fac[N];
int mul(int cnt, ...)
{
    va_list ptr; va_start(ptr,cnt);
    int res=1;
    for(int i=0; i<cnt; i++)
        res=res*va_arg(ptr,int)%mod;
    va_end(ptr);
    return res;
}
int qpow(int a,int b)
{
    int ans=1,base=a%mod;
    for(; b; b>>=1)
    {
        if(b&1) ans=ans*base%mod;
        base=base*base%mod;
    }
    return ans;
}
int C(int n,int m)
{
	if(n<m)return 0;
    return mul(3,fac[n], qpow(fac[m],mod-2), qpow(fac[n-m],mod-2));
}
int lucas(int n,int m)
{
	if(!m)return 1;
	return lucas(n/mod, m/mod) * C(n%mod, m%mod) % mod;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> mod; fac[0]=1;
    for(int i=1; i<=n; i++) fac[i] = fac[i-1] * i % mod;
    for(int i=1; i<=n; i++) sz[i]=1;
    for(int i=n; i>=2; i--) sz[i>>1] += sz[i];
    for(int i=n+1; i<=n*2+1; i++) f[i]=1;
    for(int i=n; i; i--) f[i] = mul(3, f[i<<1], f[i<<1|1], lucas(sz[i]-1,sz[i<<1]));
    cout << f[1] << '\n';
    return 0;
}