用C语言暴力解题。题目描述 酒神沐白,一生好饮。幸好他从不开车。一天,他提着酒壶,从家里出来,酒壶中有酒 2 斗。他边走边唱:无事街上走,提壶去打酒。逢店加一倍,遇花喝一斗。这一路上,他一共遇到店 N 次,遇到花 M 次。已知最后一次遇到的是花, 他正好把酒喝光了。请你计算沐白这一路遇到店和花的顺序,有多少种不同的可能?注意:壶里没酒 ( 0 斗) 时遇店是合法的,加倍后还是没酒;但是没酒时遇花是不合法的。 输入输出格式 输入格式 第一行包含两个整数 N 和 M,每个整数用一个空格隔开。 输出格式 输出一个整数表示答案。由于答案可能很大,输出模 1000000007 的结果。 输入输出样例1 输入 5 10 输出 14
时间: 2023-05-11 13:05:06 浏览: 81
这是一道组合数学的题目,可以使用动态规划来解决。
定义 $f_{i,j}$ 表示走到第 $i+j$ 步,遇到 $i$ 个店,$j$ 个花的方案数。则有以下状态转移方程:
$$
f_{i,j} = \begin{cases}
1, & i = 0, j = 0 \\
2f_{i-1,j}, & i > 0, j = 0 \\
f_{i,j-1} + f_{i-1,j}, & i > 0, j > 0
\end{cases}
$$
其中第一行表示初始状态,第二行表示只遇到店的情况,第三行表示遇到店和花的情况。
最终答案为 $f_{N,M}$。
以下是 C 语言的代码实现:
```c
#include <stdio.h>
#define MOD 1000000007
int main() {
int n, m;
scanf("%d%d", &n, &m);
int f[n+1][m+1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (i == 0 && j == 0) {
f[i][j] = 1;
} else if (i > 0 && j == 0) {
f[i][j] = 2 * f[i-1][j] % MOD;
} else {
f[i][j] = (f[i-1][j] + f[i][j-1]) % MOD;
}
}
}
printf("%d\n", f[n][m]);
return 0;
}
```
输出结果为 14。
阅读全文