首页 > 代码库 > BZOJ 2822 AHOI 2012 树屋阶梯 卡特兰数+高精度
BZOJ 2822 AHOI 2012 树屋阶梯 卡特兰数+高精度
题目大意:高精度卡特兰数。
思路:上维基上看看,有一个模型和这个题一模一样,然后就剩下水水的高精度了。
(谁来教教我java...
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define BASE 10000 #define MAX 100010 using namespace std; struct BigInt{ int num[MAX],len; BigInt(int _ = 0) { num[len = 1] = _; } BigInt operator +(const BigInt &a)const { BigInt re; re.len = max(len,a.len); int temp = 0; for(int i = 1; i <= a.len; ++i) { re.num[i] = temp + num[i] + a.num[i]; temp = re.num[i] / BASE; re.num[i] %= BASE; } if(temp) re.num[++re.len] = temp; return re; } BigInt operator *(int a)const { BigInt re; re.len = len; int temp = 0; for(int i = 1; i <= len; ++i) { re.num[i] = temp + num[i] * a; temp = re.num[i] / BASE; re.num[i] %= BASE; } while(temp) re.num[++re.len] = temp % BASE,temp /= BASE; return re; } BigInt operator /(int a)const { BigInt re; re.len = len; int temp = 0; for(int i = len; i; --i) { re.num[i] = (temp + num[i]) / a; temp = (temp + num[i]) % a * BASE; } while(!re.num[re.len]) --re.len; return re; } }; int main() { int x; cin >> x; BigInt ans(1); for(int i = 2; i <= x; ++i) ans = ans * (4 * i - 2) / (i + 1); printf("%d",ans.num[ans.len]); for(int i = ans.len - 1; i; --i) printf("%04d",ans.num[i]); return 0; }
BZOJ 2822 AHOI 2012 树屋阶梯 卡特兰数+高精度
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。