HDU 4828 Grids(Catalan 数列、逆元、常量数组(打表))

一、题目描述

(2014年百度之星程序设计大赛 - 初赛(第一轮))
度度熊最近很喜欢玩游戏。这一天他在纸上画了一个2行N列的长方形格子。他想把1到2N这些数依次放进去,但是为了使格子看起来优美,他想找到使每行每列都递增的方案。不过画了很久,他发现方案数实在是太多了。度度熊想知道,有多少种放数字的方法能满足上面的条件?
输入:
  第一行为数据组数T(1<=T<=100000)。
  然后T行,每行为一个数N(1<=N<=1000000)表示长方形的大小。
输出:
  对于每组数据,输出符合题意的方案数。由于数字可能非常大,你只需要把最后的结果对1000000007取模即可。

二、算法说明

法一:盲猜法(冥想法、连蒙带猜法)
设解为 f(n),枚举法发现 f(1) = 1,f(2) = 2,f(3) = 5,正好是 Catalan 数列的第 1 到 3 项(从第 0 项起)。于是可以盲猜结果符合 f(n) = h(n)。其中 h(n) 是卡特兰数列中的第 n 项。且
HDU 4828 Grids(Catalan 数列、逆元、常量数组(打表))
由于最多有 10 万组数据,如果每次输入后再开始求解,就会严重超时。因此,根据题目要求 1 <= N <= 1000000,先将这 100 万个结果存入数组中,每次查询时直接返回数组中对应下标的元素的值即可。
在写递推公式时注意,由于 h(n) 一定为整数,而除以(n + 1)后可能会出现小数,所以要将分母连同分数线在代码中写成乘以分母的逆元(数论倒数)。1 ~ 1000001 的逆元(注意分母最大可以达到 1000001)也需要事先计算并存入常量数组。

法二:(待填坑)

三、AC代码(171 ms)

#include<cstdio>
#include<cstdlib>
#pragma warning(disable:4996)
unsigned int tc; unsigned long long n, f[1000001], inv[1000002]; const unsigned long long m = 1e9 + 7;
inline void EnumerateInverse(const unsigned long long& n, const unsigned long long& p) {
	inv[1] = 1;
	for (unsigned long long i = 2; i <= n; ++i)
		inv[i] = (p - p / i) * inv[p % i] % p;
}
int main() {
	scanf("%u", &tc); f[1] = 1; EnumerateInverse(1000001, m);
	for (unsigned long long i = 2, i0 = 1, i1 = 3, j = 6; i <= 1000000; ++i, ++i0, ++i1, j += 4) {
		f[i] = f[i0] * j % m * inv[i1] % m;
	}
	for (unsigned int i = 1; i <= tc; ++i) {
		scanf("%llu", &n);
		printf("Case #%u:\n%llu\n", i, f[n]);
	}
	return 0;
}
上一篇:editable grid on power apps


下一篇:文件系统-性能优化-磁臂调度算法