[洛谷P2606] ZJOI2010 排列计数

问题描述

称一个 (1 sim n) 的排列 (p_1,p_2, dots ,p_n) 是 Magic 的，当且仅当 (forall i in [2,n],p_i > p_{lfloor i/2 floor}) 。计算 (1 sim n) 的排列中有多少是 Magic 的，答案可能很大，只能输出模 (m) 以后的值。

输入格式

一行两个整数 n,m，含义如上所述。

输出格式

输出文件中仅包含一个整数，表示 (1sim n) 的排列中， Magic 排列的个数模 m 的值。

样例输入

20 23

样例输出

16

数据范围

对于 (100\%) 的数据，(1le n le 10^6),$ 1le m le 10^9(，)m$ 是一个质数。

解析

我们可以比较显然的将原问题转化为树上问题，即求一棵二叉树上，满足要求的拓扑序方案数。设 (f_u)表示节点 (u) 的子树中满足条件的方案，(s_u) 表示 (u) 的子树中的节点个数。我们可以将子树中的点先任意排列，然后将排列后的点按顺序分给每一棵子节点的子树，即 ((s_u-1)!prod_{v in u}f_v) 。但是这样会算重。重复的原因是分给每个子节点的点不需要考虑顺序。因此，我们有：

代码

#include <iostream>
#include <cstdio>
#define int long long
#define N 1000002
using namespace std;
int n,m,i,fac[N],inv[N],f[N],s[N];
int read()
{
	char c=getchar();
	int w=0;
	while(c<'0'||c>'9') c=getchar();
	while(c<='9'&&c>='0'){
		w=w*10+c-'0';
		c=getchar();
	}
	return w;
}
int poww(int a,int b)
{
	int ans=1,base=a;
	while(b){
		if(b&1) ans=ans*base%m;
		base=base*base%m;
		b>>=1;
	}
	return ans;
}
void dfs(int x)
{
	f[x]=fac[s[x]-1];
	if(x*2<=n) dfs(x*2),f[x]=f[x]*f[x*2]%m*inv[s[x*2]]%m;
	if(x*2+1<=n) dfs(x*2+1),f[x]=f[x]*f[x*2+1]%m*inv[s[x*2+1]]%m;
}
signed main()
{
	n=read();m=read();
	for(i=n;i>=1;i--){
		s[i]=1;
		if(i*2<=n) s[i]+=s[i*2];
		if(i*2+1<=n) s[i]+=s[i*2+1];
	}
	for(i=fac[0]=1;i<=n;i++) fac[i]=fac[i-1]*i%m;
	inv[n]=poww(fac[n],m-2);
	for(i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%m;
	dfs(1);
	printf("%lld
",f[1]);
	return 0;
}