难点在推式子
本人思路
然鹅卡死只有 $80pts$
首先发现随着步数的增加，每一维的取值范围在减小，所以暴力维护每一位取值范围，对每个步数进行计算即可， $O(nwk)$ ，实测 $35pts$ ，然后我看到 $w \le 10^9$ 猜要化式子去掉那个 $w$ ，但限于我 sb 的数学水平，并没有推出来
但想了个拆贡献的做法：一个点走了多少步后不合法一定是有一维限制了它，考虑处理出 $step[j][i]$ 表示“第 $j$ 维为 $i$ 时只考虑第 $j$ 维最多走多少步”（为了避免使用 long long ，具体存的时候可以用 pair ），然后枚举每一维的每一个值，查找其它维的 $step$ 比它大的数乘起来就是它的贡献，关于如何查找，考虑给 $step$ 排序，指针单调扫即可，时间 $O(k w \log w)$ ，卡常后可得 $80pts$
代码
1 |
|
正解
我们不难发现 $80pts$ 的思路没有前途，因为 $w \le 10^9$ ，所以 瞟一眼题解 回到 $O(nwk)$ 的思路，考虑搞掉那个 $w$
为了推式子，我们先把 $O(n w k)$ 的式子写一下，我们维护 $up[j], dw[j]$ 表示“第 $j$ 维仍在当前范围内的值的上/下界”，并记 $len[j] = up[j] - dw[j] + 1$ ，设当前步改变了第 $c_i$ 维，不难发现 $uo[j], dw[j]$ 最多只减少一个数，也就只有第 $j$ 维为那个数的点会在此步被淘汰，所以：
$$
\begin{aligned}
Ans = \sum_{i}^{n * w} (i * \prod_{j \ne c_i} len[j])
\end{aligned}
$$打表找规律 不难发现，设 $n$ 步为 $1$ 轮，则除第二轮外，每一轮到前一轮的每一维变化量相等，形式化的，记 $dt[j]$ 表示第 $j$ 维一轮的变化量，有 $第 i 轮的 len[j] = 第 2 轮的 len[j] - (i - 2) * dt[j]$ （这里第一轮特殊的原因是它每有前一轮给它的偏移量），那么就可以把步数按 $\mod n$ 分开，所以答案变成：
$$
\begin{aligned}
Ans = \sum_{i = n + 1}^{2n} \sum_{k} ((i + (k - 2)n) \prod_{j \ne c_i} (len[j] - (k - 2) dt[j]))
\end{aligned}
$$
解释一下这个式子：第一次枚举 $i$ 表示“第二轮的每一步（所以 $n + 1 \le i \le 2n$ ）”，它们代表 $\mod n$ 意义下的一类步数；然后枚举 $k$ 表示“其实是在第 $k$ 轮（注意这里和题目的 $k$ 不一样）”，这样就确定了现在是第 $i + (k - 2)n$ 步，然后乘贡献即可
不难发现，我们消去了 $w$ ，但引入了一层新的枚举，而且我们不知道 $k$ 会枚举到那里，明显会挂，继续推式子
$$
\begin{aligned}
Ans
& = \sum_{i = n + 1}^{2n} \sum_{k} ((i + (k - 2)n) \prod_{j \ne c_i} (len[j] - (k - 2) dt[j])) \\
令 x & = k - 2, 有: \\
Ans
& = \sum_{i = n + 1}^{2n} \sum_{x} ((i + x * n) \prod_{j \ne c_i} (len[j] - x * dt[j])) \\
& = \sum_{x} \sum_{i = n + 1}^{2n} ((i + x * n) \prod_{j \ne c_i} (len[j] - x * dt[j])) \\
再令 f(x) &= ((i + x * n) \prod_{j \ne c_i} (len[j] - x * dt[j])) \\
&= \sum_{i = 0}^{k} a_i x^i \\
就是要求 Ans & = \sum_{i = n + 1}^{2n} \sum_{x} f(x) \\
& = \sum_{i = n + 1}^{2n} \sum_{x} \sum_{i = 0}^{k} a_i x^i \\
& = \sum_{i = n + 1}^{2n} \sum_{i = 0}^{k} a_i \sum_{x} x^i
\end{aligned}
$$
关于上面的变形， $f(x)$ 那步需要暴力求一下多项式的卷积（用 $O(k^2)$ ），而 $x$ 的范围可以直接检查每个 $len$ 得到，然后发现 $\sum_{x} x^i$ 可以直接拉格朗日插值，总时间为 $O(n k^2)$
代码
1 |
|