先上题概

Perm 排列计数

 

 

 

题目描述

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

 

输入格式

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

 

输出格式

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

 

样例

样例输入

20 23

样例输出

16

 

数据范围与提示

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

    主要意思就是在   1-n的序列里找到P(i)>P(i/2)

 

  可以想到二叉堆满足   父亲比儿子优的性质   所以即维护小根堆从root到叶子的路满足一个magic序列   （1）首先是DP   因为儿子之间是可以交换的   所以有不同的二叉树   DP即是求二叉树的种数   dp[i]=dp[i*2]*dp[i*2+1]*C(size[i]-1,size[left])

    始终没有理解式子
    其实
    这样一个小根堆的size，形状都是相对确定的
    根据乘法原理
    有两个儿子相乘
    另外，考虑两个儿子树中的任意节点可交换
    因此有*C(size[i]-1,size[left])

（2）可以看到   1 ≤ ??? N ≤ 106, P??? ≤ 10^9   这样的数据范围   需要有lucas   博主因实力太菜   实际上花了半天在调lucas   lucas戳这里     最后  

 1 #include<iostream>
 2 #include<cstdio>
 3 #define ll long long
 4 #define MAXN 2000010
 5 using namespace std;
 6 int n;
 7 ll p;
 8 ll jc[MAXN];
 9 ll dp[MAXN];
10 int size[MAXN];
11 ll pow(ll a,ll b){
12     ll ans=1;
13     while(b){
14         if(b&1)ans=(ans*a)%p;
15         a=(a*a)%p;
16         b>>=1;
17     }
18     return ans%p;
19 }
20 ll C(int a,int b){
21     if(a<b)return 0;
22     if(b==0)return 1;
23     return jc[a]*pow(jc[a-b]*jc[b]%p,p-2)%p;
24 }
25 ll lucas(int a,int b){
26     if(b>a)return 0;
27     if(b==0)return 1;
28     if(a>p||b>p)return C(a%p,b%p)*lucas(a/p,b/p)%p;
29     return C(a,b)%p;
30 }
31 void dfs(ll u){
32     if(u>n){
33         dp[u]=1;
34         return ;
35     }
36     dfs(u<<1);
37     dfs(u<<1|1);
38     size[u]=size[u<<1]+size[u<<1|1]+1;
39     dp[u]=dp[u<<1]*dp[u<<1|1]%p*lucas(size[u]-1,size[u<<1])%p;
40     return ;
41 }
42 int main(){
43     scanf("%d%lld",&n,&p);
44     jc[0]=1;
45     for(int i=1;i<=n;++i)jc[i]=jc[i-1]*1ll*i%p;
46     dfs(1);
47     printf("%lld\n",dp[1]%p);
48 }

View Code

 

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #define ll long long
 4 #define MAXN 2000010
 5 using namespace std;
 6 int n;
 7 ll p;
 8 ll jc[MAXN];
 9 ll dp[MAXN];
10 int size[MAXN];
11 ll pow(ll a,ll b){
12     ll ans=1;
13     while(b){
14         if(b&1)ans=(ans*a)%p;
15         a=(a*a)%p;
16         b>>=1;
17     }
18     return ans%p;
19 }
20 ll C(int a,int b){
21     if(a<b)return 0;
22     if(b==0)return 1;
23     return jc[a]*pow(jc[a-b]*jc[b]%p,p-2)%p;
24 }
25 ll lucas(int a,int b){
26     if(b>a)return 0;
27     if(b==0)return 1;
28     if(a>p||b>p)return C(a%p,b%p)*lucas(a/p,b/p)%p;
29     return C(a,b)%p;
30 }
31 void dfs(ll u){
32     if(u>n){
33         dp[u]=1;
34         return ;
35     }
36     dfs(u<<1);
37     dfs(u<<1|1);
38     size[u]=size[u<<1]+size[u<<1|1]+1;
39     dp[u]=dp[u<<1]*dp[u<<1|1]%p*lucas(size[u]-1,size[u<<1])%p;
40     return ;
41 }
42 int main(){
43     scanf("%d%lld",&n,&p);
44     jc[0]=1;
45     for(int i=1;i<=n;++i)jc[i]=jc[i-1]*1ll*i%p;
46     dfs(1);
47     printf("%lld\n",dp[1]%p);
48 }