首页 > 试题广场 >

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

[编程题]あなたの蛙が帰っています
あなたの蛙が帰っています！ 

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

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

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


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

输入

3
3
9
24

输出

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

说明

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

备注:


算法知识视频讲解
开通博客
头像 小琢卷不动
发表于 2021-11-23 14:24:35
虽说出题人希望大家不被卡题意，可惜我还是被卡了。 那么就观察一下样例，如果我们把要求的记作一个函数 F(x)\mathbf F(x)F(x)，那么 F(x)\mathbf F(x)F(x) 就应该满足： F(3)=3\mathbf F(3)=3F(3)=3 F(9)=3432\mathbf F(9 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 ttkqwe
发表于 2025-10-20 09:54:29
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD = 998244353; // 模数 // 快速幂算法 // 功能：计算 a^b % mod // 原理：利用二进制拆 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 Silencer76
发表于 2025-10-20 11:03:25
注意到，题目所求的答案，即为卡特兰数相邻两项的差。 这里给出卡特兰数的前 项（下标从0开始）。 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

卡特兰数
难度：
1条回答 15浏览

热门推荐

通过挑战的用户

查看代码

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号