输出文件中仅包含一个整数，表示计算1,2,?, ???的排列中， Magic排列的个数模 p的值。
样例：
样例输入：
20 23
样例输出：
16
数据范围与提示：
100%的数据中，1≤???N ≤ 106,P???≤109，p是一个质数。 数据有所加强
题解：
来介绍两种做法：
1.递推+组合数学：
前缀知识：
1）组合数学入门。
2）Lucas定理。
网上有好多人管这个叫DP，个人感觉不是DP，可能是一开始有一个叫它DP，于是好多半瓶子醋的就也叫它DP了叭～
首先，看到这道题我就想到这是一个小跟堆。
你去想想，小跟堆是一个完全二叉树，所以每一个节点i的两个儿子分别是i>>1和i>>1|1，所以P[i/2]其实就是P[i]的父亲，然后又因为P[i/2]<P[i]，所以这就是一个小跟堆啦～
那么问题就转化为，求这n个数所能组成的小跟堆的数量。
然后我们定义DP[i]表示i这个点为跟节点的方案数。
对于没一个点的方案数，显然只能从他的两个儿子转移过来，即为：DP[i]=DP[i>>1]×DP[i>>1|1]。
但是显然答案不能直接这样的来，因为每个点i的两个子树中的数可以不一样，所以会漏掉答案。
所以我们就要融入一些组合数学的问题了。
因为只是交换两棵子树之间的数，每棵子树的size是不变的，所以我们就相当于是要乘上在size[ls]+size[rs]当中取size[ls]个数的方案数。
于是式子变为了：DP[i]=DP[i>>1]×DP[i>>1|1]×C(size[i]-1,size[i>>1])。
注意P是一个小的质数，所以考虑Lucas求组合数。
2.拓扑排序：
偶然间发现这道题就是在求一棵树的拓扑排序的数量（笔者正在证明）。
直接套用公式：ans=n!/∏(1≤i≤n)s[i]。
接着就是推式子。
DP[u]=[(size[u]-1)!×∏DP[v] ]/∏size[v]（其中，v为u的儿子）。
接着定义g[u]=DP[u]/size[u]!=∏g[v]/size[u]=1/∏size[k]（其中，k为u字数上的点）。
所以g[1]=1/∏(1≤i≤n)size[i]。
所以答案即为：ans=DP[1]=g[1]×size[1]!=n!/∏(1≤i≤n)size[i]。
但是注意数据加强之后可能会挂。
代码时刻：
解法1：
#include<bits/stdc++.h>
using namespace std;
long long n,p;
long long jc[1000001],qsm[1000001],dp[1000001],size[1000001];
long long qpow(long long x,long long y)
{
long long ans=1;
while(y)
{
if(y%2)ans=(ans*x)%p;
y>>=1;
x=(x*x)%p;
}
return ans;
}
void pre_work()
{
jc[0]=1;
for(long long i=1;i<=n;i++)
jc[i]=(jc[i-1]*i)%p;
for(long long i=0;i<=n;i++)
qsm[i]=qpow(jc[i],p-2)%p;
}
long long get_C(long long x,long long y){return ((jc[x]*qsm[y])%p*qsm[x-y])%p;}
long long lucas(long long x,long long y)
{
if(!y)return 1;
return (get_C(x%p,y%p)*lucas(x/p,y/p))%p;
}
int main()
{
scanf("%lld%lld",&n,&p);
pre_work();
for(long long i=n;i>0;i--)
{
if((i<<1)>n&&(i<<1|1)>n)
{
dp[i]=1;
size[i]=1;
continue;
}
if((i<<1|1)>n)
{
dp[i]=1;
size[i]=2;
continue;
}
size[i]=size[i<<1]+size[i<<1|1]+1;
dp[i]=lucas(size[i]-1,size[i<<1]);
if((i<<1)<=n)dp[i]=(dp[i]*dp[i<<1])%p;
if((i<<1|1)<=n)dp[i]=(dp[i]*dp[i<<1|1])%p;
}
cout<<dp[1]<<endl;
return 0;
}
解法2：
#include<bits/stdc++.h>
using namespace std;
long long n,p;
long long s[1000005],inv[1000005];
long long ans=1;
int main()
{
scanf("%lld%lld",&n,&p);
inv[1]=inv[0]=1;
for(int i=1;i<=n;i++)s[i]=1;
for(int i=n;i>=2;i--)s[i>>1]+=s[i];
for(int i=2;i<=n;i++)inv[i]=(p-p/i)*inv[p%i]%p;
for(int i=1;i<=n;i++)ans=ans*i%p*inv[s[i]]%p;
printf("%lld",ans);
return 0;
}
rp++
完善中……