Description
称一个1,2,...,N的排列P1,P2...,Pn是Magic的,当且仅当2<=i<=N时,Pi>Pi/2. 计算1,2,...N的排列中有多少是Magic的,答案可能很大,只能输出模P以后的值
Solution
可以先发现这个排列其实是一个小根堆
F[i]=C(siz[i]-1,siz[i<<1])*F[i<<1]*F[i<<1|1]
组合数的部分可以用Lucas解决
#include#include #include #include #define MAXN 1000005using namespace std;typedef long long LL;int n,P,siz[MAXN],f[MAXN];LL inv[MAXN],fac[MAXN];void init(){ fac[0]=1,inv[1]=1; for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%P; for(int i=2;i<=n;i++) inv[i]=inv[P%i]*(P-P/i)%P; inv[0]=1; for(int i=1;i<=n;i++) inv[i]=inv[i-1]*inv[i]%P;}void dfs(int x){ siz[x]=1; if((x<<1)<=n)dfs(x<<1),siz[x]+=siz[x<<1]; if((x<<1|1)<=n)dfs(x<<1|1),siz[x]+=siz[x<<1|1];}LL C(LL x,LL y){ if(x n||(x<<1|1)>n)return 1; return ((C(siz[x]-1,siz[x<<1])*solve(x<<1))%P*solve(x<<1|1))%P;}int main(){ scanf("%d%d",&n,&P); init(),dfs(1); printf("%d\n",solve(1)); return 0;}