1282: 排列计数 perm

题目描述

称一个$1,2,...,N$的排列$P_1,P_2...,P_n$是$Magic$的，当且仅当$2<=i<=N$时，$P_i>P_{i/2}$. 计算$1，2，...N$的排列中有多少是$Magic$的，答案可能很大，只能输出模$P$以后的值
$1\le N\le 10^6,P\le 10^9$

题解

可以转化成小根堆，$x$的左右儿子为$2x$和$2x+1$
考虑$dp$，设$f_i$表示以$i$为根，用$1$到$siz{e}_i$来填充且合法的方案数
容易得到根最小，所以要从$siz{e}_i-1$个数中选出$siz{e}_{2i}$个数给左儿子，所以可以得到转移式子：$f_i=C_{siz{e}_i-1}^{siz{e}_{2i}}\ast f_{2i}\ast f_{2i+1}$
上代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,f[N],jc[N],ny[N],p,sz[N];
int K(int x,int y){
int A=1;while(y){
if (y&1) A=1ll*A*x%p;
x=1ll*x*x%p;y>>=1;
}return A;
}
int C(int x,int y){
return 1ll*jc[x]*ny[y]%p*ny[x-y]%p;
}
void dfs(int x){
sz[x]=1;int l=x<<1,r=l|1;
if (l<=n) dfs(l),sz[x]+=sz[l];
if (r<=n) dfs(r),sz[x]+=sz[r];
if (sz[x]<3){f[x]=1;return;}
f[x]=1ll*C(sz[x]-1,sz[l])*f[l]%p*f[r]%p;
}
int main(){
scanf("%d%d",&n,&p);
jc[0]=1;for (int i=1;i<=n;i++) jc[i]=1ll*i*jc[i-1]%p;
ny[n]=K(jc[n],p-2);for (int i=n;i;i--) ny[i-1]=1ll*i*ny[i]%p;
dfs(1);printf("%dn",f[1]);
return 0;
}

最后

以上就是感动烤鸡为你收集整理的1282: 排列计数 perm的全部内容，希望文章能够帮你解决1282: 排列计数 perm所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。