TopCoder SRM 575 Div1 500 TheSwapsDivOne

每个数只有两种情况，要么在原来的位置上，要么不在。

于是我们用一个简单的dp求出两种情况的概率。

f [ i ] [ 0 / 1 ] f[i][0/1] f[i][0/1]：Swap了 i i i次后，0表示不在原来位置上，1表示在，的概率。

转移方程

• f [ i ] [ 1 ] = f [ i − 1 ] [ 1 ] ∗ ( n − 2 ) / n + f [ i − 1 ] [ 0 ] ∗ 2 / n / ( n − 1 ) f[i][1]=f[i-1][1]*(n-2)/n+f[i-1][0]*2/n/(n-1) 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 ) ) f[i][0]=f[i-1][1]*2/n+f[i-1][0]*(1-2.0/n/(n-1)) f[i][0]=f[i−1][1]∗2/n+f[i−1][0]∗(1−2.0/n/(n−1))

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

一开始因为没开 l o n g   l o n g long\ long 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;
}