French Fries问题题解

一、问题分析与数学模型

问题理解

• 无限长的人群，初始 $P$ 个人各有一根薯条
• 每次操作：每个人把薯条平分给左右邻居
• 经过 $T$ 次操作后，统计拥有至少 $L$ 根薯条的人数
• $T$ 可达 $5 \times 10^7$，需要高效算法

概率模型

初始在位置 $x_0$ 的 1 根薯条，经过 $T$ 次随机左右移动后，在位置 $x$ 的期望数量为：

要求 $T + (x - x_0)$ 为偶数。

二、代码实现与解析

1. 输入处理与变量定义

int p, t;
long double l;
const int jd = 15;

p = read(), t = read();
const int B = min(t, 100000ll);

• 读取 $P$, $T$, $L$
• 设置计算范围 $B = \min(T, 10^5)$，因远处概率可忽略

2. 预计算概率分布（对数计算避免溢出）

long double c[200005];
bool lst = 1;

for (int i = -B; i <= B; i++) {
    if ((t + i) % 2 == 0) {
        if (lst) {
            long double ini = 0.00;
            int cur = (t - i) / 2;
            
            // 使用对数计算：ln(n!) = sum(ln(k))
            for (int j = (t + i) / 2 + 1; j <= t; j++) {
                ini += log(j) * 1.00, ini -= log(2) * 1.00;
                ini -= log(cur) * 1.00, cur--;
            }
            for (int j = 1; j <= (t + i) / 2; j++)
                ini -= log(2.00);
            
            c[i + B] = ini;
            lst = 0;
        } else {
            // 递推计算：c[i] = c[i-2] * A/B
            c[i + B] = c[i + B - 2] + log((t - i) / 2 + 1) - log((t + i) / 2) * 1.00;
        }
    } else {
        c[i + B] = 1000000.00;  // 标记无效值
    }
}

数学原理：

• 使用对数避免阶乘溢出：$\ln c[i] = \ln(T!) - \ln(\frac{T+i}{2}!) - \ln(\frac{T-i}{2}!) - T\ln 2$
• 递推关系：$c[i] = c[i-2] \times \frac{(T-i+2)/2}{(T+i)/2}$

3. 概率值恢复与分段近似

for (int j = 0; j <= 2 * B; j++)
    if (c[j] != 1000000.00)
        c[j] = exp(c[j]);  // 恢复为实际概率值

vector<pair<pair<int, int>, long double>> inc;
for (int st = lb; st <= lb; st++) {
    long double mx = c[st], mn = c[st];
    int ql = st, qr = st - 2;
    
    for (int j = st; j <= 2 * B; j += 2) {
        if (max(mx * 1.00, c[j] * 1.00) * 1.00 / min(mn * 1.00, c[j] * 1.00) > 1.5) {
            // 当前段变化太大，分段
            inc.push_back({{ql, qr}, sqrt(mn * 1.00 * mx * 1.00)});
            ql = j, qr = j;
            mx = c[j], mn = c[j];
        } else {
            // 扩展当前段
            mx = max(mx * 1.00, c[j] * 1.00);
            mn = min(mn * 1.00, c[j] * 1.00);
            qr += 2;
        }
    }
    inc.push_back({{ql, 2 * B - st}, sqrt(mn * mx * 1.00)});
}

优化目的：

• 将连续的 $c[i]$ 分段，用几何平均数近似
• 减少后续区间加的操作次数
• 在评分规则的误差允许范围内保证正确性

4. 差分数组处理区间加

long double mp[10300005];
cin >> l;

for (int i = 1; i <= p; i++) {
    int x = read();
    for (auto v : inc) {
        pair<int, int> vv = v.first;
        long double qq = v.second;
        // 差分数组：区间 [x+vv.first, x+vv.second] 加 qq
        mp[x + vv.first] += qq;
        mp[x + vv.second + 2] -= qq;
    }
}

差分数组原理：

• mp[i] += qq 表示从位置 $i$ 开始的所有同奇偶位置加 $qq$
• mp[j+2] -= qq 表示从位置 $j+2$ 开始取消这个影响
• 最终通过前缀和恢复实际值

5. 统计结果

int res = 0;
for (int i = 0; i <= 10200000; i++) {
    if (i >= 2)
        mp[i] += mp[i - 2];  // 前缀和恢复实际值
    res += mp[i] >= l;       // 统计达标人数
}
cout << res;

三、算法复杂度分析

• 概率预计算：$O(B)$，其中 $B = \min(T, 10^5)$
• 分段处理：$O(B)$
• 区间加操作：$O(P \times \text{段数})$，段数远小于 $B$
• 统计结果：$O(\text{值域范围})$

总体在给定数据范围内可行。

四、关键优化技术

$1$. 对数计算：避免阶乘溢出

$2$. 范围截断：只计算概率显著的范围

$3$. 分段近似：在误差允许范围内减少操作次数

$4$. 差分数组：高效处理区间加法

$5$. 奇偶分离：利用概率分布的奇偶特性优化存储