Description

题库链接

询问有多少个 \(1\sim N\) 的排列 \(P\) 满足“ \(\forall i\in[2,N], P_i>P_{\frac{i}{2}}\) ” 。对质数 \(P\) 取模。

\(1\leq N\leq 1000000,1\leq P\leq 10^9\)

Solution

容易发现满足题目需要的性质的序列就是满足堆性质的。那么可以在树(堆)上 \(DP\) 。

记 \(f_o\) 为在 \(o\) 节点及其子树中满足条件的编号方法数。

显然 \[f_o=f_{2o}f_{2o+1}C_{size_{2o}+size_{2o+1}}^{size_{2o}}\]

注意由于 \(p\) 不一定大于 \(n\) ,所以不能直接求逆。

Code

//It is made by Awson on 2018.3.22
#include <bits/stdc++.h>
#define LL long long
#define dob complex<double>
#define Abs(a) ((a) < 0 ? (-(a)) : (a))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))
#define writeln(x) (write(x), putchar('\n'))
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int N = 1e6;
void read(int &x) {
char ch; bool flag = 0;
for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());
for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());
x *= 1-2*flag;
}
void print(int x) {if (x > 9) print(x/10); putchar(x%10+48); }
void write(int x) {if (x < 0) putchar('-'); print(Abs(x)); } int n, p, a[N+5], b[N+5], f[N+5], size[N+5], num[N+5]; int C(int n, int m) {
if (num[n]-num[n-m]-num[m] == 0) return 1ll*a[n]*b[n-m]%p*b[m]%p;
return 0;
}
int dfs(int o) {
if (o*2 > n) {f[o] = 1; return size[o] = 1; }
if (o*2+1 > n) {size[o] = dfs(o*2)+1; f[o] = f[o*2]; return size[o]; }
size[o] = 1+dfs(o*2)+dfs(o*2+1);
f[o] = 1ll*f[o*2]*f[o*2+1]%p*C(size[o*2]+size[o*2+1], size[o*2+1])%p;
return size[o];
}
void work() {
read(n); read(p);
a[0] = b[0] = a[1] = b[1] = 1;
for (int i = 2; i <= n; i++) {
if (i%p) b[i] = -1ll*(p/i)*b[p%i]%p;
else b[i] = 1;
}
for (int i = 2; i <= n; i++) {
b[i] = 1ll*b[i]*b[i-1]%p;
if (i%p) a[i] = 1ll*a[i-1]*i%p;
else a[i] = a[i-1];
}
for (int i = 2; i <= n; i++) {
num[i] = num[i-1];
if (i%p == 0) {
int x = i;
while (x%p == 0) ++num[i], x /= p;
}
}
dfs(1); writeln((f[1]+p)%p);
}
int main() {work(); return 0; }
05-10 23:14