计算先喝牛奶的 N 人准备谷物碗的方法数量（算法请求）-解网

问：

我得到了以下内容：

Rigel是一位谷物爱好者，也是一位巨大的慈善家。每天他有N个人他需要喂食。作为一个谷物爱好者，他想传播他对谷物的热爱，所以他开设了一个食品储藏室为有需要的人提供麦片。食品储藏室有 N 个碗，总是储存 N 种不同类型的麦片和他拥有的 N 种不同类型的牛奶。每种类型的牛奶和谷物每天都有库存，以只为一个人服务。Rigel意识到，如果他一遍又一遍地做同样的事情，他会最终会感到无聊。因此，他改变了每天准备谷物的方式。请注意，Rigel 是一个坚信牛奶第一理论，鄙视任何说谷物第一是正确的方法的人。所以当有一个空碗时，他总是会先倒牛奶。给定 N 很多人可以你可以计算 Rigel 准备麦片碗的不同方法的数量？注意：如果输出大于或等于 10⁹ + 7，则取模 10⁹ + 7

输入程序将要求一个输入
，即 N

输出
打印 Rigel 可以制备谷物的不同方法的数量。

例子：

input: 1    output: 1
input: 2    output: 24
input: 3    output: 3240

我尝试使用以下方法解决它：

#include <stdio.h>
#include <math.h>

int main(){
    long long int n;
    scanf("%lld", &n);
    long long int result = 1;
    for (int i = 1; i <= n; i++)
    {
        result = 1;
        if (i == 1)
        {
            result = 1;
        }else{
        result = result * (i*i) * (pow(6, i-1) * pow(10, i-2));
        }
    }
    printf("%lld\n", result);
    return 0;
}

是的，对于它工作的 3 个输入，但这些是唯一的测试用例，所以我提交了程序，但它没有被接受。就我个人而言，我认为我的错误在于查找数字的算法，我希望有人可以帮助我解决这个问题。

C 算法组合学

Rigel可以从任何人开始，从P1到PN，给他们一个碗和牛奶（牛奶永远是第一位的，所有的碗都是一样的）。然后，他可以给同一个人麦片，或者给另一个人一碗牛奶，依此类推，直到所有人都有碗、牛奶和麦片。他永远不能在碗和牛奶之前给麦片。

对于 N=2，可能的订单为

p1m1 p1c1 p2m2 p2c2
p1m1 p2m2 p1c1 p2c2
p1m1 p2m2 p2c2 p1c1

乘以 P、M、C 的 8 种组合，得到 24。

对于任何 N，这与通过 NxNxN 立方体的路径有关，其中路径只能在 x、y 和 z 轴上递增步长。我假设有一个封闭形式的解决方案。

p1m p1c p2m p2c p3m p3c
p1m p1c p2m p3m p2c p3c
p1m p1c p2m p3m p3c p2c
p1m p2m p2c p3m p3c p1c
p1m p2m p2c p3m p1c p3c
p1m p2m p2c p1c p3m p3c
p1m p2m p1c p2c p3m p3c
p1m p2m p1c p3m p2c p3c
p1m p2m p1c p3m p3c p2c
p1m p2m p3m p1c p2c p3c
p1m p2m p3m p1c p3c p2c
p1m p2m p3m p2c p1c p3c
p1m p2m p3m p2c p3c p1c
p1m p2m p3m p3c p1c p2c
p1m p2m p3m p3c p2c p1c

请注意，人员的顺序是通过将人员排列在 N 中来覆盖的！方式，因此 P1、P2 和 P3 的严格顺序。而且由于已经选择了牛奶和谷物的类型，我也懒得给它们编号。

现在 15 * 216 = 3240。

剩下的唯一问题是为可能的订单找到一个不错的闭合表达式。

加法：对于 N = 1，只有一个可能的订单来添加牛奶和谷物。请注意，有 2 个操作需要执行。

如果添加另一个碗作为第一个碗，则可以在准备第二个碗之前、期间或之后添加谷物。这给了我们 N = 2 的 3 个可能的订单。

添加更多的碗延续了这种模式。因此，可能的总订单数为 3 * 5 * ... * （2N - 1）

@JasonChristian 对于 N=2，我们有 4 个动作。因此，如果我们添加一个碗（如第 1 个），可以在 5 个地方添加谷物。因此，我们最终会得到 5 * 3 个可能的订单。如果我们再加一个碗，我们最终会得到 7 * 5 * 3 的可能订单。等等。（对于 N=1，有 2 个动作。添加一个碗为我们提供了 N=2 时找到的 3 个可能的阶数）。在 TeX 中，我会写：可能的订单数量是 $\Pi_{n=1}^{N-1} （2n+1}$。（从 3 到 2N-1 的所有奇数的乘法）。

上一个：尝试检查长整数是否为质数

下一个：度/秒到轴角

计算先喝牛奶的 N 人准备谷物碗的方法数量（算法请求）

Calculating the Number of Ways to Prepare Cereal Bowls for N People with Milk First (Algorithm Request)

评论

评论

评论