AGC006C Rabbit Exercise
2020-05-21 16:00:27来源:博客园 阅读 ()
AGC006C Rabbit Exercise
题目链接
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.cnblogs.com/wxyww/p/agc006c.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 「LYOI2018 Summer」Hzy's Rabbit Candy 2018-08-07
- HDU 4452 Running Rabbits 模拟 2018-06-17
- HDU 4745---Two Rabbits(区间DP) 2018-06-17
- hdu 4057--Rescue the Rabbit(AC自动机+状压DP) 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash