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;
}