题解 CF2247B Yet Another Constructive

JuRuoOIer · 2026-07-20 14:15:31 · 题解

题解 CF2247B Yet Another Constructive

其他题

题意

给定 n,m,k，求构造一个长为 n、值域 [1,10^{18}] 的数组 a，满足其最短的和为 m 的倍数的子段长为 k，无解输出 -1。

数据范围：多测，\sum n\le 2\times 10^5。

做法

:::info[我毫无头绪。] 先判无解。 :::

首先 m<k 时无解。

反之，考虑求出前 m+1 个数模 m 意义下的前缀和，由于值域内一共就 m 个数，所以一定有重复，则重复两位置之间是长度小于 k 的合法段。

有解时放一个 m-k+1 别的全放 1 就行。

单组复杂度 O(n)。