题解 | #再编号#

考察知识点：前缀和

定义 $sum(a)=\sum\limits_{i=1}^{n} a_i$ ，考虑计算 $s u m (a^{'})$ 。

sum(a') = \sum\limits_{i=1}^{n} a'_i = \sum\limits_{i=1}^{n} (sum(a)-a_i) = \sum\limits_{i=1}^{n} sum(a) - \sum\limits_{i=1}^{n} a_i = (n-1)sum(a)

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

当 $t > 0$ 时，有：

a_t(x) = {sum}_{t-1}-a_{t-1}(x)

由此递推公式可得 $a_{t} (x)$ 的通项：

a_t(x) = \sum\limits_{i=0}^{t-1} (-1)^i {sum}_{t-1-i} + (-1)^t a_0(x)

因为 ${sum}_t=(n-1){sum}_{t-1}$ ，所以 $\sum\limits_{i=0}^{t-1} (-1)^i {sum}_{t-1-i}$ 事实上是一个等比数列，且有如下关系：

\sum\limits_{i=0}^{t-1} (-1)^i {sum}_{t-1-i} = {sum}_{t-1} - \sum\limits_{i=0}^{t-2} (-1)^i {sum}_{t-2-i}

使用前缀和预处理 ${sum}_i$ 和 $\sum\limits_{i=0}^{t-1} (-1)^i {sum}_{t-1-i}$ ，即为程序中的 s[i] 和 p[i]。

然后根据 t 的奇偶性，计算出 $a_{t} (x)$ 的值即可。

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

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

#define MOD 1000000007
#define N 100005

void solve()
{
    int n, m;
    cin >> n >> m;
    ll a[N], s[N] = {0}, p[N] = {0};
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        s[0] = (s[0] + a[i]) % MOD;
    }
    for (int i = 1; i <= 100000; i++)
    {
        s[i] = ((n - 1) * s[i - 1] % MOD) % MOD;
        p[i] = (s[i - 1] - p[i - 1] + MOD) % MOD;
    }
    while (m--)
    {
        int x, t;
        cin >> x >> t;
        if (t == 0)
            cout << a[x] << endl;
        else if (t % 2)
            cout << (p[t] - a[x] + MOD) % MOD << endl;
        else
            cout << (p[t] + a[x]) % MOD << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}