正题
题目链接:https://www.luogu.com.cn/problem/AT2164
题目大意
n n n只兔子编号为 1 ∼ n 1\sim n 1∼n，第 i i i只在坐标轴 x i x_i xi处。然后 m m m次跳跃，每次给出 a i a_i ai，编号为 a i a_i ai的兔子会等概率的选取 a i − 1 a_{i-1} ai−1和 a i + 1 a_{i+1} ai+1跳跃到对称位置。进行 k k k轮，求最后每只兔子的期望位置。
3 ≤ n ≤ 1 0 5 , 1 ≤ m ≤ 1 0 5 , 1 ≤ k ≤ 1 0 18 3\leq n\leq 10^5,1\leq m\leq 10^5,1\leq k\leq 10^{18} 3≤n≤105,1≤m≤105,1≤k≤1018
解题思路
设
f
i
f_i
fi表示
i
i
i的期望位置的话，对于每次跳跃兔子
x
x
x，它的概率就是
f
x
=
(
2
f
x
−
1
−
f
x
)
+
(
2
f
x
+
1
−
f
x
)
2
=
f
x
−
1
+
f
x
+
1
−
f
x
f_x=\frac{(2f_{x-1}-f_{x})+(2f_{x+1}-f_x)}{2}=f_{x-1}+f_{x+1}-f_{x}
fx=2(2fx−1−fx)+(2fx+1−fx)=fx−1+fx+1−fx
然后这个见到这个式子就直接差分成
g
i
=
f
i
−
f
i
−
1
g_i=f_i-f_{i-1}
gi=fi−fi−1。
然后上面那个东西就变成了交换 i i i和 i + 1 i+1 i+1。
然后就是给一个交换，交换 k k k次，因为 k k k很大倍增搞就好了。
时间复杂度 O ( n log k ) O(n\log k) O(nlogk)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=1e5+10;
ll n,m,k,d[N],ans[N],t[N];
double x[N];
signed main()
{
scanf("%lld",&n);
for(ll i=1;i<=n;i++){
scanf("%lf",&x[i]);
d[i]=ans[i]=i;
}
scanf("%lld%lld",&m,&k);
for(ll i=1;i<=m;i++){
ll x;scanf("%lld",&x);
swap(d[x],d[x+1]);
}
while(k){
if(k&1){
for(ll i=1;i<=n;i++)t[i]=ans[d[i]];
for(ll i=1;i<=n;i++)ans[i]=t[i];
}
for(ll i=1;i<=n;i++)t[i]=d[d[i]];
for(ll i=1;i<=n;i++)d[i]=t[i];
k>>=1;
}
double sum=0;
for(ll i=1;i<=n;i++){
sum+=x[ans[i]]-x[ans[i]-1];
printf("%.1lf\n",sum);
}
return 0;
}