题解 | #あなたの蛙が帰っています#

虽说出题人希望大家不被卡题意，可惜我还是被卡了。

那么就观察一下样例，如果我们把要求的记作一个函数 $\mathbf{F}(x)\backslash mathbf\; F(x)$，那么 $\mathbf{F}(x)\backslash mathbf\; F(x)$ 就应该满足：

• $\mathbf{F}(3)=3\backslash mathbf\; F(3)=3$
• $\mathbf{F}(9)=3432\backslash mathbf\; F(9)=3432$
• $\mathbf{F}(24)=508887030\backslash mathbf\; F(24)=508887030$

于是我们把数字 3432 扔到 OEIS 上去，发现了这个数列：http://oeis.org/A000245

（其实很明显可以发现这个题意中答案是单调递增的，所以我们把不是单调递增的序列去掉，倒着寻找第一个含 $33$ 的数列就是它了）

然后把它的写在脸上的递推公式找出来：$a(n)=3\times {\displaystyle \frac{(2\times n)!}{((n+2)!\times (n-1)!)}}a(n)\; =\; 3\backslash times\backslash dfrac\{(2\backslash times\; n)!\}\{\backslash left((n+2)!\backslash times(n-1)!\backslash right)\}$

另外这个题意和这个数列好像有 $11$ 单位的偏移量，复制公式的时候注意一下就好了。

#include<cstdio>
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = (int) 2e5 + 5, Mod = 998244353;
int fac[N], facinv[N];
int quick_mod(int a, int b){
    int s = 1;
    while (b) {
        if (b & 1) s = s * 1ll * a % Mod;
        a = a * 1ll * a % Mod; b >>= 1;
    }
    return s;
}
int A(int n){
    return 3ll * fac[2 * n] % Mod * facinv[n + 2] % Mod * facinv[n - 1] % Mod;
}
void PRINT(char*str){
    for (int i = 0; str[i]; ++i)
        putchar(str[i]);
}
signed main(){
    fac[0] = 1;
    for (int i = 1; i < N; ++i)
        fac[i] = fac[i - 1] * 1ll * i % Mod;
    facinv[N - 1] = quick_mod(fac[N - 1], Mod - 2);
    for (int i = N - 2; i >= 0; --i)
        facinv[i] = facinv[i + 1] * 1ll * (i + 1) % Mod;
    int T = init();
    for (int i = 1; i <= T; ++i) {
        int n = init();
        PRINT("Case #"), print(i);
        PRINT(": "), print(n == 1 ? 0 : A(n - 1)), putchar('\n');
    }
}