「ZJOI 2010」 排列计数

题目链接

戳我

(Solution)

其实我们可以发现这题等价于让你求：

用(1)~(n)的数组成一个完全二叉树使之满足小根堆性质的方案数

于是我们可以考虑(dp)

假设我们现在在(i)点,(i)的子节点个数为(s[i])(包括自己)

则：

(dp[i]=C(s[i]-1,s[i*2])*f[i*2]*f[i*2+1])

(ps:)
因为是二叉树所以(i*2)和(i*2+1)为(i)的两个儿子

这个式子很容易看懂吧。

在子节点中选一些填入左儿子,一些填入右儿子,右儿子和左儿子都要满足小根堆的性质

(Code)

#include<bits/stdc++.h>
#define rg register
#define int long long
using namespace std;
int read() {
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
    while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
    return f*x;
}
int f[1000001],s[2000011],dp[2000011];
int ksm(int a,int b,int p){
    int ans=1;
    while(b){  
        if(b&1) ans=ans*a%p;  
        a=a*a%p,b>>=1;
    }
    return ans;
}
int c(int n,int m,int p){return f[n]*ksm(f[m]*f[n-m]%p,p-2,p)%p;}
int lucas(int n,int m,int p){ return m?c(n%p,m%p,p)*lucas(n/p,m/p,p)%p:1; }
main(){
    int p,n;
    cin>>n>>p,f[0]=1;
    for(int i=1;i<=n;i++) f[i]=f[i-1]*i%p;
    for(int i=1;i<=n;i++) s[i]=1;
    for(int i=n;i>=2;i--) s[i>>1]+=s[i];
    for(int i=n+1;i<=n*2+1;i++) dp[i]=1;
    for(int i=n;i>=1;i--)
        dp[i]=lucas(s[i]-1,s[i*2],p)%p*dp[i*2]%p*dp[i*2+1]%p;
    cout<<dp[1];
}