No.2580 Hyperinflation
タグ : / 解いたユーザー数 14
作問者 :
akakimidori
/ テスター :
noshi91
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Show the original
Problem Statement
You are given an integer sequence $A = (A_1, \ldots, A_{N - 1})$ of length $N-1$.
Define an integer sequence $B = (B_0, B_1, \ldots, B_{N - 1})$ of length $N$ by $B_0 = 1, B_i = A_iB_{i - 1} (1 \leq i < N)$.
Given an integer $M$, find the number of non-negative integer sequences $C = (C_0, C_1, \ldots, C_{N - 1})$ of length $N$ satisfying the following equation. $$ \displaystyle \sum_{i = 0}^{N-1} B_i C_i = M $$ Since the answer can be very large, find it modulo $998244353$.
Input
$N$
$A_1\ \cdots\ A_{N - 1}$
$M$
- $1 \leq N \leq 2000$
- $2 \leq A_i \leq 2000 (1 \leq i < N)$
- $1 \leq M < 10^{7000}$
- All inputs are integers.
Output
Output the answer modulo $998244353$. End the output with a newline.
Sample
Sample 1
Input
3 2 2 5
Output
4
We have $B = (1, 2, 4)$. There are $4$ sequences $C$ satisfying the condition: $(1, 0, 1), (1, 2, 0), (3, 1, 0), (5, 0, 0)$.
Sample 2
Input
1 13
Output
1
Note that the input may contain an empty line.
Sample 3
Input
7 6 2 8 5 8 2 866311
Output
770044952
Output the answer modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。