求N人份先加牛奶的麦片碗制备方式数（算法纠错求助）

数学模型推导 #

要计算制备麦片碗的不同方式数，需拆解为三个独立步骤：

1. 分配牛奶：N种不同牛奶分配给N个碗，属于全排列，共N!种方式。
2. 分配麦片：N种不同麦片分配给N个碗，同样是全排列，共N!种方式。
3. 安排操作顺序：每个碗需先加牛奶再加麦片，总共有2N个操作。所有合法的操作序列数为(2N)! / 2^N——因为每个碗的两个操作中，只有一半的排列满足牛奶在前，N个碗则需除以2^N。

综上，总方式数公式为：
result = (N! * N! * (2N)!) / (2^N) mod 1e9+7

验证示例：

• N=1：(1! *1! *2!)/2^1 = (1*1*2)/2=1 ✔️
• N=2：(2! *2! *4!)/2^2=(2*2*24)/4=24 ✔️
• N=3：(3! *3! *6!)/2^3=(6*6*720)/8=3240 ✔️

原代码的问题 #

1. 公式错误：原代码使用的i*i *6^(i-1)*10^(i-2)完全不符合问题的数学逻辑。
2. 循环逻辑混乱：每次循环将result重置为1，最终仅计算了i=N的错误公式值。
3. 浮点数精度问题：使用pow()函数计算整数幂，会导致大数时精度丢失，结果错误。
4. 未处理模运算：未对1e9+7取模，大数会溢出long long类型。

正确C语言实现 #

#include <stdio.h>
#include <stdlib.h>

#define MOD 1000000007

// 快速幂计算 (base^exponent) mod modu
long long pow_mod(long long base, long long exponent, long long modu) {
    long long result = 1;
    base %= modu;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % modu;
        }
        base = (base * base) % modu;
        exponent /= 2;
    }
    return result;
}

int main() {
    long long n;
    scanf("%lld", &n);
    
    // 预处理阶乘数组，fact[i] = i! mod MOD
    long long max_fact = 2 * n;
    long long* fact = (long long*)malloc((max_fact + 1) * sizeof(long long));
    fact[0] = 1;
    for (long long i = 1; i <= max_fact; i++) {
        fact[i] = (fact[i-1] * i) % MOD;
    }
    
    // 计算 2^n 的逆元，利用费马小定理：逆元为 pow_mod(2, MOD-2, MOD)^n
    long long inv_2 = pow_mod(2, MOD - 2, MOD);
    long long inv_2n = pow_mod(inv_2, n, MOD);
    
    // 计算最终结果，分步取模避免溢出
    long long result = (fact[n] * fact[n]) % MOD;
    result = (result * fact[2*n]) % MOD;
    result = (result * inv_2n) % MOD;
    
    printf("%lld\n", result);
    
    free(fact);
    return 0;
}

代码说明 #

1. 快速幂函数：高效计算幂和模逆元，完全避免浮点数精度问题。
2. 阶乘预处理：预计算到2N的阶乘并取模，防止大数溢出。
3. 模逆元处理：利用费马小定理将除法转换为乘法（因为MOD是质数，a的逆元为a^(MOD-2) mod MOD），符合模运算规则。

内容的提问来源于stack exchange，提问作者Jason Christian