#PQJ2294x13455. QOJ 2294_13455
QOJ 2294_13455
标题: Tour - Problem - QOJ.ac
#13455. Tour
The problem was used in the following contests:
小 W 决定来一次毕业旅行,他来到了 T 市,T 市有 n 个景点,他想要从酒店出发,恰好经过每个景点一次之后回到酒店。
但是小 W 不想让自己太累,具体地说,在 从一个景点移动到另外一个景点的时候,小 W 会感受到劳累。具体来说,每个景点有一个 整数 权值 vi 如果从第 i 个景点走到第 j 个景点,则小 W 的劳累值是 vi×vj,整个旅途的劳累值是移动时的劳累值的最大值。
小 W 不想让自己太累,于是他想要找到一个旅行方案,旅途中的劳累值低于一个 非负整数 w,但是他觉得这个问题对你来说太简单了,所以他想询问总共有多少种不同的旅行方案满足条件,对 998244353 取模。
输入格式
第一行两个数 n,w 分别表示景点个数以及劳累值的限制。
第二行 n 个整数 vi 分别表示每个景点的权值。
输出格式
一行一个整数表示答案。
样例数据
样例 1 输入
3 3
1 2 3
样例 1 输出
2
样例 2 输入
6 5
1 1 4 5 1 4
样例 2 输出
144
样例 3 输入
16 20
-1 9 -9 9 -1 3 -9 2 -8 4 -1 4 0 8 5 3
样例 3 输出
802901549
子任务
对于所有数据,0≤w,|ai|≤109,1≤n≤200000。
subtask 1 (10 pts) :n≤200,ai≥0
subtask 2 (10 pts) :n≤2000,ai≥0
subtask 3 (10 pts) :n≤50000,ai≥0
subtask 4 (10 pts) :n≤200000,ai≥0
subtask 5 (10 pts) :n≤200
subtask 6 (10 pts) :n≤2000
subtask 7 (20 pts) :n≤50000
subtask 8 (20 pts) :n≤200000