[AGC006C] Rabbit Exercise

Solution

设兔子 \(a\) 在坐标 \(i\) 的概率是 \(p_i\)，然后现在有一只在坐标 \(j\) 上的兔子 \(b\) 要关于 \(a\) 做一次对称，则 \(b\) 兔子对称完之后坐标的期望应该是：

仔细思考一下发现，\(\sum i\times p_i\) 就是 \(a\) 的坐标期望值。

所以我们得到，对于一个在位置 \(j\) 的兔子关于坐标期望为 \(E_a\) 的兔子对称后的坐标期望值为：\(2E_a-j\)。挺合理的对吧。

然后考虑，如果我们现在是一个期望坐标在 \(E_b\) 的兔子 \(b\) 关于 \(a\) 对称呢？同样我们可以得到：

太合理了把。

那如果是 \(\dfrac{1}{2}\) 的概率关于它对称呢？根据期望的线性性，不难得到，如果兔子 \(a\) 以相同的概率关于兔子 \(b,c\) 对称，那么有：

也就是说，每一次操作都是让相邻两个的坐标期望加起来减去当前位置。

这东西是个很套路的差分模型。我们将 \(E\) 的差分序列 \(D\) 求出来，那么上面的变换就是：

不难发现对 \(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