結果

問題 No.1097 Remainder Operation
ユーザー 草苺奶昔
提出日時 2023-02-15 16:25:51
言語 Go
(1.23.4)
結果
AC  
実行時間 249 ms / 2,000 ms
コード長 2,590 bytes
コンパイル時間 12,137 ms
コンパイル使用メモリ 229,436 KB
実行使用メモリ 69,652 KB
最終ジャッジ日時 2024-07-18 01:20:23
合計ジャッジ時間 17,507 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package main
import (
    "bufio"
    "fmt"
    "math/bits"
    "os"
)
func main() {
    // https://yukicoder.me/problems/no/1097
    const INF int = int(1e18)
    const MOD int = 998244353
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()
    var n int
    fmt.Fscan(in, &n)
    nums := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Fscan(in, &nums[i])
    }
    db := NewDoubling(n, 1e12+10)
    for i := 0; i < n; i++ {
        db.Add(i, (i+nums[i])%n, nums[i])
    }
    db.Build()
    var q int
    fmt.Fscan(in, &q)
    for i := 0; i < q; i++ {
        var k int
        fmt.Fscan(in, &k)
        _, res := db.Jump(0, k)
        fmt.Fprintln(out, res)
    }
}
type E = int
func (*Doubling) e() E          { return 0 }
func (*Doubling) op(e1, e2 E) E { return e1 + e2 }
type Doubling struct {
    n          int
    log        int
    isPrepared bool
    to         [][]int
    dp         [][]E
}
func NewDoubling(n, maxStep int) *Doubling {
    res := &Doubling{}
    res.n = n
    res.log = bits.Len(uint(maxStep))
    res.to = make([][]int, res.log)
    res.dp = make([][]E, res.log)
    for i := 0; i < res.log; i++ {
        res.to[i] = make([]int, n)
        res.dp[i] = make([]E, n)
        for j := 0; j < n; j++ {
            res.to[i][j] = -1
            res.dp[i][j] = res.e()
        }
    }
    return res
}
// 初始状态(leaves):从 `from` 状态到 `to` 状态，值变为 `value`.
//  0 <= from, to < n
func (d *Doubling) Add(from, to int, value E) {
    if d.isPrepared {
        panic("Doubling is prepared")
    }
    if to < -1 || to >= d.n {
        panic("to is out of range")
    }
    d.to[0][from] = to
    d.dp[0][from] = value
}
func (d *Doubling) Build() {
    if d.isPrepared {
        panic("Doubling is prepared")
    }
    d.isPrepared = true
    for k := 0; k < d.log-1; k++ {
        for v := 0; v < d.n; v++ {
            w := d.to[k][v]
            if w == -1 {
                d.to[k+1][v] = -1
                d.dp[k+1][v] = d.dp[k][v]
                continue
            }
            d.to[k+1][v] = d.to[k][w]
            d.dp[k+1][v] = d.op(d.dp[k][v], d.dp[k][w])
        }
    }
}
func (d *Doubling) Jump(from, step int) (to int, res E) {
    if !d.isPrepared {
        panic("Doubling is not prepared")
    }
    if step >= 1<<d.log {
        panic("step is over max step")
    }
    res = d.e()
    to = from
    for k := 0; k < d.log; k++ {
        if to == -1 {
            break
        }
        if step&(1<<k) != 0 {
            res = d.op(res, d.dp[k][to])
            to = d.to[k][to]
        }
    }
    return
}
func (d *Doubling) MaxStep(from int, check func(e E) bool) int {
    if !d.isPrepared {
        panic("Doubling is not prepared")
    }
    res := d.e()
    step := 0
    if !check(res) {
        return 0
    }
    for k := d.log - 1; k >= 0; k-- {
        to := d.to[k][from]
        next := d.op(res, d.dp[k][from])
        if check(next) {
            step |= 1 << k
            from = to
            res = next
        }
    }
    return step
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0