作者主页:Designer 小郑 作者简介:Java全栈软件工程师一枚,来自浙江宁波,负责开发管理公司OA项目,专注软件前后端开发(Vue、SpringBoot和微信小程序)、系统定制、远程技术指导。CSDN学院、蓝桥云课认证讲师,全栈领域优质创作者,在校期间参加PAT乙级考试获得满分,三年ACM竞赛经验,斩获国奖两项,省奖五项。热爱技术、专注业务、开放合作、乐于分享,期待你我共同成长! 主打方向:Vue、SpringBoot、微信小程序
题目链接:题目链接
小王不知不觉也在太空世界玩了一天了,突然想起来明天还要上学,这可把小王急坏了。
小张告诉小王,太空会客厅出口有一套 “超时空传唤座椅”,它可以帮助小王回到地球!
“超时空传唤座椅” 有着特殊的机制,这套座椅有两个驾驶位,主驾驶位必须由身高超过 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 本题,必须学会快速幂取模和乘法逆元的算法,并且对卡特栏数的递推有一定的了解,不断递推数据,然后使用费马小定理进行取模,最终通过本题。