作者主页：Designer 小郑 作者简介：Java全栈软件工程师一枚，来自浙江宁波，负责开发管理公司OA项目，专注软件前后端开发（Vue、SpringBoot和微信小程序）、系统定制、远程技术指导。CSDN学院、蓝桥云课认证讲师，全栈领域优质创作者，在校期间参加PAT乙级考试获得满分，三年ACM竞赛经验，斩获国奖两项，省奖五项。热爱技术、专注业务、开放合作、乐于分享，期待你我共同成长！ 主打方向：Vue、SpringBoot、微信小程序
题目链接：题目链接
题面：
小王不知不觉也在太空世界玩了一天了，突然想起来明天还要上学，这可把小王急坏了。
小张告诉小王，太空会客厅出口有一套 “超时空传唤座椅”，它可以帮助小王回到地球！
“超时空传唤座椅” 有着特殊的机制，这套座椅有两个驾驶位，主驾驶位必须由身高超过 170cm 的人乘坐，而副驾驶位必须由身高不超过 170cm 的人乘坐，只有两个驾驶位坐上了人， “超时空传唤座椅” 才能启动。
只有“超时空传唤座椅”的主驾驶坐上了人，副驾驶的门才会打开，小王时间紧迫，着急告别了小张，他必须赶紧前往太空会客厅。
太空会客厅早已聚集了大量着急返回地球的人，且前面已经有一部分比较固执的人，他们不接受自己被变更排队位置。
一旦排在最前面的人无法上座椅，这个人就会发泄情绪把队列堵住，让后面的人也无法返回地球。
那么，如果小王排在第 N（1 < N < 800000) 位，他可以顺利返回地球吗？如果可以，有多少种排队方案？
提示：小王后面的人不得排到小王前面，但小王前面的人（接受自己被变更排队位置的人，含小王）可任意调整顺序，以保证初始队伍中小王及前面的人可以顺利返回地球。
引用说明：以上图片来源自蓝桥云课。
知识点
- 卡特兰数
- 乘法逆元
- 快速幂取模
初始代码
代码语言：javascript复制public class JMain {
private static final Long MOD = 1000000007L;
public static Long doWork(int n,String str) {
//代码编辑区 开始
return 0L;
//代码编辑区 结束
}
public static void main(String[] args) {
//测试用例
System.out.println((Objects.equals(2L,doWork(6,"HM")) ? "【√正确】 " : "【X错误】 ") "样例一，答案：" doWork(6,"HM"));
System.out.println((Objects.equals(0L,doWork(6,"MH")) ? "【√正确】 " : "【X错误】 ") "样例二，答案：" doWork(6,"MH"));
}
}样例说明
输入数据分为两行，第一行是一个整数 N，代表小王排队的位数。
第二行是队伍不接受自己被变更排队位置的情况，从前往后排列，身高大于 170cm 的人记为 H，否则记为 M。
需要输出一个整数 X，代表允许小王成功回到地球的不同队伍排列数量。
因排队方案数会很大，对较大素数取模依旧可以保持答案的正确性（原理如下），所以请你将顺序数对 1000000007 取模。
一个数对7取余，那么1、8、15都是一类答案，如果正确答案是8，您求出来是15，那么也会被认为是对的。
对91取余，那么1、92、183都是一类答案，如果正确答案是183，您求出来是92，那么也会被认为是对的。
以此类推，只要取余素数越大，答案正确性就越高。
如果要保证完全正确，则要用字符串去模拟大数运算，这样没有必要，也不是题目主要考察的点，所以请您对 1000000007 取模。
样例一：
代码语言：javascript复制6
HM代表小王前面（含小王）共计 6 个人，前两个人为高、矮且不可更换位置，可能的情况为高矮高矮高矮、高矮高高矮矮两种，所以输出 2。
提示：因为前两个人不能变更，所以不会出现高高高矮矮矮的情况。
样例二：
代码语言：javascript复制6
MH代表小王前面（含小王）共计 6 个人，前两个人为矮、高且不可更换位置，第 1 个人会把队列堵死，所以小王无法返回地球，输出 0。
题解
考察对卡特兰数的理解，此题的原型如下：
电影院门票五块钱，有 N 个人拿五块纸币，有 M 个人拿十块纸笔，售票口初始无零钱，问保证全部人进去，有几种方案？
题解很简单，每个拿五块纸币的人后面必须有一个拿十块纸币的人跟他对应入场，这就是卡特兰数的裸题。
此题对卡特兰数进行了改编，如果是合法的情况，将 H 看为左括号，把 M 看做右括号，已知前面的括号情况，求剩下括号情况种类数使得左括号和右括号相等。
根据组合数学的推理，解题公式为：C(n-a,n-a n-b) - C(n-a-1,n-a n-b)。
因为结果可能很大，所以需要用费马小定理和快速幂进行取模计算。
参考代码如下：
代码语言：javascript复制import java.util.Objects;
public class JAns {
private static Long[] f = new Long[1000006];
private static final Long MOD = 1000000007L;
private static Boolean INIT_FLAG = false;
public static Long doWork(int n,String str) {
if(!INIT_FLAG) {
INIT_FLAG = true;
init();
}
int a = 0;
int b = 0;
for(int i = 0; i < str.length(); i ) {
if(Objects.equals('H',str.charAt(i))) {
a ;
} else if(Objects.equals('M',str.charAt(i))) {
b ;
if(b > a) {
return 0L;
}
}
}
if( (n & 1) > 0 || b > a || n-b-(a-b) < 0){
return 0L;
}
a = n / 2 - a;
b = n / 2 - b;
if( a < 0 || b < 0){
return 0L;
}
return (((f[a b] * (b 1 - a)) % MOD) * cal((f[a] * f[b 1]) % MOD, MOD - 2L, MOD)) % MOD;
}
private static Long cal(Long a, Long b, Long p){
Long ans = 1L;
while(b > 0){
if((b & 1) > 0){
ans = (ans * a) % p;
}
b >>= 1;
a = (a * a) % p;
}
return ans;
}
private static void init() {
f[0] = 1L;
for(int i = 1; i < 1000006; i ) {
f[i] = ((f[i - 1] % MOD) * (i % MOD)) % MOD;
}
}
public static void main(String[] args) {
//测试用例
System.out.println((Objects.equals(2L,doWork(6,"HM")) ? "【√正确】 " : "【X错误】 ") "样例一，答案：" doWork(6,"HM"));
System.out.println((Objects.equals(0L,doWork(6,"MH")) ? "【√正确】 " : "【X错误】 ") "样例二，答案：" doWork(6,"MH"));
}
}总结
要 AC 本题，必须学会快速幂取模和乘法逆元的算法，并且对卡特栏数的递推有一定的了解，不断递推数据，然后使用费马小定理进行取模，最终通过本题。
