如何用Java实现话说大诗人李白,一生好饮。 幸好他从不开车。 一天,他提着酒壶,从家里出来,酒壶中有酒 2 斗。 他边走边唱: 无事街上走,提壶去打酒。 逢店加一倍,遇花喝一斗。 这一路上,他一共遇到店 N 次,遇到花 M 次。 已知最后一次遇到的是花,他正好把酒喝光了。 请你计算李白这一路遇到店和花的顺序,有多少种不同的可能? 注意:壶里没酒 (0 斗) 时遇店是合法的,加倍后还是没酒;但是没酒时遇花是不合法的。 输入格式 第一行包含两个整数 N 和 M。 输出格式 输出一个整数表示答案。由于答案可能很大,输出模 1000000007 的结果。 数据范围 对于 40% 的评测用例:1≤N,M≤10。 对于 100% 的评测用例:1≤N,M≤100。 输入样例: 5 10 输出样例: 14
时间: 2023-02-05 19:21:41 浏览: 56
用 Java 实现这道题,首先可以使用递归的方法。
首先,定义一个函数 `int solve(int n, int m, int x)`,表示当前遇到了 `n` 次店,`m` 次花,还剩下 `x` 斗酒的方案数。
然后,分类讨论:
- 如果当前遇到了店,则可以选择喝一斗酒,或者不喝,递归调用 `solve(n-1, m, x*2)` 和 `solve(n-1, m, x)`。
- 如果当前遇到了花,则只能喝一斗酒,递归调用 `solve(n, m-1, x-1)`。
- 如果酒已经喝完,则返回 1。
- 如果酒已经喝完,但还没遇到花,则返回 0。
最后,调用 `solve(n, m, 2)` 即可。
代码如下:
```
import java.util.Scanner;
public class Main {
static int mod = 1000000007;
static int solve(int n, int m, int x) {
if (x == 0) return 0;
if (x == 1) return m == 1 ? 1 : 0;
if (n == 0 && m == 0) return 1;
if (n == 0) return 0;
int ans = 0;
ans = (ans + solve(n-1, m, x)) % mod;
ans = (ans + solve(n-1, m, x*2)) % mod;
if (x > 1) ans = (ans + solve(n, m-1, x-1)) % mod;
return ans;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
System.out.println(solve(n, m, 2));
}
}
```