出题人题解 | #再编号#

原题解链接：https://ac.nowcoder.com/discuss/149978

定义 $\operatorname{sum}(a)=\sum_{i=1}^{n} a_{i}$ ，考虑计算 $\operatorname{sum}\left(a^{\prime}\right)$ 。

\operatorname{sum}\left(a^{\prime}\right)=\sum_{i=1}^{n} a_{i}^{\prime}=\sum_{i=1}^{n}\left(\operatorname{sum}(a)-a_{i}\right)=\left(\sum_{i=1}^{n} \operatorname{sum}(a)\right)-\left(\sum_{i=1}^{n} a_{i}\right)=(n-1) \operatorname{sum}(a)

定义 $a_{t}(x)$ 表示经过 $t$ 次再编号后第 $x$ 个人的编号， $s u m_{t}$ 表示 $t$ 次再编号的编号和，

则当 $t > 0$ 时，有 $a_{t}(x)=\operatorname{sum}_{t-1}-a_{t-1}(x)$ 。

对这个式子暴力展开，可得 $a_{t}(x)=\left(\sum_{i=0}^{t-1}(-1)^{i} \operatorname{sum}_{t-1-i}\right)+(-1)^{t} a_{0}(x)$ 。

因为 $s u m_{t}=(n-1) \operatorname{sum}_{t-1}$ ，所以左边是个公比 $q$ 为 $- (n - 1)$ ，首项为 $(-1)^{t-1} \operatorname{sum}_{0}$ 的等比数列。

考虑等比数列求和公式，预处理 $q^{i} ，(q-1)^{-1}$ 就可以 $O (1)$ 计算了。

实际上可以更暴力，预处理首项为 1 ，公比为 $q$ 的等比数列的前缀和，用的时候乘上 $(-1)^{t-1} \operatorname{sum}_{0}$ 就好了。

时间复杂度 $O (n + m + t)$ 。

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

typedef long long s64;
#define rep(i,l,r) for(int i=l;i<=r;++i)
const int N=1e5+5,D=1e9+7;
int a[N];
s64 sum[N];

int main()
{
	//freopen("1.in","r",stdin);
	int n,m;
	cin>>n>>m;
	rep(i,1,n)scanf("%d",a+i);
	
	int sum0=0;
	rep(i,1,n)(sum0+=a[i])%=D;
	
	s64 q=-(n-1),x=1;	
	sum[0]=x;
	rep(i,1,N-1)
	{
		x=x*q%D; 
		sum[i]=(sum[i-1]+x)%D;
	}
	
	while(m--)
	{
		int x,t;
		scanf("%d%d",&x,&t);
		printf("%d\n",int(((-sum[t-1]*sum0+a[x])*(t%2?-1:1)%D+D)%D));
	}
}