bzoj2111 [ZJOI2010]排列计数

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

HINT

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

正解：树形$dp$+组合数学。

$ZJ$水题合集。。

可以发现，这是一棵二叉树(其实就是线段树的结构)，$x$的儿子是$x*2$和$x*2+1$。

于是设$f[i]$表示以$i$为根的子树中，以$1$到$size[i]$为排列的合法方案数。

那么转移方程还是很显然的，$f[i]=f[ls[i]]*f[rs[i]]*inom{sz[i]-1}{sz[ls[i]]}$。

因为$i$上面的数一定是$1$，所以我们可以在$sz[i]-1$个数中任选$sz[ls[i]]$个数到$ls$上，其他数放到$rs$上。

如果$i$只有左儿子，那么$f[i]=f[ls[i]]$；如果$i$是叶子，那么$f[i]=1$。

注意$p$可能比$n$小，所以$inom{i}{j}$中可能有$p$的倍数，要用$lucas$定理求组合数。

 1 #include <bits/stdc++.h>
 2 #define il inline
 3 #define RG register
 4 #define ll long long
 5 #define N (5000010)
 6 #define ls (x<<1)
 7 #define rs (x<<1|1)
 8 
 9 using namespace std;
10 
11 int f[N],sz[N],fac[N],ifac[N],inv[N],n,p;
12 
13 il int gi(){
14   RG int x=0,q=1; RG char ch=getchar();
15   while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
16   if (ch=='-') q=-1,ch=getchar();
17   while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
18   return q*x;
19 }
20 
21 il void pre(){
22   fac[0]=fac[1]=ifac[0]=ifac[1]=inv[1]=1;
23   for (RG int i=2;i<=n;++i){
24     inv[i]=1LL*(p-p/i)*inv[p%i]%p;
25     fac[i]=1LL*fac[i-1]*i%p;
26     ifac[i]=1LL*ifac[i-1]*inv[i]%p;
27   }
28   return;
29 }
30 
31 il int c(RG int n,RG int m){
32   if (n<m) return 0;
33   return 1LL*fac[n]*ifac[m]%p*ifac[n-m]%p;
34 }
35 
36 il int lucas(RG int n,RG int m){
37   if (!m) return 1; RG int res=c(n%p,m%p);
38   if (!res) return 0;
39   return 1LL*res*lucas(n/p,m/p);
40 }
41 
42 il void dfs(RG int x){
43   if (ls<=n) dfs(ls); if (rs<=n) dfs(rs);
44   sz[x]=sz[ls]+sz[rs]+1;
45   if (ls>n){ f[x]=1; return; }
46   if (rs>n){ f[x]=f[ls]; return; }
47   f[x]=1LL*f[ls]*f[rs]%p*lucas(sz[x]-1,sz[ls])%p;
48   return;
49 }
50 
51 int main(){
52 #ifndef ONLINE_JUDGE
53   freopen("perm.in","r",stdin);
54   freopen("perm.out","w",stdout);
55 #endif
56   n=gi(),p=gi(),pre(),dfs(1);
57   cout<<f[1]; return 0;
58 }