牛客-再编号

链接：https://ac.nowcoder.com/acm/problem/17375
来源：牛客网

题目描述

n 个人，每个人有一个编号 a_i 。

定义对 a 的再编号为 a’ ，满足：

$a'_i=(\sum_{j=1}^{n}a_j)-a_i$

现在有 m 次询问，每次给定 x,t ，表示询问经过 t 次再编号后第 x 个人的编号。

由于答案可能很大，所以对 10⁹+7 取模。

输入描述:

第一行 2 个数 n,m ，表示人数和询问次数；

接下来一行 n 个数，表示 ai；

接下来 m 行，每行 2 个数 x,t ，描述一次询问。

输出描述:

m 行，第 i 行 1 个数表示第 i 次询问的答案对 10^9+7 取模的结果。

样例输入

4 3
1 2 3 4
1 0
2 2
4 1

样例输出

1
22
6

说明

初始编号：1  2  3  4

1 次再编号后：9  8  7  6

2 次再编号后：21  22  23  24

备注

n ≤ 100000 , m ≤ 10000 , t ≤ 100000 , 1 ≤ ai ≤ 109

分析

首先简单看一眼数据范围，复杂度应该要控制在**O(NlogN)**以内。

题目要求询问m次，每次询问输出迭代第t次后位置x的值。最容易想到的是预处理存储迭代10⁵的所有结果，然后对于每次询问直接输出答案。这种方法时间复杂度是O(n²)，且需要开的数组很大，大概率会爆空间~~(我比较懒，没有仔细算)~~显然行不通。

那么，我们来研究下题目给出的公式：

$a'_i=(\sum_{j=1}^{n}a_j)-a_i$

即：

$a_{it}=(\sum_{i=1}^{n}a_{i(t-1)})-a_{i(t-1)}\\ a_{it}=S_{t-1}-a_{i(t-1)}\\$

其中a_it表示ai经过t次迭代后的值，S_t表示t次迭代后数组的总和

然后，我们很容易写出下面的推导式：

$S_{t}=nS_{t-1}\sum_{i=1}^n-a_{i(t-1)}\\ S_{t}=(n-1)S_{t-1}$

得到了一个看起来很nice的推导式。

然而，这个推导式只能优化我们算出St的效率，

搜了下大佬们写的题解，说是观察原数列得出无论经过几轮迭代，数列中相邻两个数的差的绝对值不变。我不信邪的证明了下~~（证明过程不想看的可以选择跳过）~~。

证：

$∵\quad\quad a_{it}=S_{t-1}-a_{i(t-1)} \\[8pt] ∴设\quad a_{kt}=S_{t-1}-a_{k(t-1)}\ ①,\\[8pt] \ \ a_{(k+1)t}=S_{t-1}-a_{(k+1)(t-1)}\ ②\\[8pt] ∴②-①：\quad a_{(k+1)t}-a_{kt}=\\[8pt] -(a_{(k+1)(t-1)}-a_{k(t-1)})$

同理可得：

$a_{(k+2)t}-a_{(k+1)t}=\\[8pt] -(a_{(k+2)(t-1)}-a_{(k+1)(t-1)})$

所以

$a_{(k+1)t}-a_{kt}=a_{(k+2)t}-a_{(k+1)t}$

由此可以证明，经过n次迭代后，数列中相邻两个数的差的绝对值不变，且奇数次迭代的差值为初始数列的相反数，偶数迭代与初始数相同。

进而可以得出推论：经过n次迭代后，数列中任意两个位置的数的差的绝对值不变。

这样一来，那么我们就可以预处理所有a_1t和D_i,其中**D_i**表示数列中第i个数与第一个数的差值。

对于每次询问,答案即为：

\begin{equation} ans = \left\{ \begin{aligned} an[t]-D[x] & & t为奇数\\ an[t]+D[x] & & t为偶数 \end{aligned} \right. \end{equation}

即一次询问的时间复杂度为O(1),总时间复杂度为**O(m)**可以接受。

最后还有个小细节值得注意：因为可能存在极限数据，使得an[t]-D[x]<0、an[t]=S_t-an[t-1]<0,所以对于这两种情况，取模前需要先加上模值。

代码

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=100010;
ll a[N],an[N],D[N];
int main(){
	ll n,m;
	cin>>n>>m>>a[1];
	ll sum;
	sum=a[1],D[1]=0;
	for(int i=2;i<=n;i++){
		scanf("%lld",&a[i]);
		D[i]=(a[i]-a[1]+mod)%mod;
		sum=(sum+a[i])%mod;
	}
	
	an[0]=a[1];
	for(int i=1;i<100005;i++){
		an[i]=(sum-an[i-1]+mod)%mod;
		sum=((n-1)*sum)%mod;
	}
	
	while(m--){
		int x,t;
		scanf("%lld%lld",&x,&t);
		if(t%2)printf("%lld\n",(an[t]-D[x]+mod)%mod);
		else printf("%lld\n",(an[t]+D[x])%mod);
	}
	return 0;
}

小结

1、当思路卡住时，回归样例，仔细观察规律。

2、注意减法取模，可能存在小于0的情况，保险做法是先加模数再取模。

参考资料：https://www.cnblogs.com/bljfy/p/9532789.html