题解：CF1968C Assembly via Remainders

原题链接

• 洛谷 CF1968C Assembly via Remainders

题意简述

给定长度为 $n-1$ 的数列 $x_i$，构造长度为 $n$ 的数列 $a_i$，满足 $x_i=a_i \bmod a_{i-1}$。

解题思路

令 $a_i=a_{i-1}+x_i$，此时：

$$\begin{aligned} x_i &= a_i \bmod a_{i-1} \\ &= (a_{i-1}+x_i) \bmod a_{i-1} \\ &= a_{i-1} \bmod a_{i-1} + x_i \bmod a_{i-1} \\ &= x_i \bmod a_{i-1} \end{aligned}$$

不难发现，当 $a_{i-1}$ 较大时即可满足条件。

由于 $x_i \le 500$，$a_i \le 10^9$，所以不妨令 $a_1$ 为一个较大的数。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=200005;
int x[N],a[N];
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		for(int i=2;i<=n;i++)
		{
			cin>>x[i];
		}
		a[1]=114514;
		for(int i=2;i<=n;i++)
		{
			a[i]=a[i-1]+x[i];
		}
		for(int i=1;i<=n;i++)
		{
			cout<<a[i]<<' ';
		}
		cout<<'\n';
	}
	return 0;
}