题解

问题分析

题目要求计算使用“亵渎”法术杀死所有怪物的总得分。核心是理解“亵渎”的施放机制和得分计算方式：

• 总施放次数 ( k ) 等于怪物的最大血量（即 ( n )，因为最高血量为 ( n ) 且必存在）。
• 每次施放后，存活怪物的伤害前血量 ( x ) 会贡献 ( x^k ) 分，总得分是所有怪物在存活期间的贡献总和。

关键思路

1. 得分公式转化：
   每个血量为 ( s ) 的怪物，在第 ( 1 ) 到 ( s ) 次施放中存活，贡献为 ( 1^k + 2^k + \dots + s^k )。总得分可转化为：
   [ \text{总得分} = \sum_{s \in S} \sum_{x=1}^s x^k ]
   其中 ( S ) 是所有存在的怪物血量集合（( 1 \sim n ) 除去缺失的 ( a_i )），( k = n )。

2. 高效求和：
   通过数学转化，总得分可拆分为两部分：

   • ( S_1 )：所有可能血量（( 1 \sim n )）的贡献总和。
   • ( S_2 )：缺失血量的贡献总和（需减去）。
     即 ( \text{总得分} = (S_1 - S_2) \mod (10^9 + 7) )。

3. 幂和计算优化：
   利用费马小定理简化大指数幂计算，结合周期求和处理大规模数据（( n \leq 10^{13} )）：

   • 对 ( x^b \mod \text{MOD} )，当 ( x ) 与 MOD 互质时，( x^b \equiv x^{b \mod (\text{MOD}-1)} \mod \text{MOD} )。
   • 按模长周期分组求和，减少重复计算。

代码实现

MOD = 10**9 + 7
PHI = MOD - 1  # 因为MOD是质数，φ(MOD)=MOD-1

def pow_mod(x, e, mod):
    """计算x^e mod mod，处理x=0的情况"""
    if x == 0:
        return 0
    res = 1
    x = x % mod
    while e > 0:
        if e % 2 == 1:
            res = res * x % mod
        x = x * x % mod
        e = e // 2
    return res

def sum_powers(a, b):
    """计算sum_{x=1}^a x^b mod MOD"""
    if a == 0:
        return 0
    # 处理指数b，利用费马小定理
    if b == 0:
        return a % MOD  # x^0=1，sum是a
    e = b % PHI
    # 当b >= PHI且x与MOD互质时，x^b ≡ x^e mod MOD；x是MOD倍数时为0
    # 计算一个周期内的和（MOD长度）
    cycle = MOD
    sum_cycle = 0
    for x in range(1, cycle):
        sum_cycle = (sum_cycle + pow_mod(x, e, MOD)) % MOD
    # 完整周期数和余数
    full_cycles = a // cycle
    rem = a % cycle
    # 完整周期的贡献
    total = full_cycles % MOD * sum_cycle % MOD
    # 余数部分的贡献
    for x in range(1, rem + 1):
        if x % MOD == 0:
            continue  # x是MOD倍数，x^b mod MOD=0
        total = (total + pow_mod(x, e, MOD)) % MOD
    return total

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    T = int(input[ptr])
    ptr += 1
    for _ in range(T):
        n = int(input[ptr])
        m = int(input[ptr + 1])
        ptr += 2
        A = []
        for __ in range(m):
            a = int(input[ptr])
            ptr += 1
            A.append(a)
        k = n
        # 计算S1 = (n+1)*f(n, n) - f(n, n+1)
        f_n_n = sum_powers(n, k)
        f_n_n1 = sum_powers(n, k + 1)
        S1 = (( (n + 1) % MOD ) * f_n_n % MOD - f_n_n1) % MOD
        # 计算S2 = sum f(a, n) for a in A
        S2 = 0
        for a in A:
            if a > n:
                continue  # 超出范围，无贡献
            fa = sum_powers(a, k)
            S2 = (S2 + fa) % MOD
        # 总得分
        ans = (S1 - S2) % MOD
        if ans < 0:
            ans += MOD
        print(ans)

if __name__ == "__main__":
    main()

复杂度分析

• 幂和计算：利用周期求和将单次幂和计算复杂度降至 ( O(\text{MOD}) )（( \text{MOD} = 10^9 + 7 )），但通过周期优化，实际对大规模 ( a ) 只需处理余数部分，效率极高。
• 总复杂度：每组测试数据处理 ( O(m \cdot \text{MOD}) )，结合 ( m \leq 50 )，可满足 ( n \leq 10^{13} ) 的数据范围。

该方法通过数学转化和模运算优化，高效解决了大规模数据下的得分计算问题。