九度-1421-Abor[概率计算] | Acm之家
男女出现的概率是相同的。只有男生才能叫做abor
以第三个例子：
对于任意的n，需要分别计算再相加。
Read full article from 九度-1421-Abor[概率计算] | Acm之家
- As we all known, AbOr has a lots of girls in a palace called "Hou" (About 30 millions).Now you are given n people without knowing their gender(Male and Female are equally likely for anyone). You also know the relationship between them! You want to know what is the expecting number of "abor" that could be found , where "abor" is defined as:(1) Only Male might be considered;(2) The Male who has at least m Females friends is called "abor".
- 输入：
- The first line is one integer T indicates the number of the test cases. (T <= 10000)Then for every case, the first line has only two integers n and m, indicating the number of people and the value of m.(0≤m≤n≤20)Then one n by n symmetric matrix A, where A[i][j] is 1 if j is a friend of i(vice versa) and 0 otherwise;(A[i][i] is always 0)
- 输出：
- Output the expecting number of "abor" in the given case. The answer must round to two digital after the decimal point.
- 样例输入：
3 2 1 01 10 2 0 01 10 3 2 011 101 110
- 样例输出：
0.50 1.00 0.38
男女出现的概率是相同的。只有男生才能叫做abor
以第三个例子：
011
101
1103个人期望值是相同的都为 0.5 * 0.5 * 0.5 ，结果即为 0.5 * 0.5 * 0.5 * 3 = 0.38
对于任意的n，需要分别计算再相加。
因为对于每一个人，他需要计算他有多少个女性朋友，同时朋友的性别是随机的，概率为0.5，这个题目就相当于算期望了
对每个人来说，他本身是男性的可能性为0.5 ，他有至少m个的概率就只需要在他的朋友FriendsCount中选m 个就好了，这个是组合问题。但是需要注意的是，m+1，m+2，...，FriendsCount 都是满足的，加起来就是每一个人的可能性，不要忘记前面的要求，因为他必须是男性，所以在组合概率的基础上还需要乘以0.5
- int Cal(int n, int m) {
- if(m==0)
- return 1;
- if ( m==1 )
- return n;
- else if ( n==m )
- return 1;
- else return ( Cal(n-1,m-1 )+ Cal(n-1,m));
- }
- int main()
- {
- //freopen("data.in","r",stdin);
- int num,n,m;
- double B[22];
- B[0]=1;
- for(int i=1;i<22;i++)
- B[i]=B[i-1]/2;
- scanf("%d",&num);
- while(num--)
- {
- scanf("%d%d",&n,&m);
- double result=0;
- for(int i=0;i<n;i++)
- {
- int tmp=0;
- char c[21];
- scanf("%s",&c);
- for (int j=0;j<n;j++)
- {
- if(c[j]=='1')
- tmp++;
- }
- for(int k=m;k<=tmp;k++)
- result=result+B[tmp+1]*Cal(tmp,k);
- }
- printf("%.2f\n",result);
- }
- return 0;
- }
04 | char ch[30]; |
05 | long double po[30]; |
06 | long long C(int a,int b) |
07 | { |
08 | long long u=1,d=1; |
09 | if(b-a<a) |
10 | a = b-a; |
11 | int bb = b,aa = a; |
12 | for(int i=0;i<a;i++) |
13 | { |
14 | u*=bb--; |
15 | d*=aa--; |
16 | //aa--; |
17 | //bb--; |
18 | } |
19 | long long sum = u/d; |
20 | return sum; |
21 | } |
22 | void Init() |
23 | { |
24 | po[0] = 1.0; |
25 | for(int i=1;i<=21;i++) |
26 | po[i] = po[i-1]*0.5; |
27 | } |
28 | int main() |
29 | { |
30 | int t,j; |
31 | Init(); |
32 | scanf("%d",&t); |
33 | while(t--) |
34 | { |
35 | int n,m,f; |
36 | long double p = 0.0; |
37 | scanf("%d%d",&n,&m); |
38 |
39 | for(int i=1;i<=n;i++) |
40 | { |
41 | f = 0; |
42 | scanf("%s",ch); |
43 | for( j=0;j<n;j++) |
44 | if(ch[j]=='1') |
45 | f++; |
46 | if(f<m) |
47 | continue; |
48 |
49 | for(j=m;j<=f;j++) |
50 | p+=C(j,f)*po[f+1]; |
51 | } |
52 | if(m==0) |
53 | { |
54 | printf("1.00\n"); |
55 | continue; |
56 | } |
57 | if(m==n) |
58 | { |
59 | printf("0.00\n"); |
60 | continue; |
61 | } |
62 | printf("%0.2lf\n",(double)p); |
63 |
64 | } |
65 | return 0; |
66 | } |
