asp网站的缺点,微官网怎么注册,网站百度不收录了,wap网站实例正题
题目链接:https://www.luogu.com.cn/problem/AT2164 题目大意 nnn只兔子编号为1∼n1\sim n1∼n#xff0c;第iii只在坐标轴xix_ixi处。然后mmm次跳跃#xff0c;每次给出aia_iai#xff0c;编号为aia_iai的兔子会等概率的选取ai−1a_{i-1}ai−1和ai1a_{i1}ai1…正题
题目链接:https://www.luogu.com.cn/problem/AT2164 题目大意
nnn只兔子编号为1∼n1\sim n1∼n第iii只在坐标轴xix_ixi处。然后mmm次跳跃每次给出aia_iai编号为aia_iai的兔子会等概率的选取ai−1a_{i-1}ai−1和ai1a_{i1}ai1跳跃到对称位置。进行kkk轮求最后每只兔子的期望位置。
3≤n≤105,1≤m≤105,1≤k≤10183\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 解题思路
设fif_ifi表示iii的期望位置的话对于每次跳跃兔子xxx它的概率就是 fx(2fx−1−fx)(2fx1−fx)2fx−1fx1−fxf_x\frac{(2f_{x-1}-f_{x})(2f_{x1}-f_x)}{2}f_{x-1}f_{x1}-f_{x}fx2(2fx−1−fx)(2fx1−fx)fx−1fx1−fx 然后这个见到这个式子就直接差分成gifi−fi−1g_if_i-f_{i-1}gifi−fi−1。
然后上面那个东西就变成了交换iii和i1i1i1。
然后就是给一个交换交换kkk次因为kkk很大倍增搞就好了。
时间复杂度O(nlogk)O(n\log k)O(nlogk) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e510;
ll n,m,k,d[N],ans[N],t[N];
double x[N];
signed main()
{scanf(%lld,n);for(ll i1;in;i){scanf(%lf,x[i]);d[i]ans[i]i;}scanf(%lld%lld,m,k);for(ll i1;im;i){ll x;scanf(%lld,x);swap(d[x],d[x1]);}while(k){if(k1){for(ll i1;in;i)t[i]ans[d[i]];for(ll i1;in;i)ans[i]t[i];}for(ll i1;in;i)t[i]d[d[i]];for(ll i1;in;i)d[i]t[i];k1;}double sum0;for(ll i1;in;i){sumx[ans[i]]-x[ans[i]-1];printf(%.1lf\n,sum);}return 0;
}
