链接：https://www.nowcoder.com/acm/contest/158/C
来源：牛客网
定义对 a 的再编号为 a' ，满足 。
现在有 m 次询问，每次给定 x,t ，表示询问经过 t 次再编号后第 x 个人的编号。
由于答案可能很大，所以对 109+7 取模。
输入描述:
第一行 2 个数 n,m ，表示人数和询问次数；
接下来一行 n 个数，表示 ai;
接下来 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 ≤ 109
按照题目模拟，应该可以过个$30%$吧。
我们来看一下数据会发现具有一定的规律。
初始编号：1 2 3 4 $sum0:10=1+2+3+4$
一次编号：9 8 7 6 $sum1:30=10 imes 4-1-2-3-4=sum1-sum0=sum0 imes (n-1)$
二次编号：21 22 23 24 $sum2:90=30*4-...=sum1 imes (n-1)$
从而得出规律：$$sumk=sum(k-1) imes (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[100010],n,m,con[100100]; // a[]原序列，con[]表示原序列的大小关系 LL ans[100001][2],num; //ans[i][1]表示第i次变幻1号点的大小 int main() { LL x,t; scanf("%lld%lld%lld",&n,&m,&a[1]); num=a[1]; for(int i=2;i<=n;i++) { scanf("%lld",&a[i]); num+=a[i]; con[i]=a[1]-a[i]; } ans[0][1]=a[1]; for(int i=1;i<=100001;i++) { ans[i][1]=((num-a[1])+2*mod)%mod; a[1]=ans[i][1]; //更新 num=(num*(n-1))%mod;//每次改变前缀和 } for(int i=1;i<=m;i++) { scanf("%lld%lld",&x,&t); //判断变幻的次数的奇偶 if(t%2!=0)printf("%lld ",(ans[t][1]+con[x]+mod)%mod); else printf("%lld ",(ans[t][1]-con[x]+mod/*防止出现负数取模*/)%mod); } }