首页 > 代码库 > HNU 13101 The Triangle Division of the Convex Polygon 卡特兰数第n项%m(m可为非素数
HNU 13101 The Triangle Division of the Convex Polygon 卡特兰数第n项%m(m可为非素数
题目链接:点击打开链接
首先要n-=2,然后就是一个卡特兰数了。
上一题用的是 h(n) = h(n-1) * (4n-2)/(n+1);
这题用的是 h(n) = (2n)! * n! / (n+1)!;
然后对阶乘分解质因数:
点击打开链接
分解完了直接快速幂。
#include<stdio.h> #include<iostream> #include<cmath> #include<cstring> using namespace std; #define int __int64 const int N = 100000; int prime[N],primenum;//有primenum个素数 math.h void PRIME(int Max_Prime){ primenum=0; prime[primenum++]=2; for(int i=3;i<=Max_Prime;i+=2) for(int j=0;j<primenum;j++) if(i%prime[j]==0)break; else if(prime[j]>sqrt((double)i) || j==primenum-1) { prime[primenum++]=i; break; } } int n, m; void mul(int &x, int y){ x *= y; if(x >= m) x %= m; else if(x<0) x = x%m+m; } int Pow(int x, int y){ int ans = 1; while(y){ if(y&1) mul(ans, x); mul(x, x); y >>= 1; } return ans; } int D[N]; void work1(int x){ for(int i = 0; prime[i]<=x; i++){ D[i] = 0; for(int j = prime[i]; j <= x; j*=prime[i]) D[i] += x/j; } } void work2(int x){ for(int i = 0; prime[i]<=x; i++) for(int j = prime[i]; j <= x; j*=prime[i]) D[i] -= x/j; } void debug(){ for(int i = 0; i<primenum; i++) if(D[i])printf("[%d,%d]\n", prime[i],D[i]);puts(""); } int work(){ if(m==1)return 0; if(n==1)return 1; int res = 1; //f[n] = 2n!/n!/(n+1)!; work1(2*n); work2(n); work2(n+1); for(int i = 0; prime[i] <= 2*n; i++) if(D[i]) mul(res, Pow(prime[i],D[i])); return res; } #undef int int main() { PRIME(1000000); while(cin>>n>>m){ n-=2; cout<< work()%m <<endl; } return 0; }
HNU 13101 The Triangle Division of the Convex Polygon 卡特兰数第n项%m(m可为非素数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。