Codeforces Round 924 E. Modular Sequence

本文主要是介绍Codeforces Round 924 E. Modular Sequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

E. Modular Sequence

题意

对于一个长度为 $n$ 的数组 $a$ ，定义它是 $g oo d$ 的当且仅当：

$a_1 = x$
$a_{i} = a_{i - 1} + y$ 或 $a_{i} = a_{i - 1} mod \hspace{3pt} y \quad i \geq 2$

给定 $n 、 x 、 y 、 S$ ，问能否构造出一个和为 $S$ 的长度为 $n$ 的 $g oo d$ 数组

思路

注意到后面每个放置的 $a_i$ ，它们模除 $y$ 的值都是一样的，因为自从 $a_1 = x$ 后，后面每次变化都是同余 $y$ 的。

定义 $\hspace{3pt} mod \hspace{3pt} y$ ，那么我们先将数组的 $n$ 个位置填成： $a_i = r$ ， $a_1 = x$ ，先计算一下这样子最小的数组和是否超过 $S$ ，超过的话显然没有答案。对于没有超过 $S$ 的时候，我们后面肯定是要在 $r$ 的基础上放置若干个 $y$ ，那么剩余要放置的和应该能被 $y$ 整除才行。

假设要放置 $\over y$ 个 $y$ ，我们就一定要尽可能用最短的长度构造出来这么多个 $y$ 的放置方式，考虑 $D P$ ，用 $dp_k$ 表示要从空序列开始放置 $k$ 个物品，最短需要的长度，那么转移我们可以枚举最后使用的完整上升长度 $l e n$ ，这个上升长度必须从 $0$ 开始，长度为 $l e n$ ，例如： $...., 0, 1, 2, ..., l e n - 1$ 这样一个结尾方式，那么它的子状态就是： $\frac{len \cdot (len - 1)}{2}]$ ，因为最后这一段上升序列的贡献是 $\frac{len \cdot (len - 1)}{2}$ ，长度为 $l e n$ ，我们取 $min$ 值就可以

对于多组样例，我们只需要关心最后要放置多少个 $y$ ，所以我们可以预计算 $d p$ 数组

我们先枚举一开始是否需要先跟着 $x$ 递增一段长度，然后再从 $0$ 开始构造答案，因为我们的 $d p$ 数组是从 $0$ 开始构造答案的最短长度，假设一开始从 $x$ 开始递增了 $k$ 次（不包含 $a_1$ ），也就是数组开头为： $x, x + y, x + 2 y, ..., x + k y$ ，这样子的形式，我们得先确保这个 $p re S u m$ 不会超过 $S$ ，然后在此基础上计算后面还需要放置的和的余量 $l e f tS u m = S - p re S u m$ ，当然这个余量要先预算一下后面每个位置放一个 $r$ 的花销， $\times (n - 1 - k)$ ，最后的这个 $l e f tS u m$ 不能为负数，并且要能被 $y$ 整除，还要要求 $\over y}]$ 的值小于等于 $n - 1 - k$ ，意思是我们剩余的位置必须要足够放置这么多个 $y$ ，我们才能在这个基础上构造答案

如果上述条件都符合，我们现在中间多余的用不上的位置 $\over y}]]$ 先填补上 $r$ ，然后从 $\over y}] + 1$ 这个位置开始构造答案，我们用一个 $l e n$ 数组来暂存一下我们的答案构造的上升长度序列，枚举转移的路径即可

时间复杂度： $\sqrt{S})$

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;const int INF=0x3f3f3f3f;
const long long INFLL=1e18;typedef long long ll;const int N = 200050;int dp[N];void solve(){int n;ll x, y, S;std::cin >> n >> x >> y >> S;fore(k, 0, n){ //除了首项x外，后面还跟着递增了k次ll preSum = (k + 1) * x + k * (k + 1) / 2 * y; //前缀和if(preSum > S) continue;ll leftSum = S - preSum; //后面需要构造的和leftSum -= (n - 1 - k) * (x % y); //先减去模数 x % yif(leftSum < 0 || leftSum % y) continue;int needSum = leftSum / y; //后面需要多少个yif(dp[needSum] > n - k - 1) continue; //长度不够构造std::vector<int> a(n);a[0] = x; //首项fore(i, 1, k + 1) a[i] = a[i - 1] + y; //起初跟着长度为k的一个递增fore(i, k + 1, n - dp[needSum]) a[i] = x % y; //中间这里用不上，我们在 n - dp[needSum] -> n - 1构造int idx = n - dp[needSum];std::vector<int> len;while(needSum){for(int l = 2; l * (l - 1) / 2 <= needSum; ++l)if(dp[needSum] == dp[needSum - l * (l - 1) / 2] + l){ //这是一个最短长度的转移len.push_back(l); //记录构成最短长度的转移needSum -= l * (l - 1) / 2; //剩余需要放置的y的数量break;}}for(auto l : len) //按照答案转移放置yfore(j, 0, l) //从0开始放置，放 l 次a[idx++] = x % y + j * y; //记住底是 x % ystd::cout << "YES\n";for(auto el : a) std::cout << el << ' ';std::cout << endl;return;}std::cout << "NO\n";
}int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);fore(i, 1, N) dp[i] = INF;fore(k, 1, N)   //dp[i] 表示要放 i 个 y 需要的最短长度是多长for(int len = 2; len * (len - 1) / 2 <= k; ++len) //这里len是从0开始放的，所以最后一位是len - 1，长度为lendp[k] = std::min(dp[k], dp[k - len * (len - 1) / 2] + len);int t;std::cin >> t;while(t--){solve();}return 0;
}