#1931. Tour

    ID: 1931 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>CTT赛事:contest2294来源:qoj.ac数据:公开样例枚举

Tour

Tour

题目描述

标题: Tour - Problem - QOJ.ac

#13455. Tour

Statistics

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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 3
1 2 3
2

样例 2

6 5
1 1 4 5 1 4
144