题目描述
A、B两个人玩抢7游戏，游戏规则为：
A先报一个起始数字 X（10 ≤ 起始数字 ≤ 10000），B报下一个数字 Y （X - Y < 3），A再报一个数字 Z（Y - Z < 3），以此类推，直到其中一个抢到7，抢到7即为胜者；
在B赢得比赛的情况下，一共有多少种组合？
输入描述
起始数字 M
10 ≤ M ≤ 10000如：
100
输出描述
B能赢得比赛的组合次数
用例
| 输入 | 10 |
| 输出 | 1 |
| 说明 | 无 |
数学分析解法（可能会超时）
下面模拟M为10~14时，B能够获胜的一些情况：
看完上图，我们可以发现：
抛开A首次叫的数字M，剩下的 M - 7 长度（上图中有颜色的），必须发生奇数次叫，才能保证B获胜。
原因是：奇数次叫中，第一次必然是B，由于是奇数次，因此最后一次也必然是B，比如
BAB
BABAB
都是奇数次。
因此我们只需要将整数 M - 7 划分为奇数块即可，且每块取值只能是1或2。
我们可以假设初始时，一共发生了M-7次叫（M-7可能不是奇数），即每块长度都是1，此时我们设
oneCount = M - 7twoCount = 0然后检查 oneCount + twoCount 的和（一共叫几次）：
若为奇数，则计算 oneCount 个 1 和 twoCount 个 2 形成的不重复的全排列的个数，统计进结果ans若为偶数，则B无法获胜之后，我们应该合并两个1为一个2，即：
oneCount -= 2twoCount += 1此时就会产生一种新的叫声情况，将新的oneCount和twoCount带入前面逻辑，进行循环处理，知道oneCount < 0 停止。
本题的数量级很大，10 ≤ M ≤ 10000，因此满足要求的情况数量可能极端大，此时我们应该使用大数记录结果。
JS算法源码
const rl = require("readline").createInterface({ input: process.stdin });var iter = rl[Symbol.asyncIterator]();const readline = async () => (await iter.next()).value;void (async function () { const m = parseInt(await readline()); const factor = initFactor(m - 7); let oneCount = m - 7; let twoCount = 0; // 记录B赢的情况数 let ans = BigInt(0); while (oneCount >= 0) { // 叫的次数为奇数时，才能B赢 if ((oneCount + twoCount) % 2 != 0) { ans += getPermutationCount(oneCount, twoCount); } // 合并两个1为一个2 oneCount -= 2; twoCount += 1; } console.log(ans.toString()); // 求解不重复的全排列数 function getPermutationCount(oneCount, twoCount) { // 即 1 1 1 1 1 或 2 2 2 这种情况，此时只有一种排列 if (oneCount == 0 || twoCount == 0) { return BigInt(1); } else { // 排列数去重，比如 1 1 1 2 2 的不重复排列数为 5! / 3! / 2! = 10 return factor[oneCount + twoCount] / factor[oneCount] / factor[twoCount]; } } // 阶乘 function initFactor(n) { const factor = new Array(n + 1); factor[0] = BigInt(1); for (let i = 1; i <= n; i++) { factor[i] = BigInt(i) * factor[i - 1]; } return factor; }})();
Java算法源码
import java.math.BigInteger;import java.util.Scanner;public class Main { static BigInteger[] factor; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); initFactor(m - 7); int oneCount = m - 7; int twoCount = 0; // 记录B赢的情况数 BigInteger ans = new BigInteger("0"); while (oneCount >= 0) { // 叫的次数为奇数时，才能B赢 if ((oneCount + twoCount) % 2 != 0) { ans = ans.add(getPermutationCount(oneCount, twoCount)); } // 合并两个1为一个2 oneCount -= 2; twoCount += 1; } System.out.println(ans); } // 求解不重复的全排列数 public static BigInteger getPermutationCount(int oneCount, int twoCount) { if (oneCount == 0 || twoCount == 0) { // 即 1 1 1 1 1 或 2 2 2 这种情况，此时只有一种排列 return new BigInteger("1"); } else { // 排列数去重，比如 1 1 1 2 2 的不重复排列数为 5! / 3! / 2! = 10 return factor[oneCount + twoCount].divide(factor[oneCount].multiply(factor[twoCount])); } } // 阶乘 public static void initFactor(int n) { factor = new BigInteger[n + 1]; factor[0] = new BigInteger("1"); for (int i = 1; i <= n; i++) { factor[i] = factor[i - 1].multiply(new BigInteger(i + "")); } }}
Python算法源码
这里Python进行了大数除法，因此数值类型变为了float，不在支持大数，所以需要使用decimal。
import decimal # 超大数运算内置库from decimal import Decimaldecimal.setcontext(decimal.Context(prec=2500)) # 设置超大数精度m = int(input())factor = []# 阶乘def initFactor(n): factor.append(Decimal(1)) for i in range(1, n+1): factor.append(Decimal(i) * factor[-1])# 求解不重复的全排列数def getPermutationCount(oneCount, twoCount): if oneCount == 0 or twoCount == 0: # 即 1 1 1 1 1 或 2 2 2 这种情况，此时只有一种排列 return 1 else: # 排列数去重，比如 1 1 1 2 2 的不重复排列数为 5! / 3! / 2! = 10 return factor[oneCount + twoCount] / factor[oneCount] / factor[twoCount]def getResult(): initFactor(m - 7) oneCount = m - 7 twoCount = 0 # 记录B赢的情况数 ans = Decimal(0) while oneCount >= 0: # 叫的次数为奇数时，才能B赢 if (oneCount + twoCount) % 2 != 0: ans += getPermutationCount(oneCount, twoCount) # 合并两个1为一个2 oneCount -= 2 twoCount += 1 return ansprint("{:.0f}".format(getResult()))
C算法源码
下面代码没有实现大数运算，关于大数运算可以参考：
大数运算（加、减、乘、除）-CSDN博客
#include <stdio.h>// 阶乘long long getFactor(int n) { long long ans = 1; for (int i = 2; i <= n; i++) { ans *= i; } return ans;}// 求解不重复的全排列数long long getPermutationCount(int oneCount, int twoCount) { if (oneCount == 0 || twoCount == 0) { // 即 1 1 1 1 1 或 2 2 2 这种情况，此时只有一种排列 return 1; } else { // 排列数去重，比如 1 1 1 2 2 的不重复排列数为 5! / 3! / 2! = 10 return getFactor(oneCount + twoCount) / getFactor(oneCount) / getFactor(twoCount); }}int main() { int m; scanf("%d", &m); int oneCount = m - 7; int twoCount = 0; // 记录B赢的情况数 long long ans = 0; while (oneCount >= 0) { // 叫的次数为奇数时，才能B赢 if ((oneCount + twoCount) % 2 != 0) { ans += getPermutationCount(oneCount, twoCount); } // 合并两个1为一个2 oneCount -= 2; twoCount += 1; } printf("%lld", ans); return 0;}
动态规划解法（不会超时）
本题最优解法为动态规划，动态规划的逻辑很简单，假设A从m开始叫，那么：
B叫了数字 i 的方案数有多少种呢？
如果B叫了数字 i，那么上一把A可能会叫数字i+1，也可能叫数字i+2
dpB[i] 表示 B 能叫到数字 i 的方案数
dpA[i] 表示 A 能叫到数字 j 的方案数
那么 dpB[i] = dpA[i+1] + dpA[i+2]
同理的是，如果A叫了数字 i，那么上一把B可能会叫数字i+1，也可能会叫数字 i+2
那么 dpA[i] = dpB[i+1] + dpB[i+2]
初始时，是A从m开始叫，因此 dpA[m] = 1，即A叫到数字m的方案数为1。而B肯定叫不到数字m，因此初始化dpB[m] = 0。
之后我们可以递推出dpB[m-1]，即B叫出数字m-1的方案数，即dpB[m-1] = dpA[m] + dp[m+1]
提示，根据dpB[m-1] = dpA[m] + dpA[m+1]的递推式，我们可以了解到dpA,dpB数组的长度应该初始化为m+2，这样上面递推式才不会越界。
且dpA[m] = 1，dpA[m+1] = 0
而数字m-1，对于A而言是叫不到的，因此dpA[m-1]=0，但是也可以基于递推式得到：
dpA[m-1] = dpB[m] + dpB[m+1]，而dpB[m]和dpB[m+1]都应该初始化为0。
因此我们只需要按照上面递推式，一直递推到dpB[7]即可返回。
Java算法源码
import java.math.BigInteger;import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); // dpA[i] 表示 A 叫 数字i 的方案数 BigInteger[] dpA = new BigInteger[m + 2]; // 初始化dpA[i] for (int i = 0; i < m + 2; i++) dpA[i] = new BigInteger("0"); // 由于是A从m开始叫，因此A叫m的方案数为1 dpA[m] = new BigInteger("1"); // dpB[i] 表示 B叫 数字i 的方案数 BigInteger[] dpB = new BigInteger[m + 2]; // 初始化dpB[i] for (int i = 0; i < m + 2; i++) dpB[i] = new BigInteger("0"); for (int i = m - 1; i >= 7; i--) { // B叫数字i的方案数 = A叫数字i+1的方案数 + A叫数字i+2的方案数 dpB[i] = dpA[i + 1].add(dpA[i + 2]); // A叫数字i的方案数 = B叫数字i+1的方案数 + B叫数字i+2的方案数 dpA[i] = dpB[i + 1].add(dpB[i + 2]); } // 返回B叫7的方案数 System.out.println(dpB[7]); }}
JS算法源码
const rl = require("readline").createInterface({ input: process.stdin });var iter = rl[Symbol.asyncIterator]();const readline = async () => (await iter.next()).value;void (async function () { const m = parseInt(await readline()); // dpA[i] 表示 A 叫 数字i 的方案数 const dpA = new Array(m + 2).fill(0).map(() => BigInt(0)); // 由于是A从m开始叫，因此A叫m的方案数为1 dpA[m] = BigInt(1); // dpB[i] 表示 B叫 数字i 的方案数 const dpB = new Array(m + 2).fill(0).map(() => BigInt(0)); for (let i = m - 1; i >= 7; i--) { // B叫数字i的方案数 = A叫数字i+1的方案数 + A叫数字i+2的方案数 dpB[i] = dpA[i + 1] + dpA[i + 2]; // A叫数字i的方案数 = B叫数字i+1的方案数 + B叫数字i+2的方案数 dpA[i] = dpB[i + 1] + dpB[i + 2]; } console.log(dpB[7].toString());})();
Python算法源码
# 输入获取m = int(input())# 算法入口def getResult(): # dpA[i] 表示 A 叫 数字i 的方案数 dpA = [0 for _ in range(m + 2)] # 由于是A从m开始叫，因此A叫m的方案数为1 dpA[m] = 1 # dpB[i] 表示 B叫 数字i 的方案数 dpB = [0 for _ in range(m + 2)] for i in range(m - 1, 6, -1): # B叫数字i的方案数 = A叫数字i+1的方案数 + A叫数字i+2的方案数 dpB[i] = dpA[i + 1] + dpA[i + 2] # A叫数字i的方案数 = B叫数字i+1的方案数 + B叫数字i+2的方案数 dpA[i] = dpB[i + 1] + dpB[i + 2] # 返回B叫7的方案数 return dpB[7]# 算法调用print(getResult())
C算法源码
下面代码没有实现大数运算，关于大数运算可以参考：
大数运算（加、减、乘、除）-CSDN博客
#include <stdio.h>int main() { int m; scanf("%d", &m); // dpA[i] 表示 A 叫 数字i 的方案数 long long dpA[m + 2]; // 初始化dpA[i] for (int i = 0; i < m + 2; i++) dpA[i] = 0; // 由于是A从m开始叫，因此A叫m的方案数为1 dpA[m] = 1; // dpB[i] 表示 B叫 数字i 的方案数 long long dpB[m + 2]; // 初始化dpB[i] for (int i = 0; i < m + 2; i++) dpB[i] = 0; for (int i = m - 1; i >= 7; i--) { // B叫数字i的方案数 = A叫数字i+1的方案数 + A叫数字i+2的方案数 dpB[i] = dpA[i + 1] + dpA[i + 2]; // A叫数字i的方案数 = B叫数字i+1的方案数 + B叫数字i+2的方案数 dpA[i] = dpB[i + 1] + dpB[i + 2]; } // 返回B叫7的方案数 printf("%lld", dpB[7]); return 0;}