#V. Sugoroku 3

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l
    Type: RemoteJudge 2000ms 256MiB

Sugoroku 3

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面翻译

题目描述

一共有 NN 个格子编号 11 到 NN。有一个人站在 11 号格子。

对于 ∀i∈[1,N−1]\forall i \in [1,N-1] 号格子有一个 Ai+1A_i + 1 面的骰子，写有 00 到 AiA_i 这些数。如果 ta 掷到了 kk，他将往前走 kk 格，走到 i+ki+k 号方格。

求走到 NN 号方格的期望次数。对 998244353998244353 取模。

输入格式

第一行一个正整数 NN，第二行 N−1N-1 个正整数表示 AiA_i。

输出格式

如果期望次数为 PQ\frac{P}{Q}，输入最小非负整数 RR 使得 R×Q≡P(mod998244353)R\times Q \equiv P\pmod {998244353}。

数据范围

2≤N≤2×1052\leq N\leq 2\times 10^5

∀i∈[1,N−1],1≤Ai≤N−i\forall i \in [1,N-1],1\leq A_i\leq N-i

题目描述

マス 1 1 からマス N N の N N 個のマスがあります。はじめ、あなたはマス 1 1 にいます。

また、マス 1 1 からマス N−1 N-1 にはそれぞれサイコロが置いてあります。マス i i のサイコロは 0 0 以上 Ai A_i 以下の整数を等確率にランダムで出します。(サイコロを振る操作は毎回独立です。)

あなたは、マス N N に到達するまで、現在いるマスに置かれているサイコロを振り、出た目の数だけ進むことを繰り返します。厳密に言うと、マス X X にいるときにサイコロで Y Y が出た場合はマス X+Y X+Y に移動します。

サイコロを振る回数の期待値  mod  998244353 \bmod\ 998244353 を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

N N A1 A_1 A2 A_2 … \dots AN−1 A_{N-1}

输出格式

答えを出力せよ。

样例 #1

样例输入 #1

3
1 1

样例输出 #1

4

样例 #2

样例输入 #2

5
3 1 2 1

样例输出 #2

332748122

提示

注記

求める期待値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な 2 2 つの整数 P P , Q Q を用いて PQ \frac{P}{Q} と表したとき、R × Q ≡ P(mod998244353) R\ \times\ Q\ \equiv\ P\pmod{998244353} かつ 0 ≤ R < 998244353 0\ \leq\ R\ \lt\ 998244353 を満たす整数 R R がただ一つ存在することが証明できます。この R R を求めてください。

制約

  • 2 ≤ N ≤ 2 × 105 2\ \le\ N\ \le\ 2\ \times\ 10^5
  • 1 ≤ Ai ≤ N−i(1 ≤ i ≤ N−1) 1\ \le\ A_i\ \le\ N-i(1\ \le\ i\ \le\ N-1)
  • 入力は全て整数。

Sample Explanation 1

求める期待値は 4 4 であるため、4 4 を出力します。 マス N N に到達するまでの流れとしては、以下のようなものが考えられます。 - マス 1 1 で 1 1 を出し、マス 2 2 に移動する。 - マス 2 2 で 0 0 を出し、移動しない。 - マス 2 2 で 1 1 を出し、マス 3 3 に移動する。 このようになる確率は 18 \frac{1}{8} です。

北辰OI提高组第2周序列问题课后练习题👍

Not Attended
Status
Done
Rule
IOI
Problem
44
Start at
2024-1-7 16:00
End at
2024-2-18 8:00
Duration
1000 hour(s)
Host
Partic.
15
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. text

  4. 鲁公网安备 37079402001599号

  • 鲁ICP备2022025036号-1
  • Worker 0, 45ms
  • Powered by Hydro v4.9.27 Community