●洛谷P2606 [ZJOI2010]排列计数
2024-10-12 07:38:47
题链:
https://www.luogu.org/problemnew/show/P2606
题解:
组合数(DP),Lucas定理
首先应该容易看出,这个排列其实是一个小顶堆。
然后我们可以考虑dp:
令F[i]为小顶堆的i号节点那棵子树的方案数:
F[i]=F[i*2]*F[i*2+1]*C(size[i]-1,size[i*2])
含义就是左儿子的方案数*右儿子的方案数*当前i节点取走最小的那个值后分size[i*2]个数给左儿子的方案数。
(BZOJ上数据加强,可能会N>P,所以如果直接预处理阶乘和阶乘逆元可能会导致出现很多不该出现的0,所以这里考虑用Lucas定理)
代码:
#include<bits/stdc++.h>
#define MAXN 1000006
using namespace std;
int N,P,ANS=1;
int size[MAXN],fac[MAXN],inv[MAXN];
int fastpow(int a,int b){
int ret=1;
if(a==0) return 1;
for(;b;a=1ll*a*a%P,b>>=1)
if(b&1) ret=1ll*ret*a%P;
return ret;
}
void prepare(int m){
fac[0]=inv[0]=1;
for(int i=1;i<=m;i++) fac[i]=1ll*fac[i-1]*i%P;
inv[m]=fastpow(fac[m],P-2);
for(int i=m-1;i>=1;i--) inv[i]=1ll*inv[i+1]*(i+1)%P;
}
int C(int m,int n){
int ret=1,nn,mm;
while(m&&n){
mm=m%P; nn=n%P; m/=P; m/=P;
if(mm<nn) return 0;
ret=1ll*ret*fac[mm]%P*inv[nn]%P*inv[mm-nn]%P;
}
return ret;
}
int main(){
scanf("%d%d",&N,&P);
prepare(min(N,P-1));
for(int i=N;i>=1;i--) size[i]++,size[i/2]+=size[i];
for(int i=1;i<=N;i++) if(i*2<=N)
ANS=1ll*ANS*C(size[i]-1,size[i*2])%P;
printf("%d\n",ANS);
return 0;
}
最新文章
- 调试使用windows堆程序遇到的问题
- [hadoop] 一些基础概念
- Intersection of Two Linked Lists | LeetCode
- iOS开发 字符串添加行间距
- C语言signal处理的小例子
- guid 新建
- TCP协议状态简介
- iOS 天气应用代码中文介绍
- Windows下FFmpeg快速入门 <;第二篇>;
- python学习day2(一)
- 查看内存数据的函数(ByteToHex和ByteToBin,最终都变成String)
- Python垃圾回收机制 总结
- UVA - 11624 多点bfs [kuangbin带你飞]专题一
- 关于JSON字符串的处理与总结 【原创】
- WPF使用第三方字体(TTF字体)
- Largest Rectangle in a Histogram POJ - 2559 (单调栈)
- 洛谷 P1691 有重复元素的排列问题 解题报告
- node微信公众号开发---域名绑定
- Intellij IDEA去除@Autowired下划线红色提示
- windows下用python转换markdown到html