Submission #2453727

---

Source Code Expand

#include<algorithm>
#include<iostream>
#include<sstream>
#include<vector>
#include<cmath>
using namespace std;
typedef long long lint;
typedef vector<int>vi;
typedef pair<int,int>pii;
#define rep(i,n)for(int i=0;i<(int)(n);++i)

const int DEBUG = 0;

double dp[31][31];

int main(){
  int n;
  cin>>n;
  string pq;
  cin>>pq;
  stringstream ss(pq);
  double p;
  {
    int u,v;
    ss>>u;
    ss.ignore();
    ss>>v;
    p=(double)u/(double)v;
  }
  vector<vi>a(n,vi(n));
  rep(i,n)rep(j,n)cin>>a[i][j];
  vector<pii>has(n);
  rep(i,n){
    int t=0;
    rep(j,n)t+=a[i][j];
    has[i]=pii(-t,i);
  }
  sort(has.begin(),has.end());
  dp[0][n-1]=1;
  rep(i,n){
    int u=i==0?-1:has[i-1].second,v=has[i].second;
    vector<double> trans(n);
    int bc=0;
    rep(j,n)bc+=a[v][j];
    rep(j,bc+1){
      rep(k,n-bc){
	double tmp=pow(p,j+n-1-bc-k)*pow(1-p,bc-j+k);
	rep(l,j)tmp=tmp*(bc-l)/(l+1);
	rep(l,k)tmp=tmp*(n-1-bc-l)/(l+1);
	trans[j+k]+=tmp;
      }
    }
    if(DEBUG){
      cerr<<"trans["<<v<<"]:";
      rep(j,n)cerr<<" "<<trans[j];
      cerr<<endl;
    }
    rep(j,n)rep(k,n)
      if(j<k||(u<=v&&j==k))dp[i+1][j]+=trans[j]*dp[i][k];
  }
  double ans=0;
  rep(i,n)ans+=dp[n][i];
  printf("%.15f\n",ans);
}

Submission Info

Judge Result