题解

问题分析

题目要求计算从酒店出发，经过所有景点恰好一次后返回酒店的旅行方案中，劳累值最大值低于 ( w ) 的方案数。劳累值定义为两个相邻景点权值的乘积，整个旅途的劳累值是所有相邻乘积的最大值。

关键观察：

1. 权值为正和负的景点相邻时，乘积为负，而 ( w ) 是非负数，因此这类乘积一定小于 ( w )，无需额外限制。
2. 权值同号（均正或均负）的景点相邻时，乘积为正，需满足乘积小于 ( w ) 才合法。
3. 完全交替排列（正负交替）的方案中，所有相邻乘积均为负，一定合法。
4. 存在同号相邻的方案需保证所有同号相邻的乘积均小于 ( w )。

核心思路

1. 分类与排序：将景点分为负数（取绝对值）和正数两类，分别记为数组 ( A )（负数绝对值）和 ( B )（正数），并排序（便于后续双指针判断乘积是否合法）。
2. 生成函数构建：
   • 对 ( A ) 和 ( B ) 分别计算生成函数，用于表示将对应类别元素排列时，满足“同号相邻乘积小于 ( w )”的方案数系数（记为 ( f ) 和 ( g )）。
   • 生成函数的构建通过双指针确定合法相邻元素范围，结合多项式乘法（NTT 优化）高效计算。
3. 方案数计算：
   • 完全交替排列的方案数：根据正负元素数量差异（不超过1）直接计算。
   • 非完全交替排列的方案数：通过生成函数系数 ( f ) 和 ( g ) 组合计算，即所有满足同号相邻乘积限制的排列数。

代码解析

1. 预处理：初始化阶乘、逆阶乘、NTT 所需的单位根等，用于后续组合数和多项式运算。
2. 分类与排序：将输入的权值分为负数（取绝对值）和正数，分别排序。
3. 生成函数计算（solve 函数）：
   • 用双指针确定同号元素中可相邻的范围（乘积 ≤ ( w )）。
   • 通过优先队列合并多项式，结合 NTT 计算生成函数，最终得到系数 ( f )（对应负数）和 ( g )（对应正数）。
4. 答案合成：汇总完全交替和非完全交替的合法方案数，公式为 ( \sum (2 \cdot f[i] \cdot g[i] + f[i+1] \cdot g[i] + f[i] \cdot g[i+1]) )，模 998244353 后输出。