題目鏈接
problem
有\(n\)個兔子站成一排，每只兔子有自己的位置，有\(m\)次操作，第\(i\)次操作將\(a_i\)以相等的概率挪到關于\(a_{i-1}\)對稱的位置或挪到與\(a_{i+1}\)對稱的位置，
將這m次操作進行K輪，
問最終每只兔子位置坐標的期望，
solution
對于第\(a_i\)個兔子，設\(a_i-a_{i-1}=x,a_{i+1}-a_i=y\)，那么如果選擇關于\(a_{i-1}\)對稱，所到達的位置就是\(l=a_{i-1}-x\)，同樣的，如果選擇關于\(a_{i+1}\)對稱，到達的位置就是\(r=a_{i+1}+y\)，根據期望的線性性，第\(i\)只兔子所在坐標的期望就是\(t=\frac{l+r}{2}\)，顯然\(t-l=r-t=x+y\)，又因為\(a_{i-1}-l=x,r-a_{i+1}=y\)，所以就有\(t-a_{i-1}=y,a_{i+1}-t=x\)，
設\(d_i=a_i-a_{i-1}\)，對于第\(i\)個兔子進行一次操作，就相當于交換了\(d_i\)與\(d_{i+1}\)，
那么做法就很簡單了，先根據\(m\)操作求出一個置換，然后利用快速冪計算置換\(K\)次后的答案，
復雜度\(O(nlogK)\)
code
/*
* @Author: wxyww
* @Date: 2020-05-21 15:53:33
* @Last Modified time: 2020-05-21 16:09:36
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 200010;
#define int ll
ll read() {
ll x = 0,f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1; c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + c - '0'; c = getchar();
}
return x * f;
}
int n;
ll tmp[N];
void mul(int *a,int *b) {
for(int i = 1;i <= n;++i) {
tmp[i] = a[b[i]];
}
for(int i = 1;i <= n;++i) a[i] = tmp[i];
}
int a[N],p[N];
void qm(ll y) {
int ret[N];
for(int i = 1;i <= n;++i) ret[i] = i;
for(;y;y >>= 1,mul(p,p))
if(y & 1) mul(ret,p);
for(int i = 1;i <= n;++i) p[i] = ret[i];
}
signed main() {
n = read();
for(int i = 1;i <= n;++i) {
a[i] = read();p[i] = i;
}
int m = read();ll K = read();
for(int i = n;i >= 1;--i) a[i] -= a[i - 1];
for(int i = 1;i <= m;++i) {
int x = read();
swap(p[x],p[x + 1]);
}
qm(K);
for(int i = 1;i <= n;++i) tmp[i] = a[p[i]];
// for(int i = 1;i <= n;++i) printf("%d ",tmp[i]);
// puts("");
for(int i = 1;i <= n;++i) {
printf("%lld.0\n",tmp[i] += tmp[i - 1]);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/24305.html
標籤：C++
上一篇：C++基礎之函式