The Swap

WonderfulZealousTom · 2018-09-28 16:34:33 · 个人记录

The Swap

源程序      swap.cpp* 
输入文件    swap.in 
输出文件    swap.out 
时间限制    1s 
空间限制    256MB
【问题描述】 
Alice 得到了一个整数， 她将其视作长度为 n 的字符串 S。为了好玩，她迚行了 k 次如下操作： 
1)  随机选取两个不同的位置 x 和y（即每次操作， {<x, y> | 1<=x < y <=n}中每个元素都有
相同的概率被选到） 
2)  交换数位 S[x]和数位 S[y] 
为了自虐，在 Alice 恶搞之后，Bob 会随机一个子串（即对于任意子串都有相同概率被选到），然后
他想知道他选出的子串中各个位置数字之和的期望为多少。聪明的 Bob 想出了一个很好的方法来解决这个
问题，那就是把这个问题交给你。Bob 会告诉你 S和 k，你需要告诉他期望。 
【输入格式】
一行，包含字 S和 k。 
【输出格式】
一行，一个实数。当你的输出和标准答案的差距少于 10^-6 时，被认为是正确的。 
【样例输入】 
477 1 
【样例输出】 
10 
【样例输入】 
57268508514909598902647806463326698034850446919720257361969 7 
【样例输出】 
98.3238536775161 
【数据范围】 
对于 70%的数据 |S|<=2500，k<=1000000 
对于 100%的数据 |S|<=1000000，k<=1000000 

以下是题解部分。

首先，我们定义以下数组：

int a[]     //储存这个字符串
int f[]     //任意字符在i轮交换之后不在自己原位上的概率
int total   //结果
int sum     //所有字符的权值和

【疑问环节】

Q：为什么f是“任意字符”的不在原位概率呢？为什么不是考虑每一个字符不在原位的概率呢？

A：因为对于每一个字符，它在交换i轮之后的概率都是相等的，所以我们可以把每一个字符每一轮的概率合并成任意字符每一轮的概率，即将二维转化为一维。

然后我们考虑f数组。对于第k轮交换，一个字符它只有两种可能：即上一轮在自己原位；与上一轮不在自己原位。那么，上一轮每个字符的位置情况决定了这一轮的概率。

上一轮不在自己原位的概率：

我们知道，每个字符串都可以和与自己不相同的字符串交换，所以交换的可能性为：\frac{n(n-1)}{2}。一个上一轮不在自己原位的字符回到自己原位的概率是\frac{1}{\frac{n(n-1)}{2}}，化简得\frac{2}{n(n-1)}。

所以，一个上一轮不在自己原位的字符在这一轮不回到自己原位的概率是：1-\frac{2}{n(n-1)}，化简得\frac{n(n-1)-2}{n(n-1)}。而上一轮不在自己原位的概率又是f[k-1]，可得递推式f[k-1]×\frac{n(n-1)-2}{n(n-1)}

上一轮在自己原位的概率：

如果一个字符上一轮在自己的位置，那么它在上上轮不在自己位置到了上轮在自己位置的概率为1-f[k-1]，而如果一个字符上一轮在自己位置上，那么这一轮它只需要和任意一个非自己位置的字符交换即可，有\frac{n-1}{\frac{n(n-1)}{2}} 即\frac{1}{n/2}种概率在这一轮不在自己位置。于是合并得：(1-f[k-1])×\frac{1}{n/2}。

最后，只需把两种概率相加，可得：

贡献值

求和: