打字打到一半蓝屏了...
freq[opt]表示二进制状态opt出现的概率。
用sigma{freq[opt]*sigma(n个位置需要等待的步数）/n}更新下一个opt'
代码如下~~~
#include <cstdio>
#include <vector>
using namespace std;
int n,num[1<<20],freq[1<<20];
vector<int> OPT[21];
double ans[20];
int main(){
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
scanf("%d",&n);
for (int opt=0;opt<(1<<n);opt++){
num[opt]=num[opt>>1]+(opt&1);
OPT[num[opt]].push_back(opt);
}
freq[0]=n;
for (int i=0;i<n;i++){
for (vector<int>::iterator it=OPT[i].begin();it!=OPT[i].end();it++){
int opt=*it;
int last=0,step=0;
while (opt&(1<<last)) last++;
for (int p=n-1;p>=0;p--){
if (!(opt&(1<<p))) last=p;
step+=(last-p+n)%n;
freq[opt|(1<<last)]++;
}
int size=(!i)?(1):(OPT[i-1].size());
ans[i]+=1.0*freq[opt]*step/n/n/size;
}
}
for (int i=0;i<n;i++) printf("%lf\n",ans[i]);
return 0;
}
