题目描述
称一个1,2,...,N1,2,...,N1,2,...,N的排列P1,P2...,PnP_1,P_2...,P_nP1,P2...,Pn是MagicMagicMagic的,当且仅当2<=i<=N2<=i<=N2<=i<=N时,Pi>Pi/2P_i>P_{i/2}Pi>Pi/2. 计算1,2,...N1,2,...N1,2,...N的排列中有多少是MagicMagicMagic的,答案可能很大,只能输出模PPP以后的值
1≤N≤106,P≤1091≤N≤10^6,P≤10^91≤N≤106,P≤109题解
可以转化成小根堆,xxx的左右儿子为2x2x2x和2x+12x+12x+1
考虑dpdpdp,设fif_ifi表示以iii为根,用111到sizeisize_isizei来填充且合法的方案数 容易得到根最小,所以要从sizei−1size_i-1sizei−1个数中选出size2isize_{2i}size2i个数给左儿子,所以可以得到转移式子:fi=Csizei−1size2i∗f2i∗f2i+1f_i=C_{size_i-1}^{size_{2i}}*f_{2i}*f_{2i+1}fi=Csizei−1size2i∗f2i∗f2i+1 上代码#includeusing namespace std;const int N=1e6+5;int n,f[N],jc[N],ny[N],p,sz[N];int K(int x,int y){ int A=1;while(y){ if (y&1) A=1ll*A*x%p; x=1ll*x*x%p;y>>=1; }return A;}int C(int x,int y){ return 1ll*jc[x]*ny[y]%p*ny[x-y]%p;}void dfs(int x){ sz[x]=1;int l=x<<1,r=l|1; if (l<=n) dfs(l),sz[x]+=sz[l]; if (r<=n) dfs(r),sz[x]+=sz[r]; if (sz[x]<3){f[x]=1;return;} f[x]=1ll*C(sz[x]-1,sz[l])*f[l]%p*f[r]%p;}int main(){ scanf("%d%d",&n,&p); jc[0]=1;for (int i=1;i<=n;i++) jc[i]=1ll*i*jc[i-1]%p; ny[n]=K(jc[n],p-2);for (int i=n;i;i--) ny[i-1]=1ll*i*ny[i]%p; dfs(1);printf("%d\n",f[1]); return 0;}