记录编号	460739	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2010] 排列计数	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	1.209 s
提交时间	2017-10-18 09:35:15	内存使用	23.20 MiB

#include<cstdio>
#include<iostream>
const int maxn=1e6+5;
using namespace std;
inline long long get();
inline long long C(long long N,long long M);
inline long long pow(long long ans,long long mi);
long long lucas(long long N,long long M);
long long exgcd(long long a,long long b,long long &x,long long &y);
long long n,p,x,y;
long long f[maxn],size[2*maxn];
int main()
{
	freopen("permzj.in","r",stdin);
	freopen("permzj.out","w",stdout);
	n=get(),p=get();
	for(long long i=n;i;i--)
	{
		size[i]=1+size[2*i]+size[2*i+1];
		f[i]=lucas(size[i]-1,size[i*2])%p;
		if(i*2<=n)f[i]=f[i]*f[i*2]%p;
		if(i*2+1<=n)f[i]=f[i]*f[2*i+1]%p;		
	}
	printf("%lld\n",f[1]);
	return 0;
}
long long pow(long long ans,long long mi)
{
	long long re=1;
	while(mi)
	{
		if(mi%2)
		{
			re=re*ans%p;
			mi--;
		}
		ans=ans*ans%p;
		mi>>=1;
	}
	return re;
}
long long lucas(long long N,long long M)
{
	if(!M)return 1;
	return C(N%p,M%p)*lucas(N/p,M/p)%p;
}
inline long long C(long long N,long long M)
{
	if(M>N-M)M=N-M;
	long long a=1,b=1;
	for(long long i=0;i<M;i++)
	{
		a=a*(N-i)%p;
		b=b*(i+1)%p;
	}
	exgcd(b,p,x,y);
	if(x<0)x+=p;
	else x%=p;
	return a*pow(b,p-2)%p;
}
long long exgcd(long long a,long long b,long long &x,long long &y)
{
	if(!b)
	{
		x=1,y=0;
		return a;
	}
	long long r=exgcd(b,a%b,x,y);
	long long t=x;
	x=y;
	y=t-a/b*y;
	return r;
}
inline long long get()
{
	long long t=0;char c=getchar(),j=1;
	while(!isdigit(c))
		if(c=='-')j=-1,c=getchar();
		else c=getchar();
	while(isdigit(c))
		t=(t<<3)+(t<<1)+c-'0',
		c=getchar();
	return j*t;
}