题目链接：题目链接
题面：
小王不知不觉也在太空世界玩了一天了，突然想起来明天还要上学，这可把小王急坏了。
小张告诉小王，太空会客厅出口有一套 “超时空传唤座椅”，它可以帮助小王回到地球！
“超时空传唤座椅” 有着特殊的机制，这套座椅有两个驾驶位，主驾驶位必须由身高超过 170cm 的人乘坐，而副驾驶位必须由身高不超过 170cm 的人乘坐，只有两个驾驶位坐上了人， “超时空传唤座椅” 才能启动。
只有“超时空传唤座椅”的主驾驶坐上了人，副驾驶的门才会打开，小王时间紧迫，着急告别了小张，他必须赶紧前往太空会客厅。
太空会客厅早已聚集了大量着急返回地球的人，且前面已经有一部分比较固执的人，他们不接受自己被变更排队位置。
一旦排在最前面的人无法上座椅，这个人就会发泄情绪把队列堵住，让后面的人也无法返回地球。
那么，如果小王排在第 N（1 < N < 800000) 位，他可以顺利返回地球吗？如果可以，有多少种排队方案？
提示：小王后面的人不得排到小王前面，但小王前面的人（接受自己被变更排队位置的人，含小王）可任意调整顺序，以保证初始队伍中小王及前面的人可以顺利返回地球。
引用说明：以上图片来源自蓝桥云课。
知识点
- 卡特兰数
- 乘法逆元
- 快速幂取模
初始代码
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 取模。
样例一：
6 HM
代表小王前面（含小王）共计 6 个人，前两个人为高、矮且不可更换位置，可能的情况为高矮高矮高矮、高矮高高矮矮两种，所以输出 2。
提示：因为前两个人不能变更，所以不会出现高高高矮矮矮的情况。
样例二：
6 MH
代表小王前面（含小王）共计 6 个人，前两个人为矮、高且不可更换位置，第 1 个人会把队列堵死，所以小王无法返回地球，输出 0。
题解
考察对卡特兰数的理解，此题的原型如下：
电影院门票五块钱，有 N 个人拿五块纸币，有 M 个人拿十块纸笔，售票口初始无零钱，问保证全部人进去，有几种方案？
题解很简单，每个拿五块纸币的人后面必须有一个拿十块纸币的人跟他对应入场，这就是卡特兰数的裸题。
此题对卡特兰数进行了改编，如果是合法的情况，将 H 看为左括号，把 M 看做右括号，已知前面的括号情况，求剩下括号情况种类数使得左括号和右括号相等。
根据组合数学的推理，解题公式为：C(n-a,n-a+n-b) - C(n-a-1,n-a+n-b)。
因为结果可能很大，所以需要用费马小定理和快速幂进行取模计算。
参考代码如下：
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 本题，必须学会快速幂取模和乘法逆元的算法，并且对卡特栏数的递推有一定的了解，不断递推数据，然后使用费马小定理进行取模，最终通过本题。
