BZOJ 2111([ZJOI2010]Perm 排列计数-乘法逆元+完全二叉树模型+数列分数表示法)

2111: [ZJOI2010]Perm 排列计数

Time Limit: 10 Sec   Memory Limit: 259 MB

Submit: 478  

Solved: 283

[​​Submit​​][​​Status​​][​​Discuss​​]

Description

称一个1,2,...,N的排列P1,P2...,Pn是Magic的，当且仅当2<=i<=N时，Pi>Pi/2. 计算1，2，...N的排列中有多少是Magic的，答案可能很大，只能输出模P以后的值

Input

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

Output

输出文件中仅包含一个整数，表示计算1,2,⋯, �的排列中， Magic排列的个数模 p的值。

Sample Input

20 23

Sample Output

16

HINT

100%的数据中，1 ≤ � N ≤ 106, P� ≤ 10^9，p是一个质数。

显然可以把这题看成-有n个节点的完全二叉树（小根堆性质）的排列数。

那就把最小的那个拎出来，其它的点随便塞入2边（不影响结果）。

接下来就是把答案分解成分数，乘法逆元啥的。。。

lyd的 ​​题解​​

#include<cstdio>
#include<cmath>
#include<functional>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN (1000000+1)
#define eps (1e-9)
int n,F;
int exgcd(int a,int b,long long &x,long long &y){if (!b) {x=1,y=0;return a;}int ans=exgcd(b,a%b,x,y);long long z=x;x=y;y=z-(a/b)*y;return ans;}
long long f[MAXN],g[MAXN],jc[MAXN];
long long mulinv(int b)
{
  long long x,y;
  exgcd(b,F,x,y);
//  return ((-x)/F*F+F+x)%F;
  return (x+abs(x)/F*F+F)%F;
}
int main()
{
  scanf("%d%d",&n,&F);
  f[0]=g[0]=f[1]=g[1]=1%F;
  jc[0]=jc[1]=1;
  for (int i=2;i<=n;i++) jc[i]=jc[i-1]*i%F;  
  for(int i=2;i<=n;i++)
  {
    int dep=(int)(log(i)/log(2)+eps)+1;
    int l=(int)pow(2.0,dep-2)-1;
//    cout<<l<<' '<<(int)(eps+pow(2.0,dep-2))<<' '<<(i-1-2*l)<<' ';
    l+=min((i-1-2*l),(int)(eps+pow(2.0,dep-2)));
    int r=i-l-1;
//    cout<<i<<' '<<dep<<' '<<l<<' '<<r<<' '<<f[l]<<' '<<f[r]<<endl;
    f[i]=f[l]*f[r]%F*jc[i-1]%F;
    g[i]=g[l]*g[r]%F*jc[l]%F*jc[r]%F;
  }
//  cout<<f[n]<<' '<<g[n]<<endl;
  cout<<f[n]*mulinv(g[n])%F<<endl;
  return 0;
}