#1783. 没有创意的题目名称
没有创意的题目名称
没有创意的题目名称
题目描述
标题: 没有创意的题目名称 - Problem - QOJ.ac
#7650. 没有创意的题目名称
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