好的，我看看……

N=20的答案:
0.0000000000
0.0500000000
0.1075000000
0.1740000000
0.2513750000
0.3419875000
0.4488393750
0.5757788750
0.7277855875
0.9113668313
1.1351150741
1.4105007029
1.7530128690
2.1838214556
2.7322291824
3.4393375095
4.3636025057
5.5893747532
7.2402186389
9.5000000000


老老实实O(2^20*20*20)的dp吧:
考虑我上转马前的二进制状态i,设概率pro[i],0≤i<2^N-1。先枚举下一个人要去的位置j,求出他实际能去的位置k:
for(j = 0;j < N;++j) for(k=j;i & (1 << k);k = (k + 1)%N);
因此dp[i|(1<<k)] += dp[i]/(double)N;
初始条件dp[0] = 1;
下面就简单了


我N=20的答案：
0.000000
0.050000
0.107500
0.171579
0.243421
0.324510
0.416728
0.522500
0.645000
0.788462
0.958654
1.163636
1.415000
1.730000
2.135417
2.675000
3.425000
4.530000
6.297500
9.500000


回复：5楼
有错误，你把代码贴出来看看

打字打到一半蓝屏了...
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;
}


这个为了避免double运算精度有问题，把一些操作都放到算ans[i]裏边了..看不懂就是我的罪过了T.T

这个是原版~
#include <cstdio>
#include <vector>
using namespace std;
int n,num[1<<20];
vector<int> OPT[21];
double ans[20],freq[1<<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]=1.0;
       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)]+=1.0/(OPT[i].size()*n);
                   }
                   ans[i]+=freq[opt]*step/n;
             }
       }
       for (int i=0;i<n;i++) printf("%lf\n",ans[i]);
      
       return 0;
}


我把
freq[opt|(1<<last)]+=1.0/(OPT[i].size()*n);
这句改成
freq[opt|(1<<last)]+=1.0*freq[opt]/n;
就和你的一样了T.T

accepted..多亏看了4L..usrbin千秋万载，一统江湖~

回复：11楼
好吧，那就结贴了……下次搞dp细心点嘿

回复：12楼
嗯嗯

求mathmatic下载地址~~~找不到啊

回复：14楼
http://apps.hi.baidu.com/share/detail/24631499