[NOI赛前训练]——专项测试3·数学

由于并不想写T1和T2的题解……所有只有T3的题解了。

T3

　　由于内部题就只写题解了。

　　好吧，我是一点都不想写……

　　说一下这zz题解哪里写错了吧……

　　……不想写……

　　就说一个吧……

　　$n-\frac{k-i}{2}$应该是$\frac{k-i}{2}$。

　　好累啊，完全不想写题解，有空再说吧。

 #include "bits/stdc++.h"

 using namespace std;

 const int N=4e2+;

 double f[N][N],p[N][N],C[N][N],mi[N][N];

 int n,num[N][N];

 char s[N];

 inline void init(){

     int i,j,k;

     for (C[][]=i=;i<N;++i)

         for (C[i][]=j=;j<=i;++j)

             C[i][j]=C[i-][j]+C[i-][j-];

     for (i=;i<=n;++i)

         for (j=i,k=;j<=n;++j){

             if (s[j]=='.') ++k;

             num[i][j]=k;

         }

 }

 inline void dp(){

     if (!num[][n]){

         puts("0.000000");return ;

     }

     register int i,j,k,l;

     for (i=;i<=n;++i) if(s[i]=='.')

         p[i][i]=1.0;

     for (l=;l<=(n>>);++l) {

         for (i=;i<=l;++i)

             for (mi[i][]=,k=;k<=l;++k)

                  mi[i][k]=mi[i][k-]*i/l;

         for (i=,j=l;i<=n;++i,++j) {

             f[i][j]=p[i][j]=0.0;

             if(s[j]=='.'){

                 for (k=i;k<j;++k) if(s[k]=='.'){

                     int lk=num[i][k-],rk=num[k+][j-];

                     double now=C[lk+rk][lk]*

                                mi[(k-i+)][lk+]*

                                mi[(j-k)][rk]*

                                p[i][k]*p[k+][j];

                     p[i][j]+=now;

                     f[i][j]+=now*(f[i][k]+f[k+][j]+(k-i)/2.0);

                 }

                 if (num[i][j-]==)p[i][j]=1.0;

                 f[i][j]/=p[i][j];

             }

         }

     }

     double ans=0.0;

     for (i=;i<=n/;++i)

         ans+=f[i][i+n/-]*p[i][i+n/-];

     ans+=(n/-)/2.0;

     printf("%.6f\n",ans);

 }

 int main(){

     int T;

     scanf("%d",&T);

     while (T--) {

         scanf("%s",s+);

         n=strlen(s+);

         for (int i=n+;i<=(n<<);++i)

             s[i]=s[i-n];

         n<<=;

         init();

         dp();

     }

 }