设 \(f_{i,j}\) 表示兔子 \(i\) 在当前 \(j\) 轮的期望位置

对于一次操作 \(f_{i,j+1}=\frac{1}{2}(2f_{i-1,j}-f_{i,j})+\frac{1}{2}(2f_{i+1,j}-f_{i,j})=f_{i-1,j}+f_{i+1,j}-f_{i,j}\)

这个东西就是差分数组上两个位置的交换

相当于是求经过 \(k\) 次长度为 \(m\) 的置换后的位置

只要求每个位置在每个环走 \(k\) 的位置即可

# include 
    
     using namespace std;typedef long long ll;     const int maxn(1e5 + 5);     int n, m, b[maxn], nxt[maxn], que[maxn], len, vis[maxn];ll k, f[maxn], g[maxn];     int main() {    int i, j;    scanf("%d", &n);    for (i = 1; i <= n; ++i) scanf("%lld", &f[i]), b[i] = i;    for (i = n; i; --i) f[i] -= f[i - 1];    scanf("%d%lld", &m, &k);    for (i = 1; i <= m; ++i) scanf("%d", &j), swap(b[j], b[j + 1]);    for (i = 1; i <= n; ++i)        if (!vis[i]) {            vis[i] = 1, j = b[i], que[len = 1] = i;            while (!vis[j]) que[++len] = j, vis[j] = 1, j = b[j];            for (j = 1; j <= len; ++j) nxt[que[j]] = que[(k + j - 1) % len + 1];        }    for (i = 1; i <= n; ++i) g[i] = f[nxt[i]];    for (i = 1; i <= n; ++i) g[i] += g[i - 1], printf("%lld\n", g[i]);    return 0;}