厦门唯一官方网站,宜昌做网站优化,近期的新闻消息,ppt模板下载官网题目链接#xff1a; http://acm.hdu.edu.cn/showproblem.php?pid5673 题目描述#xff1a; 一个人从原点开始向右走#xff0c; 要求N秒后回到原点#xff0c; 且过程中不能到负半轴#xff0c; 人有两种操作#xff0c; 走动或者停止#xff0c; 问总共有多少种方案 http://acm.hdu.edu.cn/showproblem.php?pid5673 题目描述 一个人从原点开始向右走 要求N秒后回到原点 且过程中不能到负半轴 人有两种操作 走动或者停止 问总共有多少种方案 解题思路 类似于括号匹配问题 和那个我去年这个时候接触到的最裸的不能越过对角线的正方形走到对角问题 卡特兰数 从2开始枚举走动步数 然后剩下的就是不动的步数 用不动的步数做个填充就可以了 设计到取模 需要逆元 代码 #include iostream
#include cstdio
#include string
#include vector
#include cstring
#include iterator
#include cmath
#include algorithm
#include stack
#include deque
#include map
#define lson l, m, rt1
#define rson m1, r, rt1|1
#define mem0(a) memset(a,0,sizeof(a))
#define meminf(a) memset(a,-0x3f,sizeof(a))
#define fi(n) for(i0;in;i)
#define fj(m) for(j0;jm;j)
#define sca(x) scanf(%d,x)
#define ssca(x) scanf(%s,x)
#define scalld(x) scanf(%I64d,x)
#define print(x) printf(%d\n, x)
#define printlld(x) printf(%I64d\n,x)
#define de printf(\n)
#define yes printf(YES\n)
#define no printf(NO\n)
typedef long long ll;
using namespace std;const int mod 1e97;
const int maxn 1e6100;ll inv[maxn];
ll h[maxn];
ll c[maxn];void init() {inv[1] 1;for( int i 2; i maxn; i ) { // 预处理逆元inv[i] (mod - mod / i) * inv[mod%i] % mod;}
}int main() {init();int t;int n;h[0] h[1] 1;for( int i 2; i maxn; i ) { // 卡特兰数h[i] h[i-1] * (4*i-2)%mod * inv[i1] % mod;}sca(t);while( t-- ) {sca(n);ll ans 1;c[0] 1;for( int i 1; i n; i ) { // 组合数c[i] c[i-1] * (n-i1) % mod * inv[i] % mod;}for( int i 1; ; i ) {int k n - (i1);if( k 0 ) break;ans (ans h[i] * c[k]) % mod;}printf( %lld\n, ans );}return 0;
} View Code 思考 很裸的卡特兰数 组合数学很有意思 然后就是说我感觉现在需要开始整理一下板子了 比如说这个 还有那个神题等等 洗完澡回来再说 我好菜啊 http://acm.hdu.edu.cn/showproblem.php?pid5673 转载于:https://www.cnblogs.com/FriskyPuppy/p/7429331.html
