首页 > 代码库 > HNU 13101 The Triangle Division of the Convex Polygon 组合数的因式分解求法
HNU 13101 The Triangle Division of the Convex Polygon 组合数的因式分解求法
题意：
求第n-2个Catalan数 模上 m。
思路：
Catalan数公式： Catalan[n] = C(n, 2n)/(n+1) = (2n)!/[(n+1)!n!]
因为m是在输入中给的，所以我们不能用求阶乘和其逆元的方法来求。因为当m不是素数的时候，可能不存在逆元。
这里，我们把阶乘做质因数分解，然后上下两边约分，即可求出解。
怎么来把这个n!因式分解呢？ 我们知道 n!中某个因子x的数量可以用log(n)的方法来求。
详见：这里
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #include <string> 8 #include <queue> 9 #include <stack>10 #include <vector>11 #include <map>12 #include <set>13 #include <functional>14 #include <cctype>15 #include <time.h>16 17 using namespace std;18 19 typedef __int64 ll;20 21 const int INF = 1<<30;22 const int MAXN = 1e6+5;23 /*24 Catalan Number : C(n, 2n)/(n+1) = (2n)!/[(n+1)!n!]25 */26 27 bool isPrime[MAXN];28 int Prime[MAXN], primeCnt;29 30 int cnt[MAXN];31 32 ll myPow(ll x, ll y, ll mod) {33 ll ret = 1;34 while (y>0) {35 if (y&1) ret = (ret*x)%mod;36 x = (x*x)%mod;37 y >>= 1;38 }39 return ret;40 }41 42 void getPrime() {43 primeCnt = 0;44 for (int i = 2; i < MAXN; i++) if (!isPrime[i]) {45 Prime[primeCnt++] = i;46 for (ll j = (ll)i*i; j < MAXN; j += i)47 isPrime[j] = true;48 }49 }50 51 inline void initFactor(int x) {52 for (int i = 0; Prime[i] <= x; i++)53 cnt[i] = 0;54 }55 56 void getFactor(int x, int v) {57 for (int i = 0; Prime[i]<=x; i++) {58 int t = x;59 while (t>0) {60 cnt[i] += (t/Prime[i])*v;61 t /= Prime[i];62 }63 }64 }65 66 ll getAns(int x, ll mod) {67 ll ret = 1;68 for (int i = 0; Prime[i] <= x; i++)69 ret = (ret*myPow(Prime[i], cnt[i], mod))%mod;70 return ret;71 }72 73 int main() {74 #ifdef Phantom0175 freopen("HNU13101.txt", "r", stdin);76 #endif //Phantom0177 78 getPrime();79 int n, m;80 ll ans;81 while (scanf("%d%d", &n, &m)!=EOF) {82 n -= 2;83 initFactor(2*n);84 getFactor(2*n, 1);85 getFactor(n+1, -1);86 getFactor(n, -1);87 printf("%I64d\n", getAns(2*n, m));88 }89 90 return 0;91 }
HNU 13101 The Triangle Division of the Convex Polygon 组合数的因式分解求法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。