dmy#14

[R3B] k 次幂之和

难度入门
时限 1s
空限 512m
数学模拟

数据规模： $1 \le n,k \le 100$ ， $1 \le A_i \le 10^9$ 。

思路

对每个 $A_i$ 循环 $k$ 次做乘法并逐次取模，累加后取模。 $n,k \le 100$ ，朴素做法足够。

复杂度：时间 $O(nk)$ ，空间 $O(1)$ 。

仓颉实现

查看仓颉实现

import std.env.*
import std.convert.*

const MOD = 998244353

main() {
    let reader = getStdIn()
    let nk = reader.readln().getOrThrow().split(" ", removeEmpty: true).map({ p => Int64.parse(p) })
    let n = nk[0]
    let k = nk[1]
    let a = reader.readln().getOrThrow().split(" ", removeEmpty: true).map({ p => Int64.parse(p) })
    var ans: Int64 = 0
    for (i in 0..n) {
        let x = a[i] % MOD
        var pw: Int64 = 1
        for (_ in 0..k) {
            pw = pw * x % MOD
        }
        ans = (ans + pw) % MOD
    }
    println(ans)
}

要点：

$A_i$ 先对模数取一次模，幂运算过程中每次乘法后立刻取模；两个小于模数的数相乘不超过 $10^{18}$ ，Int64 内不溢出。