描述

传送门：牛客小白月赛1-I

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

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

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

Input

第一行一个数$T$，表示蛙蛙有$T$组询问。
接下去 $T$行，每行一个正整数$N$，表示目的地的个数（入栈元素个数）。

Output

输出共$T$行，每行一个答案，格式形如 “Case #i: xxx“，具体可见样例。
答案可能较大，请对$998244353$取模后输出。

Examples

intput
1
2
3
4
3
3
9
24

output

1
2
3

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

思路

看到出栈序列个数就知道肯定和卡特兰数有关。

总数就是全部的出栈个数，也就是第N个卡特兰数，不合法的就是：$A_1$固定第一个出栈，其他的出栈个数，也就是第N-1个卡特兰数。

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=1e5+5;
const long long mod=998244353;
typedef long long ll;

ll a[N]= {0,1};

ll x,y;
ll exgcd(ll a,ll b) {
    if(b==0) {
        x=1;y=0;
        return a;
    }
    ll r=exgcd(b,a%b);
    ll c=x; x=y;
    y=c-a/b*y;
    return r;
}

void Catalan() {        //卡特兰数递推式：a[n]=a[n-1]*(4*n-2)/(i+1)
    rep(i,2,100000) {
        exgcd(i+1,mod); //求(i+1)在模 mod 意义下的逆元
        x= (x%mod+mod)%mod;
        a[i]=a[i-1]*(4*i-2)%mod*x%mod;      
    }
}

int main() {
    Catalan();
    int T,n;
    scanf("%d",&T);
    rep(i,1,T) {
        scanf("%d",&n);
        printf("Case #%d: %lld\n",i,(a[n]-a[n-1]+mod)%mod);
    }
    return 0;
}