結果

問題 No.1097 Remainder Operation
コンテスト
ユーザー 草苺奶昔
提出日時 2023-06-17 02:07:26
言語 TypeScript
(5.7.2)
結果
WA  
実行時間 -
コード長 3,953 bytes
コンパイル時間 7,951 ms
コンパイル使用メモリ 231,256 KB
実行使用メモリ 136,668 KB
最終ジャッジ日時 2024-12-31 16:54:41
合計ジャッジ時間 31,259 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 14 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

/**
 * 倍增维护`n`个状态的转移编号和值.
 * 每个状态对应一个`编号(0-n-1)`和`值(幺半群)`.
 * 从状态`a`转移一次到达状态`b`，状态`b`对应的值与`边权`进行结合运算.
 */
class Doubling<E> {
  private readonly _n: number
  private readonly _log: number
  private readonly _e: () => E
  private readonly _op: (e1: E, e2: E) => E
  private readonly _to: Int32Array
  private readonly _dp: E[]
  private _isPrepared = false

  /**
   * @param n 状态的数量.
   * @param maxStep 最大的转移次数.
   * @param e 转移边权的单位元.
   * @param op 转移边权的结合律运算.
   */
  constructor(n: number, maxStep: number, e: () => E, op: (e1: E, e2: E) => E) {
    this._n = n
    this._log = 1
    while (2 ** this._log <= maxStep) this._log++
    this._e = e
    this._op = op

    const size = n * this._log
    this._to = new Int32Array(size)
    this._dp = Array<E>(size)
    for (let i = 0; i < size; i++) {
      this._to[i] = -1
      this._dp[i] = e()
    }
  }

  /**
   * 初始状态(leaves):从 `from` 状态到 `to` 状态，边权为 `weight`.
   * 0 <= from, to < n.
   */
  add(from: number, to: number, weight: E): void {
    if (this._isPrepared) throw new Error('Doubling is prepared')
    if (to < -1 || to >= this._n) throw new RangeError('to is out of range')
    this._to[from] = to
    this._dp[from] = weight
  }

  build(): void {
    if (this._isPrepared) return
    this._isPrepared = true
    const n = this._n
    for (let k = 0; k < this._log - 1; k++) {
      for (let v = 0; v < n; v++) {
        const w = this._to[k * n + v]
        const next = (k + 1) * n + v
        if (w === -1) {
          this._to[next] = -1
          this._dp[next] = this._dp[k * n + v]
          continue
        }
        this._to[next] = this._to[k * n + w]
        this._dp[next] = this._op(this._dp[k * n + v], this._dp[k * n + w])
      }
    }
  }

  /**
   * 从 `from` 状态开始，执行 `step` 次操作，返回最终状态的编号和值.
   * 0 <= from < n.
   * 如果最终状态不存在，返回 [-1, e()].
   */
  jump(from: number, step: number): [to: number, value: E] {
    if (!this._isPrepared) this.build()
    if (step >= 2 ** this._log) throw new RangeError('step is over max step')
    let value = this._e()
    let to = from
    for (let k = 0; k < this._log; k++) {
      if (to === -1) break
      const div = 2 ** k
      if (Math.floor(step / div) % 2) {
        const pos = k * this._n + to
        value = this._op(value, this._dp[pos])
        to = this._to[pos]
      }
    }
    return [to, value]
  }

  /**
   * 求从 `from` 状态开始转移 `step` 次，满足 `check` 为 `true` 的最大的 `step`.
   * 0 <= from < n.
   */
  maxStep(from: number, check: (e: E) => boolean): number {
    if (!this._isPrepared) this.build()
    let res = this._e()
    let step = 0
    for (let k = this._log - 1; ~k; k--) {
      const pos = k * this._n + from
      const to = this._to[pos]
      const next = this._op(res, this._dp[pos])
      if (check(next)) {
        step += 2 ** k
        from = to
        res = next
      }
    }
    return step
  }
}


import * as fs from 'fs'
import { resolve } from 'path'


function useInput(path?: string) {
  let data: string
  if (path) {
    data = fs.readFileSync(resolve(__dirname, path), 'utf8')
  } else {
    data = fs.readFileSync(process.stdin.fd, 'utf8')
  }

  const lines = data.split(/\r\n|\r|\n/)
  let lineId = 0
  const input = (): string => lines[lineId++]

  return {
    input
  }
}

const { input } = useInput()

const n = Number(input())

const D = new Doubling(
  n,
  1e12 + 10,
  () => 0,
  (a, b) => a + b
)

const nums = input().split(' ').map(Number)
for (let i = 0; i < n; i++) {
  D.add(i, (i + nums[i]) % n, nums[i])
}

const q = Number(input())
for (let i = 0; i < q; i++) {
  const step = Number(input())
  const [_, value] = D.jump(0, step)
  console.log(value)
}
0