2111: [ZJOI2010]Perm 排列计数
Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 2418 Solved: 688[][][]Description
称一个1,2,...,N的排列P1,P2...,Pn是Magic的，当且仅当2<=i<=N时，Pi>Pi/2. 计算1，2，...N的排列中有多少是Magic的，答案可能很大，只能输出模P以后的值
Input
输入文件的第一行包含两个整数 n和p，含义如上所述。
Output
输出文件中仅包含一个整数，表示计算1,2,⋯, n的排列中， Magic排列的个数模 p的值。
Sample Input
20 23
Sample Output
16
HINT
100%的数据中，1 ≤ N ≤ 10^6, P ≤ 10^9，p是一个质数。 数据有所加强.
分析：有一堆限制，比如p3 < p6,p3 < p7.可以发现每个数最多都会有两个限制，即pi < p(i*2) ,pi < p(i*2+1).这两种限制条件给人的感觉就像是一棵二叉树，根节点必须必子节点小,问有多少种二叉树的组成方式.
那么先建树，设f[i]表示以i为根节点的子树的方案数，size[i]表示i的子树大小，那么就是一个非常经典的树形dp了.f[i] = f[i*2] * f[i * 2 + 1] * C(size[i] - 1,size[i * 2]).大概的意思就是i的子节点有i-1个数可以选，答案就是左子树的方案数*右子树的方案数*左子树选k个的方案数.
需要注意的是这道题p不是已经给定的，p有可能比n大，如果直接预处理出阶乘和逆元的阶乘，当n >= p时，阶乘就为0，不能直接算，需要把n变成p以下，那么就要用到lucas定理.
教训：n > p且p为质数时，不可直接算组合数，要用到lucas定理.
#include#include #include #include #include using namespace std;typedef long long ll;ll n, p, jie[1000010], ni[1000010], nijie[1000010], f[1000010], sizee[1000010];void init(){ jie[1] = 1; jie[0] = 0; ni[1] = 1; nijie[1] = nijie[0] = 1; for (int i = 2; i <= 1000000; i++) { jie[i] = (jie[i - 1] * i) % p; ni[i] = (p - p / i) * ni[p % i] % p; nijie[i] = (nijie[i - 1] * ni[i]) % p; }}ll solve(ll a, ll b){ if (a < b) return 0; if (a < p && b < p) return jie[a] * nijie[b] % p * nijie[a - b] % p; return solve(a / p, b / p) * solve(a % p, b % p) % p;}void dfs(ll u){ sizee[u] = 1; if (u * 2 > n) { f[u] = 1; return; } ll temp1 = 1, temp2 = 1; if (u * 2 <= n) { dfs(u * 2); sizee[u] += sizee[u * 2]; temp1 = f[u * 2]; } if (u * 2 + 1 <= n) { dfs(u * 2 + 1); sizee[u] += sizee[u * 2 + 1]; temp2 = f[u * 2 + 1]; } f[u] = temp1 * temp2 % p * solve(sizee[u] - 1, sizee[u * 2]) % p;}int main(){ scanf("%lld%lld", &n, &p); init(); dfs(1); printf("%lld\n", f[1] % p);return 0;}