[组合数学T2] [递推]
数学知识：
1.费马小定理：ap-1≡1(mod p) （a任意整数，p质数） （详细讲解 https://www.cnblogs.com/zylAK/p/9569668.html）
（简单证明：由欧拉定理 aφ（n）≡ 1（mod n） （正整数a，n互质） n为质数，φ(n)=n-1）
应用：由ap-1≡1(mod p) 得 a*ap-2≡1 即 inv[a]=ap-2(mod p)
2.lucas定理/组合数取模：
（https://www.cnblogs.com/fzl194/p/9095177.html）（https://blog.csdn.net/cutedumpling/article/details/81840047）
lucas定理：
lucas定理用于求C（n，m）mod p（p为质数） 的值
lucas(n,m,p)=C(n%p,m%p)*lucas(n/p,m/p,p)%p 递归出口lucas（n，0，p）返回1
题目描述
输入格式
输出格式
样例
数据范围与提示
题解 （题解参考 https://blog.csdn.net/yanzhenhuai/article/details/80615615）
1.Pi>P(i/2) 对于i=4，5 ，P(i/2)都是2， 所以对于所有的数连边，可以看成一个小根堆。
2.定义 F[i] :以i为子树，含有majic的个数;
显然最后输出结果 F[1];
3.定义size[i] :以i为子树的节点个数 倒着循环处理size
size[i]=size[i<<1]+size[i<<1|1]+1;
4.F[i]的转移： 首先根据分步乘法原理，若左右子树互不影响，则节点i的方案数=左子树的方案数×右子树的方案数
但由于对于下图
若将4，5，6节点交换位置仍符合要求
所以考虑组合数 对于1来说，右子树的组成可以是 从size[1]-1（不算1自己）个节点中的选出size[i<<1]个节点的情况数
所以在原来结果上乘$C_{size[i]-1}^{size[i<<1]}$
即F·[i]=F[i<<1]*F[i<<1|1]*$C_{size[i]-1}^{size[i<<1]}$
倒着循环进行递推即可
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #define ll long long 6 using namespace std; 7 8 const ll maxn=2000005; 9 int n,mod; 10 ll size[maxn],f[maxn]; 11 ll poww(ll a,ll b,ll p) 12 { 13 ll ans=1; 14 a%=p; 15 while(b) 16 { 17 if(b&1) ans=ans*a%p; 18 b>>=1; 19 a=a*a%p; 20 } 21 ans%=p; 22 return ans; 23 } 24 ll inv(ll x) 25 { 26 return poww(x,mod-2,mod); 27 } 28 ll C(ll x,ll y) 29 { 30 if(x<y) return 0; 31 if(y>x-y) y=x-y; 32 ll up=1,down=1; 33 for(ll i=x-y+1;i<=x;i++) up=up*i%mod; 34 for(ll i=1;i<=y;i++) down=down*i%mod; 35 return up*inv(down)%mod; 36 } 37 ll lucas(ll x,ll y) 38 { 39 if(y==0) return 1; 40 return C(x%mod,y%mod)*lucas(x/mod,y/mod)%mod; 41 } 42 43 int main() 44 { 45 scanf("%d%d",&n,&mod); 46 for(ll i=n;i>=1;i--) 47 size[i]=size[i<<1]+size[i<<1|1]+1; 48 for(ll i=1;i<=maxn;i++) 49 f[i]=1; 50 for(ll i=n;i>=1;i--) 51 f[i]=(f[i<<1]*f[i<<1|1])%mod*lucas(size[i]-1,size[i<<1])%mod; 52 printf("%lld ",f[1]); 53 }