#1783. 没有创意的题目名称

    ID: 1783 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1401来源:qoj.ac数据:公开样例动态规划

没有创意的题目名称

没有创意的题目名称

题目描述

标题: 没有创意的题目名称 - Problem - QOJ.ac

#7650. 没有创意的题目名称

Statistics

The problem was used in the following contests:

题目描述

给定一个正整数 n 和一个长度为 n+1 的序列 lim0,lim1,lim2,…,limn,求长度为 n+1 的整数序列 f0,f1,f2,…,fn 的方案数,使得以下条件成立。

  • 对于所有 0≤i≤n,有 0≤fi≤limi。
  • 对于任意 0≤m≤n 满足,对于所有 0≤i≤m,有 ffi+fm−i=fm。(当 i>n 时,fi=−1)

答案对 998244353 取模。

输入格式

输入共两行。

第一行一个正整数 n,表示序列长度为 n+1。

第二行 n+1 个正整数,分别表示 lim0,lim1,…,limn。

输出格式

输出共一行。

第一行一个整数,表示符合要求的序列个数对 998244353 取模的结果。

样例一

input
2
2 2 2
output
6
explanation

符合要求的方案有:[0,0,0],[0,1,0],[0,1,1],[0,1,2],[1,0,1],[1,1,1]。

样例二

input
5
1 1 4 5 1 4
output
8

样例三

input
10
0 1 2 3 4 5 6 7 8 9 10
output
56

数据范围

下发文件中有 Unix 格式的样例。

对于 100% 的数据,有 1≤n≤2000,0≤limi≤n。

共 20 个测试点,各个测试点的数据范围如下:

测试点编号n≤其他约束11无25无315无430无550无670无7100无8200无9100lim0=010500lim0=0112000lim0=0122000lim0=0 且 limi≤5132000limi≤5142000limi≤2015∼162000limi=i17∼202000无

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2
2 2 2
6

样例 2

5
1 1 4 5 1 4
8