题意
给定一个数列({a})
每次你需要选中一个区间([L,R])
然后对区间内每个数字进行一次操作，让(a_i)变成(a_i+k)，并且满足(k mod (R-L+1)=0)
你只能严格做三遍操作，使得最终所有数字变成(0)
限制
Time limit per test: 1 second
Memory limit per test: 256 megabytes
输入限制
(1leq nleq 10^5)
(-10^9leq a_ileq 10^9)
输出限制
(1leq l,rleq n)
(-10^{18}leq b_ileq 10^{18}, b_i mod (r-l+1)=0)
思路一（复杂版）
这个版本的思路主要是为了应对输出更为严格的限制下的题目
但本题的输出要求为(±10^{18})以内（跟没限制一样）
所以这里可能会讲得过于麻烦
只想看本题能过的简单版可以下拉到思路二
该部分输出的值可以证明一定在(±[(10^5-1)+(10^5-1) imes(10^5-1)+10^9]≈±1.1 imes10^{10})以内
进一步对正负进行讨论后可以优化到(±10^{10})以内（但我没进一步讨论qwq）
引入 1
假设(m)是奇数，那么(m-1)是偶数
对于某个数(xin [0,m-1))，可以得到((x+m) mod (m-1)=(x+1) mod (m-1))
观察到在该式子中，加上(m)的意义与加上(1)的意义相同
所以可以得到([x+(m-1-x)*m] mod (m-1)=0)
也就是对于(x)，加上(m-1-x)倍的(m)后得到的值取模(m-1)等于(0)
引入 2
假设(m)是偶数，那么(m-1)是奇数
对于某个数(xin [1,m))，可以得到([x+(m-1)] mod m=(x-1) mod m)
观察到在该式子中，加上(m-1)的意义与减去(1)的意义相同
所以可以得到([x+x*(m-1)] mod m=0)
也就是对于(x)，加上(x)倍的(m-1)后得到的值取模(m)等于(0)
得到的结论
一个数，加上一个奇数的倍数，最终肯定能表示成一个偶数的倍数
本题
根据上述结论，可以根据总长度(n)的奇偶性进行分类讨论
如果总长度(n)为奇数
①
我们可以直接拿区间([1,n])进行处理
将所有数字加上(n)（奇数）的倍数，并表示成(n-1)（偶数）的倍数
首先将数字转移到([0,n))内
tmp=(a[i]%n+n)%n;
再计算要加上多少倍，并加上这些倍数
tmp+=((n-1)-tmp)*n;
此时的(tmp)就表示成了(n-1)的倍数，且((tmp-a[i]) mod n=0)
这一步就将(a[i])变成(tmp)，输出差值(tmp-a[i])即可
②
因为上面一步将所有数字全部变成了(n-1)的倍数
那么这一步只需要选择([1,n-1])这个区间，将所有数字全部变成(0)并输出差值即可
③
最后选择([n,n])单个数字变成(0)并输出差值即可
如果总长度(n)为偶数
①
我们可以先拿区间([1,n-1])进行处理
将所有数字加上(n-1)（奇数）的倍数，并表示成(n)（偶数）的倍数
首先将数字转移到([0,n-1))内
tmp=(a[i]%(n-1)+(n-1))%(n-1);
然后直接加上倍数即可
tmp+=tmp*(n-1);
这里的操作同上，只需要输出差值(tmp-a[i])即可，并将(a[i]=tmp)
②
然后选择区间([n,n])，将这个数字直接变成(0)并输出差值即可
③
最后选择区间([1,n])，将所有数字变成(0)后输出差值即可
代码一
(93ms/1000ms)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100050];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
if(n==1)
{
puts("1 1");
printf("%lld
",-a[1]);
puts("1 1");
puts("0");
puts("1 1");
puts("0");
return 0;
}
if(n&1) //长度为奇数，选一遍消除两遍
{
printf("%d %d
",1,n);
for(int i=1;i<=n;i++)
{
if(a[i]%(n-1)==0) //已经是n-1的倍数的话则无需进行操作
printf("0 ");
else
{
ll tmp=(a[i]%n+n)%n;
tmp+=((n-1)-tmp)*n;
printf("%lld ",tmp-a[i]); //先输出差值
a[i]=tmp; //再替换
}
}
putchar('
');
printf("%d %d
",1,n-1);
for(int i=1;i<n;i++)
printf("%lld ",-a[i]); //输出相反数即可，下同
putchar('
');
printf("%d %d
",n,n);
printf("%lld
",-a[n]);
}
else //长度为偶数，选两遍消除一遍
{
printf("1 %d
",n-1);
for(int i=1;i<n;i++)
{
if(a[i]%n==0)
printf("0 ");
else
{
ll tmp=(a[i]%(n-1)+(n-1))%(n-1);
tmp+=tmp*(n-1);
printf("%lld ",tmp-a[i]);
a[i]=tmp;
}
}
putchar('
');
printf("%d %d
",n,n);
printf("%lld
",-a[n]);
a[n]=0;
printf("%d %d
",1,n);
for(int i=1;i<=n;i++)
printf("%lld ",-a[i]);
putchar('
');
}
return 0;
}
思路二（简单版）
明显的，对于某个数字(x)
(n imes x)肯定是(n)的倍数
且(n imes x-x=(n-1) imes x)，差值也肯定是(n-1)的倍数
那么只需要选择一段长度为(n-1)的区间，将所有数字乘以(n)
再将单独的那个数字变成(0)
最后将所有数字变成(0)即可
对于这种方法，输出的最大值约为(10^9 imes 10^5=10^{14})，在输出允许的范围内
代码二
(109ms/1000ms)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100050];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
if(n==1)
{
puts("1 1");
printf("%lld
",-a[1]);
puts("1 1");
puts("0");
puts("1 1");
puts("0");
return 0;
}
printf("%d %d
",1,n-1);
for(int i=1;i<n;i++)
{
printf("%lld ",a[i]*(n-1));
a[i]*=n;
}
putchar('
');
printf("%d %d
",n,n);
printf("%lld
",-a[n]);
a[n]=0;
printf("%d %d
",1,n);
for(int i=1;i<=n;i++)
printf("%lld ",-a[i]);
putchar('
');
return 0;
}