2111: [ZJOI2010]Perm 排列计数
Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 1936 Solved: 477
[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的值。
100%的数据中，1 ≤ ��� N ≤ 106, P��� ≤ 10^9，p是一个质数。 数据有所加强
该死傻逼题
这是个堆
模型和卡特兰数算二叉树形态数很像，只不过这个左右孩子固定了
然后算就行了，需要乘组合数
然后n>p，组合数要除阶乘，阶乘可能是p的倍数，没有逆元.....
我一开始以为不用Lucas也行，一直WA然后想了一下应该用Lucas，因为m<P的时候m!就有逆元了，剩下的系数还是用贡献的
然后改了Lucas还是一直WA....
无奈参考PoPoQQQ改了一下递推就过了.....
该死 我要去吃饭了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=1e6+;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,P;
ll fac[N];
ll Pow(ll a,int b,int P){
ll re=;
for(;b;b>>=,a=a*a%P)
if(b&) re=re*a%P;
return re;
}
void iniFac(int n){
fac[]=;
for(int i=;i<=n;i++) fac[i]=fac[i-]*i%P;
}
ll C(int n,int m){
return fac[n]*Pow(fac[m]*fac[n-m]%P,P-,P)%P;
}
ll Lucas(int n,int m){
if(n<m) return ;
ll re=;
for(;m;m/=P,n/=P) re=re*C(n%P,m%P)%P;
return re;
}
int size[N<<];
ll f[N<<];
void dp(){
for(int i=n;i>=;i--){
int l=i<<,r=i<<|;
size[i]=size[l]+size[r]+;
f[i]=Lucas(size[i]-,size[l])*(l>n?:f[l])%P*(r>n?:f[r])%P;
}
printf("%lld",f[]);
}
int main(){
freopen("in","r",stdin);
n=read();P=read();
iniFac(n);
dp();
}