天津网站seo营销模板,Seo建设网站的步骤,昆明网站建设c3sales,国外设计公司网站欣赏文章目录题目描述解析代码题目描述 解析
首先#xff0c;可以使用dp解决本题 设fi,j,k#xff1a;操作i轮之后编号j的小球有k个的概率 转移和统计答案就都不难了 但是还有一个问题 不难发现这个题循环下去是可以无穷无尽的 所以限定一个i的上界#xff08;如500000#xf…
文章目录题目描述解析代码题目描述 解析
首先可以使用dp解决本题 设fi,j,k操作i轮之后编号j的小球有k个的概率 转移和统计答案就都不难了 但是还有一个问题 不难发现这个题循环下去是可以无穷无尽的 所以限定一个i的上界如500000在损失精度可以接受的前提下使答案可求
代码
#includebits/stdc.h
using namespace std;
#define ll long long
const int N1e7100;
const int mod20040313;
int n,num[28],id[28],tot;
char s[28];
double dp[2][28][28];
int main(){scanf(%s,s1);totstrlen(s1);for(int i1;itot;i){int nows[i]-A1;if(id[now]0) id[now]n;num[id[now]];//printf(s%c id%d num%d\n,s[i],id[now],num[id[now]]);}for(int i1;in;i){//printf(i%d num%d\n,i,num[i]);dp[1][i][num[i]]1.0;}int now1;double ans0;for(int k0;k50000;k){for(int i1;in;i) ansdp[now][i][tot]*k;now^1;int prenow^1;for(int i1;in;i){for(int j0;jtot;j) dp[now][i][j]0;}//printf(k%d now%d pre%d\n,k,now,pre);for(int i1;in;i){for(int j0;jtot;j){double p1.0*j*(tot-j)/(tot*(tot-1));//printf( col%d num%d dp%lf p%lf\n,i,j,dp[pre][i][j],p);if(j0) dp[now][i][j-1]dp[pre][i][j]*p;dp[now][i][j1]dp[pre][i][j]*p;dp[now][i][j]dp[pre][i][j]*(1.0-2*p);}}//printf(k%d ans%lf\n,k,ans);}printf(%.6lf\n,ans);return 0;
}
/**/
