链接：https://www.nowcoder.com/acm/contest/158/C
来源：牛客网
定义对 a 的再编号为 a' ，满足 。
现在有 m 次询问，每次给定 x,t ，表示询问经过 t 次再编号后第 x 个人的编号。
由于答案可能很大，所以对 10+7 取模。
输入描述:
第一行 2 个数 n,m ，表示人数和询问次数；
接下来一行 n 个数，表示 a;
接下来 m 行，每行 2 个数 x,t ，描述一次询问。
输出描述:
m 行，第 i 行 1 个数表示第 i 次询问的答案对 109+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 ≤ a ≤ 10
按照题目模拟，应该可以过个$30%$吧。
我们来看一下数据会发现具有一定的规律。
初始编号：1 2 3 4 $sum0:10=1+2+3+4$
一次编号：9 8 7 6 $sum1:30=10 \times 4-1-2-3-4=sum1-sum0=sum0 \times (n-1)$
二次编号：21 22 23 24 $sum2:90=30*4-...=sum1 \times (n-1)$
从而得出规律：$$sumk=sum(k-1) \times (n-1)$$
这样我们则可以在线性时间内求出每次变换序列的和，这显然还不足以得出答案。
现在我们在考虑如何查询x位置上的数？
拿二位数组储存明显会MLE，所以我们再观察一下序列，会发现序列存在一定的关系。
就那每次变化第一个数为例,每一行其他的数减第一个数绝对值相等，在更深入考虑一下，为什么？
每次我们的序列元素是由同一个相同的数减来的，所以相对大的数变小，相对小的数变大，但是他们的差值不变。
初始编号：逐渐递增。与1位置数相减序列为 0 1 2 3
一次编号：逐渐递减。与1位置数相减序列为 0 -1 -2 -3
二次编号：逐渐递增。... 0 1 2 3
所以我们可以发现在偶数次变化后序列大小关系与原序列相同，奇数次相反。
从而我们可以预处理时记录下每一次变化一号位置的数，从而根据大小关系的出x号点的大小。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
#define LL long long
#define mod int(1e9+7)
LL a[],n,m,con[]; // a[]原序列，con[]表示原序列的大小关系
LL ans[][],num; //ans[i][1]表示第i次变幻1号点的大小
int main()
{
LL x,t;
scanf("%lld%lld%lld",&n,&m,&a[]);
num=a[];
for(int i=;i<=n;i++)
{
scanf("%lld",&a[i]);
num+=a[i];
con[i]=a[]-a[i];
}
ans[][]=a[];
for(int i=;i<=;i++)
{
ans[i][]=((num-a[])+*mod)%mod;
a[]=ans[i][]; //更新
num=(num*(n-))%mod;//每次改变前缀和
}
for(int i=;i<=m;i++)
{
scanf("%lld%lld",&x,&t);
//判断变幻的次数的奇偶
if(t%!=)printf("%lld\n",(ans[t][]+con[x]+mod)%mod);
else printf("%lld\n",(ans[t][]-con[x]+mod/*防止出现负数取模*/)%mod); }
}