[ZJOI2010]Perm

[ZJOI2010]Perm

题目

称一个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

OUTPUT

16

解题报告

这竟然是一道树规= =

其实想明白之后挺简单的

我们考虑一颗满二叉树,一个节点$i$如果有左儿子,那么它的左儿子编号一定为$i\times 2$,如果它有右儿子,那么它的右儿子编号一定为$i\times 2+1$

再回来看这道题,假如我们建一颗满二叉树,那么问题不就转化成所有儿子的权值都比父亲的权值大的方案数么?

设$f[size[i]]$代表编号为$i$的节点的方案数

我们要取出$i-1$个(把自己去掉)比它大的数,一部分放在左子树,一部分放在右子树,且当左子树确定了取出哪些数时,右子树所取出的数也是一定的

故我们可以推出状态转移方程:

$$f[size[i]]=C_{size[i]-1}^{size[i<<1]}\times f[size[i<<1]]\times f[size[i<<1|1]]$$

然后实现即可

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 typedef long long L;
 6 L n,p;
 7 L fac[1000005];
 8 inline L po(L x,L hm){
 9     L ret(1);
10     while(hm){
11         if(hm&1)
12             ret=ret*x%p;
13         x=x*x%p;
14         hm>>=1;
15     }
16     return ret;
17 }
18 inline L C(int n,int m){
19     return fac[n]*po(fac[m],p-2)%p*po(fac[n-m],p-2)%p;
20 }
21 struct edge{
22     int e;
23     edge *n;
24 }a[1000005],*pre[1000005];
25 int tot;
26 inline void insert(int s,int e){
27     a[++tot].e=e;
28     a[tot].n=pre[s];
29     pre[s]=&a[tot];
30 }
31 int size[2000005];
32 inline void get_size(int u){
33     size[u]=1;
34     for(edge *i=pre[u];i;i=i->n){
35         int e(i->e);
36         if(!size[e]){
37             get_size(e);
38             size[u]+=size[e];
39         }
40     }
41 }
42 L f[2000005];
43 inline void dfs(int u){
44     if(u>n){
45 //      size[u]=0;
46 //      f[0]=1;
47         return;
48     }
49 //  cout<<u<<endl;
50 //  size[u]=1;
51     dfs(u<<1);
52 //  size[u]+=size[u<<1];
53     dfs(u<<1|1);
54 //  size[u]+=size[u<<1|1];
55     f[size[u]]=C(size[u]-1,size[u<<1])*f[size[u<<1]]%p*f[size[u<<1|1]]%p;
56 }
57 inline int gg(){
58 //  freopen("permzj.in","r",stdin);
59 //  freopen("permzj.out","w",stdout);
60     scanf("%lld%lld",&n,&p);
61     fac[0]=fac[1]=1;
62     for(int i=2;i<=n;++i){
63         L tmp(i);
64         while(tmp%p==0)
65             tmp/=p;
66         fac[i]=fac[i-1]*tmp%p;
67     }
68     for(int i=1;i<=n;++i){
69         if((i<<1)>n)
70             break;
71         insert(i,i<<1);
72         if((i<<1|1)>n)
73             break;
74         insert(i,i<<1|1);
75     }
76     get_size(1);
77     f[0]=f[1]=1;
78     dfs(1);
79     printf("%lld",f[n]%p);
80 //  for(int i=1;i<=n;++i)
81 //      cout<<"i="<<i<<" size[i]="<<size[i]<<endl;
82     return 0;
83 }
84 int K(gg());
85 int main(){;}

时间: 09-07

[ZJOI2010]Perm的相关文章

【BZOJ2111】[ZJOI2010]Perm 排列计数 组合数

[BZOJ2111][ZJOI2010]Perm 排列计数 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

【bzoj2111】[ZJOI2010]Perm 排列计数 dp+Lucas定理

题目描述 称一个1,2,...,N的排列P1,P2...,Pn是Mogic的,当且仅当2<=i<=N时,Pi>Pi/2. 计算1,2,...N的排列中有多少是Mogic的,答案可能很大,只能输出模P以后的值 输入 输入文件的第一行包含两个整数 n和p,含义如上所述. 输出 输出文件中仅包含一个整数,表示计算1,2,?, n的排列中, Mogic排列的个数模 p的值. 样例输入 20 23 样例输出 16 题解 dp+Lucas定理 题目显然小根堆,考虑怎么求以一个节点为根的方案数.根肯定

