#P6532. 「2020-2021 集训队作业」Tour

    ID: 6011 传统题 2000ms 512MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>CF3100NOI/NOI+/CTS相向双指针极端元素优先处理递推计数分治乘积卷积转化二项式反演NTT阶乘逆元预处理组合计数

「2020-2021 集训队作业」Tour

题目描述

小 W 决定来一次毕业旅行,他来到了 T 市,T 市有 nn 个景点,他想要从酒店出发,恰好经过每个景点一次之后回到酒店。

但是小 W 不想让自己太累,具体地说,在 从一个景点移动到另外一个景点的时候,小 W 会感受到劳累。具体来说,每个景点有一个 整数 权值 viv_i 如果从第 ii 个景点走到第 jj 个景点,则小 W 的劳累值是 vi×vjv_i\times v_j,整个旅途的劳累值是移动时的劳累值的最大值。

小 W 不想让自己太累,于是他想要找到一个旅行方案,每次在相邻景点之间移动时的劳累值都不超过非负整数 ww,但是他觉得这个问题对你来说太简单了,所以他想询问总共有多少种不同的旅行方案满足条件,对 998244353998244353 取模。

输入格式

第一行两个数 n,wn,w 分别表示景点个数以及劳累值的限制。

第二行 nn 个整数 viv_i 分别表示每个景点的权值。

输出格式

输出一个整数,表示合法景点访问顺序的数量对 998244353998244353 取模的结果。不同景点按编号区分,即使权值相同。

3 3
1 2 3
2
6 5
1 1 4 5 1 4
144
16 20
-1 9 -9 9 -1 3 -9 2 -8 4 -1 4 0 8 5 3
802901549

数据范围与提示

对于所有数据,0≤w,∣vi∣≤1090 \le w, |v_i| \le 10^9 ,1≤n≤2000001 \le n \le 200000。

subtask 1 (10 pts) \textbf{subtask 1 (10 pts) }:n≤200n\le 200 ,vi≥0v_i\ge 0

subtask 2 (10 pts) \textbf{subtask 2 (10 pts) }:n≤2000n\le 2000,vi≥0v_i\ge 0

subtask 3 (10 pts) \textbf{subtask 3 (10 pts) }:n≤50000n\le 50000,vi≥0v_i \ge 0

subtask 4 (10 pts) \textbf{subtask 4 (10 pts) }:n≤200000n\le 200000,vi≥0v_i \ge 0

subtask 5 (10 pts) \textbf{subtask 5 (10 pts) }:n≤200n\le 200

subtask 6 (10 pts) \textbf{subtask 6 (10 pts) }:n≤2000n\le 2000

subtask 7 (20 pts) \textbf{subtask 7 (20 pts) }:n≤50000n\le 50000

subtask 8 (20 pts) \textbf{subtask 8 (20 pts) }:n≤200000n\le 200000

原赛题(QOJ 13455)