问题描述

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

输入格式

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

输出格式

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

样例输入

20 23

样例输出

16

数据范围

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

解析

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

\[f[u]=\frac{(s_u-1)!\prod_{v\in u}f_v}{\prod_{v\in u}s_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\n",f[1]);
	return 0;
}