\(\textbf{Problem Statement}\)
给定 \(n,x,y,s\)，构造长度为 \(n\) 的序列 \(a\)，满足：
-
\(a_1 = x\)。
-
\(\forall i \in [2,n],a_i = a_{i-1} + y\) 或者 \(a_i = a_{i-1} \bmod y\)。
-
\(\sum \limits_{i=1}^n a_i = s\)。
给出构造或报告无解。\(\sum n,\sum s \le 2 \cdot 10^5\)。
\(\textbf{Hints}\)
\(\textbf{Hint 1}\)
令 \(p = s - n \cdot (x \bmod y)\)，如果 \(p \bmod y \ne 0\)，这个问题可能有解吗？
\(\textbf{Hint 2}\)
令 \(s = \dfrac{p}{y}\)，问题等价于构造序列 \(a\)，使得 \(a_1 = x\)，\(\forall i \in [2,n],a_i = a_{i-1}+1\) 或 \(a_i = 0\)，且 \(\sum \limits_{i=1}^n a_i = s\)。
\(\textbf{Hint 3}\)
解决 \(x < y\) 的情况。\(x \ge y\) 的情况可以简单转化。
\(\textbf{Hint 4}\)
当 \(x < y\) 时，鉴于你可以填 \(0\)，你只需要关心拼出一个整数 \(q\) 最小需要几个数字。
\(\textbf{Hint 5}\)
可以用最短路解决，相信你的常数。
\(\textbf{Solution}\)
先阅读完所有提示。
我们来解决 \(x < y\) 的情况，此时我们关心拼出整数 \(q\) 最少需要几个数字。考虑图论建模，对于数字 \(i\)，向 \(x = i+\sum\limits_{j=1}^k j\) 连边权为 \(k+1\) 的边，表示从 \(i\) 到 \(x\) 需要 \(k+1\) 个新的数字，容易发现边数为 \(\mathcal O(n \sqrt n)\) 级别。跑一边 dij 即可得到拼出每个整数的最少代价，复杂度 \(\mathcal O(n \sqrt n \log n)\)。
然后我们就 \(\mathcal O(1)\) 解决了 \(x < y\) 的情况，对于 \(x \ge y\) 的情况，我们只需要枚举第一部分填几个数字，然后就转化成了 \(x < y\) 的情况。
构造答案只需要记录最短路方案，这也是容易完成的。回答每组询问的时间复杂度是 \(\mathcal O(n)\)，可以通过。
代码。
标签：limits,Hint,题解,sum,textbf,CF1928E,mathcal,bmod From： https://www.cnblogs.com/sunkuangzheng/p/18013450