【BZOJ2111】[ZJOI2010]Perm 排列计数 组合数
组合 排列 计数
2023-09-11 14:15:27 时间
【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
Sample Output
16
HINT
100%的数据中,1 ≤ N ≤ 106, P ≤ 10^9,p是一个质数。
题解:题意可转化为:求n个节点能构成的完全二叉堆的个数。显然我们可以求出左右两棵子树的大小,然后分别递归下去即可。
细节有点多~
#include <cstdio> #include <cstring> #include <iostream> using namespace std; typedef long long ll; const int maxn=1000010; int m=1000000; ll n,p; ll jc[maxn],jcc[maxn],ine[maxn],f[maxn]; int Log[maxn]; ll C(ll a,ll b) { if(a<b) return 0; if(!b) return 1; if(a<p&&b<p) return jc[a]*jcc[b]%p*jcc[a-b]%p; return C(a%p,b%p)*C(a/p,b/p)%p; } ll calc(ll x) { if(f[x]) return f[x]; ll a=x-(1<<Log[x+1])+1; if(a<(1<<Log[x+1]-1)) a=(1<<Log[x+1]-1)-1+a; else a=(1<<Log[x+1])-1; return f[x]=C(x-1,a)*calc(a)%p*calc(x-a-1)%p; } int main() { scanf("%lld%lld",&n,&p); if(m>=p) m=p-1; ll i; jc[0]=jcc[0]=1,ine[0]=ine[1]=1; for(i=2;i<=m;i++) ine[i]=(p-(p/i)*ine[p%i]%p)%p; for(i=1;i<=m;i++) jc[i]=jc[i-1]*i%p,jcc[i]=jcc[i-1]*ine[i]%p; for(i=2;i<=n+1;i++) Log[i]=Log[i>>1]+1; f[0]=f[1]=1; printf("%lld",calc(n)); return 0; }
相关文章
- 石头剪刀布---组合数取模,数论
- Java实现 LeetCode 40 组合总和 II(二)
- (Java实现) 组合的输出
- Python的组合模式与责任链模式编程示例
- 【设计模式】组合实体模式
- 面向对象之继承和组合浅谈
- rxjs pipe和filter组合的一个实际例子的单步调试
- rxjs pipe和map组合的一个实际例子的单步调试
- rxjs pipe和filter组合的一个实际例子的单步调试
- ZZNUOJ_C语言1100:求组合数(函数专题)(完整代码)
- Database之SQL:SQL在线编程、工作中常用SQL代码实践之查询-SQL问题分析解决思路、高级案例SQL语法拆解(单技巧各自用法详细分类/多技巧组合用法)、经典组合案例实战之详细攻略
- DL之DNN:自定义MultiLayerNet【6*100+ReLU,SGD】对MNIST数据集训练进而比较【多个超参数组合最优化】性能
- SVM与基于马氏距离的径向基函数(MDRBF)核结合组合(Matlab代码实现)
- 风电的Weibull分布及光电的Beta分布组合研究(Matlab代码实现)
- tf.group()用于组合多个操作
- Python对5支股票的投资组合进行分析
- python 设计模式之组合模式Composite Pattern
- leetcode 39. 组合总和 js实现
- Java 实现组合(Composite)模式
- 组合逻辑块的测试平台