bzoj2111【ZJOI2010】Perm 排列计数

2111: [ZJOI2010]Perm 排列计数 Time Limit: 10 Sec  Memory Limit: 259 MB Submit: 1548  Solved: 321 [Submit][Status][Discuss] Description 称一个1,2,...,N的排列P1,P2...,Pn是Magic的,当且仅当2<=i<=N时,Pi>Pi/2. 计算1,2,...N的排列中有多少是Magic的,答案可能非常大,仅仅能输出模P以后的值 Input 输入文件的第一行

东北育才10天大总结

老师们 Scanf的嗓门照例是最大的.恩. “我是山里的孩子……小的时候背书,整个山头都听得见……” 有一个哈师大附中的竞赛教练很……怎么说呢?接地气好了. Scanf说东北人很耿直,似乎确实是这样的.衡水的教练早就被遣返了…… “他啊,监考去了!” 虽然他不在,但还是不还手机.让衡水的人天天在电脑上颓废…… Scanf不在,你看我们就很老实.他到处“乱”玩,甚至跑到了国境线边,连火车票都忘了买,坐高铁去,乘绿皮火车回,路过长白山就去玩了一趟,结果暴风雪逼得他去吃“暴辣”的烤鱿鱼. “我看<三八

bzoj1834: [ZJOI2010]network 网络扩容

努力看了很久样例一直过不了...然后各种输出中间过程啊巴拉巴拉弄了1h,没办法了...然后突然想到啊原来的边可以用啊为什么不用...于是A了...感人肺腑 #include<cstdio> #include<cstring> #include<queue> #include<iostream> #include<algorithm> using namespace std; #define rep(i,n) for(int i=1;i<=n

全排列问题的递归算法(Perm)

[题目]设计一个递归算法生成n个元素{r1,r2,-,rn}的全排列. [算法讲解] 设R={r1,r2,-,rn}是要进行排列的n个元素,Ri=R-{ri}.集合X中元素的全排列记为perm(X).(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列.R的全排列可归纳定义如下: 当n=1时,perm(R)=(r),其中r是集合R中唯一的元素:当n>1时,perm(R)由(r1)perm(R1),(r2)perm(R2),-,(rn)perm(Rn)构成.实现思想:将

1833: [ZJOI2010]count 数字计数

1833: [ZJOI2010]count 数字计数 Time Limit: 3 Sec  Memory Limit: 64 MBSubmit: 2951  Solved: 1307[Submit][Status][Discuss] Description 给定两个正整数a和b,求在[a,b]中的所有整数中,每个数码(digit)各出现了多少次. Input 输入文件中仅包含一行两个整数a.b,含义如上所述. Output 输出文件中包含一行10个整数,分别表示0-9在[a,b]中出现了多少次.

BZOJ_1833_[ZJOI2010]_数字计数_(数位dp)

描述 http://www.lydsy.com/JudgeOnline/problem.php?id=1833 统计\(a~b\)中数字\(0,1,2,...,9\)分别出现了多少次. 分析 数位dp真是细节又多又容易出错,我都懒得看题解,所以也就懒得写题解了... 注意细节吧还是... 1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long ll; 5 ll a,b; 6 ll A[10],B[10],n

[BZOJ1072][SCOI2007]排列perm 状压dp

1072: [SCOI2007]排列perm Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 2488  Solved: 1546[Submit][Status][Discuss] Description 给一个数字串s和正整数d, 统计s有多少种不同的排列能被d整除(可以有前导0).例如123434有90种排列能被2整除,其中末位为2的有30种,末位为4的有60种. Input 输入第一行是一个整数T,表示测试数据的个数,以下每行一组s和d,中间

【BZOJ1835】[ZJOI2010]base 基站选址 线段树+DP

[BZOJ1835][ZJOI2010]base 基站选址 Description 有N个村庄坐落在一条直线上,第i(i>1)个村庄距离第1个村庄的距离为Di.需要在这些村庄中建立不超过K个通讯基站,在第i个村庄建立基站的费用为Ci.如果在距离第i个村庄不超过Si的范围内建立了一个通讯基站,那么就成它被覆盖了.如果第i个村庄没有被覆盖,则需要向他们补偿,费用为Wi.现在的问题是,选择基站的位置,使得总费用最小. 输入数据 (base.in) 输入文件的第一行包含两个整数N,K,含义如上所述. 第