本文共 2290 字，大约阅读时间需要 7 分钟。

为了解决这个问题，我们需要计算所有n个点的带标号简单无向图的价值之和。简单无向图的价值定义为每个点度数的k次方的和。给定n和k，我们需要对结果取模998244353。

方法思路

解决代码

MOD = 998244353def main():    import sys    input = sys.stdin.read    data = input().split()    n = int(data[0])    k = int(data[1])    n -= 1  # 减1，因为每个点的度数最多为n-1        max_k = k    # 预计算斯特林数S(k, j)    st = [[0] * (max_k + 1) for _ in range(max_k + 1)]    st[0][0] = 1    for i in range(1, max_k + 1):        for j in range(1, i + 1):            st[i][j] = (st[i-1][j-1] + j * st[i-1][j]) % MOD        # 预计算阶乘    fact = [1] * (max_k + 1)    for i in range(1, max_k + 1):        fact[i] = fact[i-1] * i % MOD        # 计算斯特林数和各项的和    res = 0    for j in range(0, min(max_k, n) + 1):        s = st[k][j]        fj = fact[j]        # 计算C(n, j)        # 使用卢卡斯定理        def comb(n, k):            res = 1            while n > 0 or k > 0:                a = n % MOD                b = k % MOD                if b > a:                    return 0                # 计算C(a, b) mod MOD                numerator = 1                for i in range(b):                    numerator = numerator * (a - i) % MOD                denominator = 1                for i in range(b):                    denominator = denominator * (i + 1) % MOD                inv_denominator = pow(denominator, MOD-2, MOD)                c = numerator * inv_denominator % MOD                res = res * c % MOD                n = n // MOD                k = k // MOD            return res                c_nj = comb(n, j)        if c_nj == 0:            continue        # 计算2^{n - j}        power = pow(2, n - j, MOD)        term = s * fj % MOD        term = term * c_nj % MOD        term = term * power % MOD        res = (res + term) % MOD        print(res % MOD)if __name__ == '__main__':    main()

代码解释

通过以上步骤，我们可以高效地计算所有n个点带标号简单无向图的价值之和，并对结果取模998244353。

转载地址：http://immu.baihongyu.com/