首页 > 代码库 > HDU 4828 Grids
HDU 4828 Grids
这道题我做了很久，推出来一个过程，但是那样做是n^2的复杂度，这道题做不了。
后来，上网上搜了一下题解，才发现这个原来叫做卡特兰数。。。
真心给跪了，到底我是有多无知啊！！ 还有一个递推公式，不，应该说有很多，我选择了一个，不，是除题解的那人选了一个最好用的。
不光是这样，我还终于明白了逆元的终极奥义。原来他是用来抵消运算的，或者说是换了一种形式，变加为减，变除为乘。
说到乘法逆元，尤其是求模的逆元，当然少不了ex_gcd()了。
下面的是代码
#include <iostream>#include <cstdio>#include <cstring>using namespace std;#define LL long longconst int maxn = 1000010;const LL mod = 1000000007;LL ans[maxn];void exgcd(LL a, LL b, LL &x, LL &y){ if(b == 0) { x = 1; y = 0; return ; } exgcd(b, a%b, x, y); LL t = x; x = y; y = t - a/b * x;}void init(){ ans[1] = 1; for(int i = 2; i < maxn; i++) { ans[i] = (ans[i-1] * (4 * i - 2)) % mod; LL x, y; exgcd((LL)i+1, mod, x, y); ans[i] = (ans[i] * ((x + mod) % mod)) % mod; } return ;}int main(){ int t; cin >> t; init(); for(int Case = 1; Case <= t; Case++) { int n; scanf("%d", &n); printf("Case #%d:\n%I64d\n", Case, ans[n]); }}
很短，很精悍。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。