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