Solution
设兔子 \(a\) 在坐标 \(i\) 的概率是 \(p_i\),然后现在有一只在坐标 \(j\) 上的兔子 \(b\) 要关于 \(a\) 做一次对称,则 \(b\) 兔子对称完之后坐标的期望应该是:
\[\sum(2i-j)\times p_i=\sum2i\times p_i-j\sum p_i=2\sum i\times p_i-j \]
仔细思考一下发现,\(\sum i\times p_i\) 就是 \(a\) 的坐标期望值。
所以我们得到,对于一个在位置 \(j\) 的兔子关于坐标期望为 \(E_a\) 的兔子对称后的坐标期望值为:\(2E_a-j\)。挺合理的对吧。
然后考虑,如果我们现在是一个期望坐标在 \(E_b\) 的兔子 \(b\) 关于 \(a\) 对称呢?同样我们可以得到:
\[E_b’=\sum(2E_a-j)\times p_j=2E_a-E_b \]
太合理了把。
那如果是 \(\dfrac{1}{2}\) 的概率关于它对称呢?根据期望的线性性,不难得到,如果兔子 \(a\) 以相同的概率关于兔子 \(b,c\) 对称,那么有:
\[E_a’=\dfrac{1}{2}(2E_b-E_a)+\dfrac{1}{2}(2E_c-E_a)=E_b+E_c-E_a \]
也就是说,每一次操作都是让相邻两个的坐标期望加起来减去当前位置。
这东西是个很套路的差分模型。我们将 \(E\) 的差分序列 \(D\) 求出来,那么上面的变换就是:
\[D_a=E_a-E_{a-1},D_{a+1}=E_{a+1}-E_a\\ D_a’=E_{a+1}-E_a,D_{a+1}’=E_a-E_{a-1} \]
不难发现对 \(a\) 进行操作就是交换 \(a\) 和 \(a+1\) 的差分数组。
所以首先我们不难求出初始的 \(D\),此后考虑如何处理 \(k\) 轮的问题。不难发现,在做若干轮的过程中,互相交换的几个位置形成若干个置换群。具体地,我们可以先手动进行一次对 \(1\sim n-1\) 排列的交换,然后直接求出每个置换群。之后对每个置换群单独做交换 \(k\) 轮,就可以直接模群的大小了。
Code
// Problem:
// [AGC006C] Rabbit Exercise
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_agc006_c
// Memory Limit: 256 MB
// Time Limit: 2000 ms
#include<bits/stdc++.h>
#define ll long long
#define inf (1<<30)
#define INF (1ll<<60)
#define pb emplace_back
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define siz(a) (int)a.size()
#define clr(a) memset(a,0,sizeof(a))
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pt(a) cerr<<#a<<'='<<a<<' '
#define pts(a) cerr<<#a<<'='<<a<<'\n'
#define int long long
using namespace std;
const int MAXN=1e5+10;
int x[MAXN],p[MAXN],vis[MAXN],q[MAXN];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n;cin>>n;
rep(i,1,n) cin>>x[i];
per(i,n,1) x[i]-=x[i-1];
int m,k;cin>>m>>k;
rep(i,1,n) p[i]=i;
rep(i,1,m){
int a;cin>>a;
swap(p[a],p[a+1]);
}rep(i,1,n) q[p[i]]=i;
rep(i,1,n){
if(vis[i]) continue;
vector<int> gp;
int tmp=i;
while(!vis[tmp]){
vis[tmp]=1;
gp.pb(tmp);
tmp=q[tmp];
}int t=k%siz(gp);
while(t--){
int cur=x[gp[0]];
rep(j,1,siz(gp)-1)
swap(cur,x[gp[j]]);
x[gp[0]]=cur;
}
}rep(i,2,n) x[i]+=x[i-1];
rep(i,1,n) cout<<x[i]<<".0\n";
return 0;
}
原文地址:http://www.cnblogs.com/ZCETHAN/p/16851951.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性