小兔的棋盘
Problem Description
小兔的叔叔从外面旅游回来给她带来了一个礼物，小兔高兴地跑回自己的房间，拆开一看是一个棋盘，小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0，0)走到终点(n,n)的最短路径数是C(2n,n),现在小兔又想如果不穿越对角线(但可接触对角线上的格点)，这样的路径数有多少?小兔想了很长时间都没想出来，现在想请你帮助小兔解决这个问题，对于你来说应该不难吧!
Input
每次输入一个数n(1<=n<=35)，当n等于－1时结束输入。
Output
对于每个输入数据输出路径数，具体格式看Sample。
Sample Input
1
3
12
-1
Sample Output
1 1 2
2 3 10
3 12 416024
Author
Rabbit
题目类型：高精度Catalan数
算法分析：直接计算高精度Catalan数即可，注意答案为相应的Catalan数乘以2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const int MOD = 1000000000 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 10000 + 66; string Mul (string a, long long b)//高精度a乘单精度b { string ans; long long na[maxn], La = a.size ();// maxn表示相乘结果的最大可能位数 fill (na, na + maxn, 0); for (long long i = La - 1; i >= 0; i--) na[La-i-1] = a[i] - '0'; long long w = 0; for (long long i = 0; i < La; i++) { na[i] = na[i] * b + w; w = na[i] / 10; na[i] = na[i] % 10; } while (w) { na[La++] = w % 10; w /= 10; } La--; while (La >= 0) ans += na[La--] + '0'; return ans; } string Div (string a, long long b)//高精度a除以单精度b { string r; long long d = 0; if(a == "0") return a;//特判 for (long long i = 0; i < a.size (); i++) { r += (d * 10 + a[i] - '0') / b + '0';//求出商 d = (d * 10 + (a[i] - '0')) % b;//求出余数 } long long p = 0; for (long long i = 0; i < r.size (); i++) if (r[i] != '0') { p = i; break; } return r.substr (p); } string Catalan (long long val) { string a("1"); for (long long i = 1; i <= val; i++) { a = Mul (a, (4 * i - 2)); a = Div (a, (i + 1)); } return a; } int main() { // ifstream cin ("aaa.txt"); long long n; int flag = 1; while (cin >> n) { if (n == -1) break; cout << flag++ << " " << n << " " << Mul (Catalan (n), 2) << endl; } return 0; } |
- « 上一篇：hdu2051
- hdu2098：下一篇 »