1 solutions

  • 0
    @ 2025-6-5 23:04:53

    对除法的模逆元处理:

    因为 109+710^9 + 7 是质数,我们可以使用费马小定理来计算除以 6 的模逆元。即:

    a/6ainv(6)modMODa / 6 ≡ a * inv(6) mod MOD

    其中 inv(6)=6(MOD2)modMODinv(6) = 6^{(MOD - 2)} mod MOD

    计算:

    MOD=109+7MOD = 10^9 + 7

    inv6=pow(6,MOD2,MOD)inv6 = pow(6, MOD - 2, MOD)

    然后:

    S=m(m+1)(2m+1)/6modMODS = m * (m + 1) * (2m + 1) / 6 mod MOD

    可以表示为:

    S = (m * (m + 1) % MOD) * ((2m + 1) % MOD) % MOD * inv6 % MOD

    Information

    ID
    89
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    (None)
    Tags
    # Submissions
    0
    Accepted
    0
    Uploaded By