题目链接：https://www.nowcoder.com/acm/contest/203/H 题目大意：        魔方国有n座城市，编号为。城市之间通过n-1条无向道路连接，形成一个树形结构。澜澜打算在魔方国进行m次旅游，每次游览至少一座城市。为了方便，每次旅游游览的城市必须是连通的。此外，澜澜希望游览所有城市恰好一次。        澜澜想知道有多少种旅游方案满足条件，两个方案

1.利用整数唯一分解定理，求(n+1-m) * (n+m)!  /  ( m! * (n+1)!  ) 任何正整数都有且只有一种方法写出其素因子幂相乘的形式。比如18= 2 * 3^2 A=(p1^k1)*(p2^k2)*(p3^k3)*(p4^k4)*......*(pn^kn)   pi为素数 还有把阶层看作一个数,比m! 怎样求m!里面素数2的指数呢？ cnt=0;   while(

题意： 有一个杨辉三角，现在从顶点到第n行第k列，只能向下或向右下，问最短路径和模p的值。 要点： 如果n>2*m，此时一直往斜左上走到边界，再一直向上，这样最短，权值总和为C（n+1,m）+（n-m)；如果n<=2*m，就先向上到边界，再斜左上到顶点，这样总和为C(n+1,m+1)+m。 这里n和m很大，所以必须要用lucas定理，需要注意的是Lucas定理处理的p的范围大致为10^5数

inv[i] = ( MOD - MOD / i ) * inv[MOD%i] % MOD 证明： 设t = MOD / i , k = MOD % i 则有 t * i + k == 0 % MOD 有 -t * i == k % MOD 两边同时除以ik得到：-t * inv[k] == inv[i] % MOD 即 inv[i] == -MOD / i * inv[MOD%i]