首页 > 代码库 > BZOJ 2111 Perm 排列计数（满二叉树）

BZOJ 2111 Perm 排列计数（满二叉树）

2024-07-09 00:15:57   211人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=2111

题意：求1到n有多少种排列满足:A[i]>A[i/2](2<=i<=n)。

思路：形式类似二叉树。建模之后其实就是n个节点的不同的满二叉树有多少种？用f[i]表示i个节点的满二叉树个数，则f[n]=f[L]*f[R]*C(n-1,L)。其中L和R对于确定的n来说是确定的。比如n=10时，左右子树分别有6、3个点。

 

i64 a[N],n,p,f[N];void init(){    int i;    a[0]=1;    FOR1(i,N-1) a[i]=a[i-1]*i%p;}i64 exGcd(i64 a,i64 b,i64 &x,i64 &y){    if(b==0)    {        x=1;        y=0;        return a;    }    i64 temp=exGcd(b,a%b,x,y);    i64 t=x;    x=y;    y=t-a/b*y;    return temp;}i64 reverse(i64 a){    i64 x,y;    exGcd(a,p,x,y);    x=(x%p+p)%p;    return x;}i64 C(i64 n,i64 m){    return a[n]*reverse(a[m]*a[n-m]%p)%p;}int get(int x){    if(x==1) return 1;    int i;    for(i=1;;i++)    {        x-=(1<<i);        if(x<=(1<<(i+1)))        {            return (1<<i)-1+max(0,x-(1<<i));        }    }}int main(){    RD(n,p); init();    int i,L,R;    f[1]=1; f[2]=1;    for(i=3;i<=n;i++)    {        R=get(i-1);        L=i-1-R;        f[i]=f[L]*f[R]%p*C(i-1,L)%p;    }    PR(f[n]);}

 

 

 


联系
我们