首页 > 代码库 > BZOJ 2111 Perm 排列计数(满二叉树)
BZOJ 2111 Perm 排列计数(满二叉树)
题目链接: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]);}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。