QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100
Statistics

题目描述

给定一个正整数 $ n $ 和一个长度为 $ n+1 $ 的序列 $ lim_0,lim_1,lim_2,\dots,lim_n $,求长度为 $ n+1 $ 的整数序列 $ f_0,f_1,f_2,\dots,f_n $ 的方案数,使得以下条件成立。

  • 对于所有 $ 0\le i\le n $,有 $ 0\le f_i\le lim_i $。
  • 对于任意 $ 0\le m\le n $ 满足,对于所有 $ 0\le i\le m $,有 $ f_{f_i+f_{m-i}}=f_m $。(当 $ i>n $ 时,$ f_i=-1 $)

答案对 $ 998244353 $ 取模。

输入格式

输入共两行。

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

第二行 $ n+1 $ 个正整数,分别表示 $ lim_0,lim_1,\dots,lim_n $。

输出格式

输出共一行。

第一行一个整数,表示符合要求的序列个数对 $ 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\le n\le 2000, 0\le lim_i\le n $。

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

测试点编号$ n\le $其他约束
$ 1 $$ 1 $
$ 2 $$ 5 $
$ 3 $$ 15 $
$ 4 $$ 30 $
$ 5 $$ 50 $
$ 6 $$ 70 $
$ 7 $$ 100 $
$ 8 $$ 200 $
$ 9 $$ 100 $$ lim_0=0 $
$ 10 $$ 500 $$ lim_0=0 $
$ 11 $$ 2000 $$ lim_0=0 $
$ 12 $$ 2000 $$ lim_0=0 $ 且 $ lim_i\le 5 $
$ 13 $$ 2000 $$ lim_i\le 5 $
$ 14 $$ 2000 $$ lim_i\le 20 $
$ 15\sim 16 $$ 2000 $$ lim_i=i $
$ 17\sim 20 $$ 2000 $