牛客小白月赛1 I あなたの蛙が帰っています 【卡特兰数】

链接:https://www.nowcoder.com/acm/contest/85/I
题目描述

あなたの蛙が帰っています! 

蛙蛙完成了一趟旅行,回家啦!但它还是没有去它心中非常想去的几个地方。总共有 N 个它 想去的目的地。蛙蛙下定了决心,它要做一个愿望清单,一定要让自己去那些想去的地方。蛙蛙 是这样做的:它会不定时地想起一个或多个目的地,然后按顺序写在愿望清单上。但是每次蛙蛙 出去旅行时,都会先去最近写在愿望清单上的地方,并且蛙蛙不会重复去一个目的地,但它会去 访问所有的目的地。蛙蛙有个最想去的地方,这个地方是它第一个想到的,但由于种种原因,这 个地方不能是第一个被蛙蛙访问的。蛙蛙脑中回想目的地的顺序是固定的,所以它想请问你,它最终访问这些目的地的顺序有多少种?
对于两种访问序列 ,它们是不同的当且仅当存在至少一个 ,使得  。

为了让大家不被卡题意,这里给出一句话题意:
已知一个没有深度限制的栈的入栈序列为 ,且  不能第一个出栈。求合法的出栈序列个数。答案对  取模。

输入描述:

第一行一个数 
 ,表示蛙蛙有 
 组询问。 
接下去
 行,每行一个正整数 
, 表示目的地的个数(入栈元素个数)。

输出描述:

输出共 
 行,每行一个答案,格式形如 
 ,具体可见样例。 
答案可能较大,请对
 取模后输出。
示例1

输入

复制
3
3
9
24

输出

复制
Case #1: 3
Case #2: 3432
Case #3: 508887030

说明

对于样例中的第一个询问,设三个目的地为 
, 
, 
,其中 
 是第一个目的地,所以不能第一个访问。则有三种合法访问序列:
 ·

 · 

 · 

备注:


 
相关知识传送门:
 
AC代码:
 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <algorithm>
 4 #include <time.h>
 5 #include <string.h>
 6 #include <math.h>
 7 #include <vector>
 8 #include <iostream>
 9 #include <deque>
10 #include <set>
11 #include <bitset>
12 #include <queue>
13 #include <map>
14 using namespace std;
15 typedef long long ll;
16 const int N = 2e5+10;
17 const ll mod = 998244353;
18 ll fac[N];
19 
20 void extgcd(ll a,ll b,ll& d,ll& x,ll& y){
21     if(!b){ d=a; x=1; y=0;}
22     else{ extgcd(b,a%b,d,y,x); y-=x*(a/b); }
23 }
24 ll inv(ll a,ll n){
25     ll d,x,y;
26     extgcd(a,n,d,x,y);
27     return d==1?(x+n)%n:-1;
28 }
29 
30 void init() {
31     fac[0] = fac[1] = 1;
32     for(int i = 2; i < N; ++i) {
33         fac[i] = fac[i-1]*i%mod;
34     }
35 }
36 ll cat(ll n) {
37     return fac[2*n]*inv(fac[n+1]*fac[n],mod)%mod;
38 }
39 int main(int argc, char *argv[]) {
40     init();
41     int T;
42     int ca = 1;
43     scanf("%d", &T);
44     while(T--) {
45         ll n;
46         cin >> n;
47         ll ans = (cat(n)-cat(n-1))%mod;
48         if(ans < 0) ans += mod;
49         printf("Case #%d: ", ca++);
50         cout << ans << '
';
51     }
52 }
原文地址:https://www.cnblogs.com/TianyuSu/p/9391376.html