题目描述
称一个1,2,...,N的排列P1,P2...,Pn是Magic的，当且仅当2<=i<=N时，Pi>Pi/2. 计算1，2，...N的排列中有多少是Magic的，答案可能很大，只能输出模P以后的值
输入输出格式
输入格式：
输入文件的第一行包含两个整数 n和p，含义如上所述。
输出格式：
输出文件中仅包含一个整数，表示计算1,2,⋯, ���的排列中， Magic排列的个数模 p的值。
输入输出样例
输入样例#1：
20 23
输出样例#1：
16
说明
100%的数据中，1 ≤N ≤ 10^6, P≤ 10^9，p是一个质数。
画图发现树的形状是唯一的
且对于一个子树的根，一定小于所有子树节点
也就是说，对于一个根节点，只要考虑给左右子树划分的方案
可以列出dp方程:
f[i]=f[2*i]*f[2*i+1]*C(size[2*i],size[2*i+1]+size[2*i])
这题据说n会大于p，也就是说1～n会含有p
那么就不能线性求逆元
统计出i!中p出现的次数num[i]和不算p的倍数的阶乘fac[i]
算组合数时，如果num[y]-num[x]-num[y-x]不为0直接返回0
逆元直接把fac[]带入拓展欧几里德，因为在算fac时排除了p，所以可行
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long lol;
lol f[],size[],p,num[],fac[],n;
lol exgcd(lol a,lol b,lol &x,lol &y)
{
if (b==)
{
x=;y=;
return a;
}
lol d=exgcd(b,a%b,x,y);
lol t=x;x=y;y=t-(a/b)*y;
return d;
}
lol reverse(lol a)
{
lol x,y;
exgcd(a,p,x,y);
return (x%p+p)%p;
}
lol C(int x,int y)
{
lol ap=num[y],bp=num[x],cp=num[y-x];
if (ap-bp-cp) return ;
lol s=(fac[y]*reverse(fac[x])%p)*reverse(fac[y-x])%p;
return s;
}
void dfs_dp(int x)
{
f[x]=;
size[x]=;
if (*x<=n)
dfs_dp(*x);
if (*x+<=n)
dfs_dp(*x+);
if (*x<=n)
if (*x+>n||size[*x+]==)
{
f[x]=f[*x];
size[x]+=size[*x];
}
else
{
f[x]=((f[*x]*f[*x+]%p)*C(size[*x],size[*x]+size[*x+])%p)%p;
size[x]+=size[*x]+size[*x+];
}
}
int main()
{int i;
cin>>n>>p;
fac[]=;
for (i=;i<=n;i++)
{
int x=i;
num[i]=num[i-];
while (x%p==)
{
num[i]++;
x/=p;
}
if (i%p==) fac[i]=fac[i-];
else fac[i]=fac[i-]*i%p;
}
dfs_dp();
cout<<f[];
}