Description
Alice得到了一個整數， 她將其視作長度為n的字符串S。為了好玩，她進行了k次如下操作：

1) 隨機選取兩個不同的位置x和y（即每次操作， { < x, y> | 1<=x < y <=n}中每個元素都有相同的概率被選到）

2) 交換數位S[x]和數位S[y]

為了自虐，在Alice惡搞之后，Bob會隨機一個子串（即對于任意子串都有相同概率被選到），然后他想知道他選出的子串中各個位置數字之和的期望為多少。聰明的Bob想出了一個很好的方法來解決這個問題，那就是把這個問題交給你。Bob會告訴你S和k，你需要告訴他期望。

Input
一行，包含字S和k。

Output
一行，一個實數。當你的輸出和標準答案的差距少于10^-6時，被認為是正確的。

Sample Input
輸入1：

477 1

輸入2：

57268508514909598902647806463326698034850446919720257361969 7

Sample Output
輸出1：

10

輸出2：

98.3238536775161

Data Constraint
對于70%的數據 |S|<=2500，k<=1000000

對于100%的數據 |S|<=1000000，k<=1000000
.
.
.
.
.

分析

k次交換后，ANS=每一位的期望值*每一位被選出的概率。
顯然第i位被選出的概率=包含i的子串數/總子串數=i*(l-i+1)/(l*(l+1)/2)。
那如何求k次交換后每一位的期望值？
我們假設最初第i位為ai，p次交換后第i位仍然等于ai的概率是x，那么p+1交換后第i為仍然等于ai的概率是x*(1-(l-1)/y))+(1-x)/y，其中y=l*(l-1)/2。
接下來有一個性質：
如果第i位不為ai，那么第i位是a中其他任何數的概率都是一樣的(交換的隨機性決定的)。
因此如果k次交換后，第i位為ai的概率是x，那么第i位的期望值=ai*x+(tj-ai)/(l-1)*(1-x)。
至此問題就可以解決了。
.
.
.
.
.

程序：

#include<iostream> #include<string.h> #include<cstdio> using namespace std; double x,y,rp,u,v; int a[1000001],tj,l,k; char zf[1000001];void jb() {cin>>zf;cin>>k;l=strlen(zf);x=1.0;y=l*(l-1.0)/2.0;for (int i=1;i<=k;i++) x=x*(1.0-(l-1.0)/y)+(1.0-x)/y;for (int i=1;i<=l;i++){a[i]=zf[i-1]-'0';tj+=a[i];} }int main() {jb();for (int i=1;i<=l;i++){u=i*(double)(l-i+1.0)/(double)(l*(l+1.0)/2.0);v=(double)a[i]*x+(double)(tj-a[i])/(double)(l-1.0)*(1.0-x);rp+=u*v;}printf("%.9lf",rp);return 0; }

轉載于:https://www.cnblogs.com/YYC-0304/p/9499919.html

總結

以上是生活随笔為你收集整理的【NOIP2013模拟9.29】TheSwaps的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。