题解 | #再编号#

考察知识点：前缀和

定义 $sum(a)={\sum }_{i=1}^n{a}_{i}sum(a)=\backslash sum\backslash limits\_\{i=1\}^\{n\}\; a\_i$，考虑计算 $sum(a^{\mathrm{\prime }})sum(a\text{'})$。

定义 $a_t(x)a\_t(x)$ 表示经过 $tt$ 次再编号后第 $xx$ 个人的编号，${sum}_t\{sum\}\_t$ 表示 $tt$ 次再编号的编号和。

当 $t>0t\; >\; 0$ 时，有：

由此递推公式可得 $a_t(x)a\_t(x)$ 的通项：

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

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

然后根据 t 的奇偶性，计算出 $a_t(x)a\_t(x)$ 的值即可。

时间复杂度：$O(n+m)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;
}