TopCoder SRM 575 Div1 500 TheSwapsDivOne

每个数只有两种情况，要么在原来的位置上，要么不在。
于是我们用一个简单的dp求出两种情况的概率。
$f\left[i\right]\left[0/1\right]$f[i][0/1]：Swap了 $i$i次后，0表示不在原来位置上，1表示在，的概率。

转移方程

• $f\left[i\right]\left[1\right]=f[i-1]\left[1\right]\ast (n-2)/n+f[i-1]\left[0\right]\ast 2/n/(n-1)$f[i][1]=f[i−1][1]∗(n−2)/n+f[i−1][0]∗2/n/(n−1)
• $f\left[i\right]\left[0\right]=f[i-1]\left[1\right]\ast 2/n+f[i-1]\left[0\right]\ast (1-2.0/n/(n-1\left)\right)$f[i][0]=f[i−1][1]∗2/n+f[i−1][0]∗(1−2.0/n/(n−1))

剩下的就很水了吧。只要求出 $i$i这个位置被子序列包含的概率就行了，这个就是 $\frac{i\ast (n-i+1)}{n\ast (n+1)/2}$n∗(n+1)/2i∗(n−i+1)​

一开始因为没开 $longlong$long long FST了(；′⌒`)

#include <bits/stdc++.h> #define fr(i,x,y) for(int i=x;i<=y;i++) #define ll long long using namespace std; const int N=1000005; double f[N][2]; ll n; ll a[2505]; template<class T> void checkmin(T &a,const T &b) { if (b<a) a=b; } template<class T> void checkmax(T &a,const T &b) { if (b>a) a=b; } class TheSwapsDivOne { public: double find( vector <string> sequence, int k ) ; }; double TheSwapsDivOne::find(vector <string> ss, int k) { string s; for(int i=0;i<ss.size();i++) s+=ss[i]; f[0][1]=1;n=s.size(); //cout<<n<<endl; fr(i,1,k){ f[i][1]=f[i-1][1]*(n-2)/n+f[i-1][0]*2/n/(n-1); f[i][0]=f[i-1][1]*2/n+f[i-1][0]*(1-2.0/n/(n-1)); } ll sum=0,w; fr(i,1,n) a[i]=s[i-1]-'0',sum+=a[i]; ll z=n*(n+1)/2; double ans=0; fr(i,1,n){ w=i*(n-i+1); ans+=a[i]*f[k][1]*w; ans+=w*(sum-a[i])*f[k][0]/(n-1); } ans/=z; return ans; }