首页 > 代码库 > HOJ 13101 The Triangle Division of the Convex Polygon（数论求卡特兰数（模不为素数））
HOJ 13101 The Triangle Division of the Convex Polygon（数论求卡特兰数（模不为素数））
The Triangle Division of the Convex Polygon
题意：求 n 凸多边形可以有多少种方法分解成不相交的三角形，最后值模 m。
思路：卡特兰数的例子，只是模 m 让人头疼，因为 m 不一定是素数，所以不一定存在逆元。
解法：式子为f(n) = ( C( 2*(n-2), (n-2) ) / (n-1)) % m ；令 p = n-2， 式子可化为：f(p) = （(2*p)! / ( p! * (p+1)! ) ） % m;
对 s！分解质因素，统计个数。设小于等于 s 的素数为 p1, p2, p3, ... , pk;
则各个素因子个数为 ：
for i = 1 to k q = s num(i) = 0 while q > 0 q = q / pi num(i) += q end while end for
所以，我们就可以统计出 f(p) 的素因子及个数，分子 + ， 分母 - 。最后计算时用快速幂。
代码：
#include <climits>#include <cstdio>#include <cstring>#include <cctype>#include <cmath>#include <ctime>#include <cstdlib>#include <cstdarg>#include <iostream>#include <fstream>#include <iomanip>#include <sstream>#include <exception>#include <stdexcept>#include <memory>#include <locale>#include <bitset>#include <deque>#include <list>#include <map>#include <set>#include <queue>#include <stack>#include <vector>#include <algorithm>#include <iterator>#include <functional>#include <string>#include <complex>#include <valarray>using namespace std;typedef long long ll;const int N = 1e6+7;bool tag[N];int p[N>>3];int t;void prime() { t = 0; memset(tag, 0, sizeof tag); p[t++] = 2, tag[4] = 0; for(int i = 3; i < N; i += 2) { if(!tag[i]) p[t++] = i; for(int j = 0, k; j < t && (k = i * p[j]) < N; ++j) { tag[k] = 1; if(i % p[j] == 0) break; } } return ;}int n;ll m, ans;int zp[N>>3], mp[N>>3];int tz, tp;int Factor(int q[], int u) { //分解 n! int i; for( i = 0; i < t && p[i] <= u; ++i) { int v = u; while(v) { v /= p[i]; q[i] += v; } } return i;}void cat(int n) { int nn = n + n; tz = tp = 0; memset(zp, 0, sizeof zp); memset(mp, 0, sizeof mp); tz = Factor(zp, nn); tp = Factor(mp, n); tp = Factor(mp, n+1); for(int i = 0; i < tp; ++i) zp[i] -= mp[i]; return ;}ll mult_mod(int a, int b, ll m) { ll res = 1LL, tt = (ll) a; while(b) { if(b&1) res = (res * tt) % m; tt = tt * tt % m; b >>= 1; } return res;}void solve() { n -= 2; cat(n); ans = 1LL; for(int i = 0; i < tz; ++i) { ans = (ans * mult_mod(p[i], zp[i], m)) % m; } printf("%I64d\n", ans);}int main(){#ifdef PIT freopen("c.in", "r", stdin);#endif // PIT prime(); while (~scanf("%d %I64d", &n, &m)) { solve(); } return 0;}
HOJ 13101 The Triangle Division of the Convex Polygon（数论求卡特兰数（模不为素数））
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。