易错辨析：八级五大翻车现场

# 易错辨析：五个最坑的写法，错例 vs 正例当场对比
from math import comb
import heapq

MOD = 10**9 + 7

# 坑 1：模意义下直接做除法 —— 除法必须先变成逆元
total = comb(100, 50) % MOD
wrong1 = (total // 2) % MOD                     # 错！取模后的数再除 2，结果无意义
right1 = total * pow(2, MOD - 2, MOD) % MOD     # 对：除以 2 等于乘 2 的逆元
print("坑1 错误写法:", wrong1, " 正确写法:", right1)

# 坑 2：快速幂 result 初始写成 0 —— 任何数的 0 次方都应是 1
def qpow_buggy(a, b, m):
    result = 0                                  # 错！初始值必须是 1
    while b > 0:
        if b % 2 == 1:
            result = result * a % m
        a = a * a % m
        b = b // 2
    return result

def qpow_right(a, b, m):
    result = 1                                  # 对
    a = a % m
    while b > 0:
        if b % 2 == 1:
            result = result * a % m
        a = a * a % m
        b = b // 2
    return result

print("坑2 2^0 错误写法:", qpow_buggy(2, 0, MOD), " 正确写法:", qpow_right(2, 0, MOD))

# 坑 3：Floyd 把 k 写进内层 —— 中转站必须最外层枚举
def floyd_wrong(d):
    n = len(d)
    for i in range(n):                          # 错！k 被关进最内层
        for j in range(n):
            for k in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d

def floyd_right(d):
    n = len(d)
    for k in range(n):                          # 对：k 在最外层
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d

INF = float("inf")
g = [  # 0→3→2→1 各一条边，0 到 1 的最短路是 3
    [0, INF, INF, 1],
    [INF, 0, INF, INF],
    [INF, 1, 0, INF],
    [INF, INF, 1, 0],
]
print("坑3 0到1 错误写法:", floyd_wrong([r[:] for r in g])[0][1], " 正确写法:", floyd_right([r[:] for r in g])[0][1])

# 坑 4：堆里放 (点, 距离) —— 堆按点编号排队，不按距离
h_wrong = []
heapq.heappush(h_wrong, (1, 100))               # 点 1，距离 100
heapq.heappush(h_wrong, (2, 5))                 # 点 2，距离 5
print("坑4 错误写法弹出:", heapq.heappop(h_wrong), "（点 1 并不最近）")
h_right = []
heapq.heappush(h_right, (100, 1))               # 对：(距离, 点)
heapq.heappush(h_right, (5, 2))
print("坑4 正确写法弹出:", heapq.heappop(h_right), "（距离 5 的点 2 先出队）")

# 坑 5：公式求和用 / 浮点除法 —— 大数丢失精度
n = 10**18
wrong5 = (n * (n + 1)) / 2                      # 错！浮点只有 15-16 位有效数字
right5 = (n * (n + 1)) // 2                     # 对：整除精确
print("坑5 浮点写法:", wrong5)
print("坑5 整除写法:", right5)