• 周四. 4月 25th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

Perm 排列计数

admin

11月 28, 2021

题目描述

称一个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 ≤ 10^6, P ≤ 10^9,p是一个质数。 数据有所加强

‘ / ‘是向下取整,然后可以YY出一个小根堆,题意转化为求一个大小为n的二叉小根堆形态数。

f[i]=f[i<<1]*f[i<<1|1]*C(siz[i]-1,siz[i<<1])

n很大表不可打,p是质数用lucas()定理

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<cstring>
 5 #define MAXN 1000005
 6 #define ll long long
 7 #define reg register
 8 #define F(i,a,b) for(i=a;i<=b;++i)
 9 using namespace std;
10 ll e[MAXN],f[MAXN];
11 int p,siz[MAXN],n;
12 ll qpow(ll x,int b)
13 {
14     ll ans=1;
15     while(b>0)
16     {
17         if(b&1) ans=(ans*x)%p;
18         b>>=1;
19         x=(x*x)%p;
20     }
21     return ans;
22 }
23 ll C(int n,int m)
24 {
25     if(n<m) return 0;
26     return (e[n]*qpow(e[m],p-2)%p*qpow(e[n-m],p-2))%p;
27 }
28 ll Lucas(int n,int m)
29 {
30     if(!m) return 1;
31     return (C(n%p,m%p)*Lucas(n/p,m/p))%p;
32 }
33 int dfs(int k)
34 {
35     if(k>n) return 0;
36     siz[k]=1;
37     siz[k]+=dfs(k<<1);
38     siz[k]+=dfs(k<<1|1);
39     return siz[k];
40 }
41 int main()
42 {
43     reg int i;
44     scanf("%d%d",&n,&p);
45     e[0]=1;
46     F(i,1,n) e[i]=(e[i-1]*i)%p;
47     dfs(1);
48     for(i=n;i;--i) f[i]=((i<<1)>n?1:f[i<<1])*((i<<1|1)>n?1:f[i<<1|1])%p*Lucas(siz[i]-1,siz[i<<1])%p;
49     printf("%lld",f[1]);
50     return 0;
51 }

View Code

《Perm 排列计数》有一个想法
  1. I love your blog.. very nice colors & theme. Did you
    create this website yourself or did you hire someone
    to do it for you? Plz respond as I’m looking to create my
    own blog and would like to know where u got this from. appreciate it

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注