题目链接:hdu 4828 Grids
题目大意:略。
解题思路:将上一行看成是入栈,下一行看成是出栈,那么执着的方案就是卡特兰数,用递推的方式求解。
#include <cstdio>
#include <cstring>
typedef long long ll;
const int N = 1000005;
const ll MOD = 1e9+7;
ll dp[N];
ll extendGcd(ll a, ll b, ll& x, ll& y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
ll d = extendGcd(b, a%b, y, x);
y -= a / b * x;
return d;
}
ll solve (ll n) {
ll x, y;
ll tmp = extendGcd(n + 1, MOD, x, y);
x = (x % MOD + MOD) % MOD;
return x;
}
void init () {
dp[1] = 1;
dp[2] = 2;
for (ll i = 3; i < N; i++)
dp[i] = (dp[i-1] * (4 * i - 2) % MOD * solve(i)) % MOD;
}
int main () {
int cas, n;
scanf("%d", &cas);
init();
for (int i = 1; i <= cas; i++) {
scanf("%d", &n);
printf("Case #%d:\n%lld\n", i, dp[n]);
}
return 0;
}
分享到:
相关推荐
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
ACM题库,一些题目和答案,以及解题报告,传上来共享
杭电OnlineJudge 200-2099的解题报告
acm hdu as easy as a+b
hdu 1695 GCD(欧拉函数+容斥原理).docx
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,现在他甚至会任意长度的正小数的加法。...
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
2、new做两件事,一是分配内存,二是调用类的构造函数 3、new建立的是一个对象,而malloc分配的是一块内存 4、new/delete是保留字,不需要头文
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
acm入门之枚举搜索,学校第一次acm培训,包括枚举及其优化,dfs和bfs
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241