题解 AT2164 【Rabbit Exercise】
Kinandra
2019-12-04 20:59:26
标签: 期望, 差分, 置换.
我们首先考虑一次跳跃对于答案的影响, 显然只改变跳跃的兔子的答案, 设这只兔子坐标为 $y$ , 跳跃后为 $y'$, 与其相邻的两只兔子坐标分别为 $x, z$, 我们考虑三元组 $(x,y,z)$ 的变化情况.
那么一次跳跃之后会转移到 $(x, 2x-y, z)$ 或 $(x, 2z-y, z)$ , 所以 $E(y')=\frac{E(2x-y)+E(2z-y)}{2}=E(x)+E(z)-E(y)$ , 那么我们只要实时维护好 $E$ 就行了.
然而暴力的 $O(mk)$ 做法并不可取, 我们容易感觉到 $k$ 轮操作必然会有某种循环的形式在其中, 需要发现更多性质来找到这种循环.
根据上面的推导一次操作会使 $(x, y, z)$ 变成 $(x, x+z-y, z)$, 这个看起来毫无规律, 观察发现三元组差分之后会有美妙的形式: $(x, y-x, z-y)$ 变成 $(x, z-y, y-x)$ , 等价于交换第二, 三个元素.
于是差分后一次加减操作变成了一个交换操作, 多次交换操作可以用轮换的形式表示, 我们用轮换表示出一轮操作的结果, 如果有了解过关于置换的知识就可以很简单的解决本题了, 不赘述.
```cpp
#include <bits/stdc++.h>
using namespace std;
int read();
int n, m;
long long x[200005], k;
int a[200005], nx[200005];
int res[200005], vis[200005], st[200005], top;
int main() {
n = read();
for (int i = 1; i <= n; ++i) x[i] = read(), nx[i] = i;
for (int i = n; i >= 1; --i) x[i] -= x[i - 1];
m = read(), scanf("%lld", &k);
for (int i = 1; i <= m; ++i) a[i] = read();
for (int j = 1; j <= m; ++j) swap(nx[a[j]], nx[a[j] + 1]);
for (int i = 1, j; i <= n; ++i) {
if (vis[i]) continue;
st[top = vis[i] = 1] = i, j = nx[i];
while (j != i) st[++top] = j, j = nx[j], vis[j] = 1;
for (j = 1; j <= top; ++j) res[st[j]] = st[(j + k - 1) % top + 1];
}
long long t = 0;
for (int i = 1; i <= n; ++i) t += x[res[i]], printf("%lld.0\n", t);
return 0;
}
int read() {
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') f = (c == '-') ? -1 : f, c = getchar();
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
```