前言
是时候多做点构造题了。
题目
题目大意：
给定三个正整数 (n,k,s)，要求构造一个长度为 (n) 的非负整数数列 (a)，满足如下要求：
-
(overset{n}{underset{i=1}{sum}}a_i=s)。
-
(a_i ge 0 (iin[1,n]))
-
(a_i = a_{i-1}-k) 或者 (a_i = a_{i-1}+1(iin[2,n]))
(1le n,kle 10^5,1le sle 10^{18})
讲解
讲解比较冗长，但请耐心看完。
part1 判断无解
首先我们需要知道一个性质：如果这个数列的第一个数定下来了，那么这个数列在模 (k+1) 意义下的和就定下来了。
证明显然，(-k) 和 (+1) 在模 (k) 意义下等价。
而我们知道整个数列的和 (s)，当然也就知道其在模 (k+1) 意义下的值，所以我们就可以根据第一个数将整个数列还原。
所以我们要先把这个数列的第一个数确定下来，我们令其为 (A)。
但在这之前我们思考一下什么情况下无解？
令由 (A) 构造出来的最小的数列和为 (S_A)。
如果 (S_A) 大于 (s)，或者 (S_A) 在模意义下不等于 (s)，那么一定无解。
否则我们一定可以构造出一组解。
part2 找A
思考如果知道了 (A)，最小的数列怎么构造？
显然是这样的：(A,A+1,A+2,...,k,0,1,...)
对于这个数列，我们可以用等差数列求和公式 (O(1)) 算出 (S_A)，而且显然 (A le k)，所以我们只需枚举 (A) 然后验证即可。
part3 构造
现在我们已经判断出了无解并求出了 (A)，考虑构造 (a)。
显然我们如果每个数同时加上 (k+1)，如果 (S_A) 依然小于等于 (s)，那么还是满足条件。
我们一定可以找个这么一个 (S_A) 使得： (S_Ale s < S_A+n*(k+1))。
也就是说这个时候不能再对整体加 (k+1) 了。
然后考虑单个加。
我们把上面我们构造出来的数列拿下来看看：(A+w*(k+1),A+1+w*(k+1),...,k+w*(k+1),0+w*(k+1),1+w*(k+1),...)
也就是：(A,A+1,A+2,...,k,0,1,...pmod{k+1})
显然我们可以这么构造：
(A+(k+1),A+1,A+2,...,k,0,1,...)(此时的 (A) 不是最开始求出来的 (A)，而是 (A+w*(k+1)))
(A+(k+1),A+1+(k+1),A+2,...,k,0,1,...)
因为 (S_A) 与 (s) 在模 (k+1) 意义下相等，且 (S_Ale S<n*(k+1))，那么我们一定可以用小于 (n) 次操作将 (S_A) 加到与 (s) 相等。
但是这个方法需要一点小优化，因为我们发现到加到 (k) 的时候不合法，也就是：
(A+(k+1),A+1+(k+1),A+2,...,k+(k+1),0,1,...)
最后一步了，你能想出来怎么解决吗？建议在这里暂停思考一下。
没错，我们只需要调换一下顺序就好了！
也就是先：
(A+(k+1),A+1+(k+1),A+2,...,k,0+(k+1),1,...)
然后：
(A+(k+1),A+1+(k+1),A+2,...,k+(k+1),0+(k+1),1,...)
你想到了吗？反正我没想到qwq。
时间复杂度 (O(n+k))。
代码
typedef long long LL;
const int MAXN = 100005;
LL n,k,s,a[MAXN],A = -1,S;
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n = Read(); k = Read(); s = Read();
for(int i = 0;i <= k && A < 0;++ i)
{
//出了一万个锅的等差数列求和
LL t1 = Min(k - i + 1,n);
S = (i + i+t1-1) * t1 / 2;
S += (n-t1) / (k+1) * ((0 + k) * (k+1) / 2);
LL fk = (n-t1) % (k+1);
S += (0 + fk-1) * fk / 2;
if(S <= s && S % (k+1) == s % (k+1)) A = i;
}
if(A < 0) {Put(-1);return 0;}
a[1] = A;
LL woc = (s - S) / (n*(k+1));//计算w
for(int i = 2;i <= n;++ i) a[i] = (a[i-1] + 1) % (k+1);
for(int i = 1;i <= n;++ i) a[i] += woc * (k+1);
S += woc * n * (k+1);
for(int i = 1;S < s;++ i)
{
S += k+1;
//判断特殊情况
if(a[i]+1 == a[i+1]) a[i] += k+1;
else
{
a[i+1] += k+1;
if(S == s) break;
a[i] += k+1;
i++;
S += k+1;
}
}
for(int i = 1;i <= n;++ i) Put(a[i],' ');
return 0;
}