2014
01-16

# 九度-1421-Abor[概率计算]

### 题目1421：Abor

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

011
101
110

3个人期望值是相同的都为 0.5 * 0.5 * 0.5 ，结果即为 0.5 * 0.5 * 0.5 * 3 = 0.38

#include<cstdio>
#include<cstring>
#include<cmath>
char ch[30];
long double po[30];
long long C(int a,int b)
{
long long u=1,d=1;
if(b-a<a)
a = b-a;
int bb = b,aa = a;
for(int i=0;i<a;i++)
{
u*=bb--;
d*=aa--;
//aa--;
//bb--;
}
long long sum = u/d;
return sum;
}
void Init()
{
po[0] = 1.0;
for(int i=1;i<=21;i++)
po[i] = po[i-1]*0.5;
}
int main()
{
int t,j;
Init();
scanf("%d",&t);
while(t--)
{
int n,m,f;
long double p = 0.0;
scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)
{
f = 0;
scanf("%s",ch);
for( j=0;j<n;j++)
if(ch[j]=='1')
f++;
if(f<m)
continue;

for(j=m;j<=f;j++)
p+=C(j,f)*po[f+1];
}
if(m==0)
{
printf("1.00\n");
continue;
}
if(m==n)
{
printf("0.00\n");
continue;
}
printf("%0.2lf\n",(double)p);

}
return 0;
}
/**************************************************************
Problem: 1421
User: 从此醉
Language: C++
Result: Accepted
Time:10 ms
Memory:1020 kb
****************************************************************/

1. /*
* =====================================================================================
*
* Filename: 1366.cc
*
* Description:
*
* Version: 1.0
* Created: 2014年01月06日 14时52分14秒
* Revision: none
* Compiler: gcc
*
* Author: Wenxian Ni (Hello World~), [email protected]
* Organization: AMS/ICT
*
* =====================================================================================
*/

#include
#include

using namespace std;

int main()
{
stack st;
int n,i,j;
int test;
int a[100001];
int b[100001];
while(cin>>n)
{
for(i=1;i>a[i];
for(i=1;i>b[i];
//st.clear();
while(!st.empty())
st.pop();
i = 1;
j = 1;

while(in)
break;
}
while(!st.empty()&&st.top()==b[j])
{
st.pop();
j++;
}
}
if(st.empty())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}