2015轻院校赛 D 社交网络（排列组合）

http://acm.zznu.edu.cn/problem.php?id=1964

题目描述

输入

输出

样例输入

2

2 1

0 1

1 0

3 1

0 1 1

1 0 1

1 1 0

样例输出

0.500

1.125

提示

之前想了一个公式  就是0.5*pow（0.5，k)*C(k,n);

k是至少认识k个人   n是认识n个人

后来队友都把所有的东西都写出来了我才去验证第二个测试数据  发现是错的  当时真的想自己从五楼上跳下来

正确的公式应该是

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

{

　　ans+=0.5*pow（0.5，n)*C(i,n);

}

现在想想真是很有道理啊

当时为啥就是蒙蔽呢

#include <iostream>

#include <cstring>

#include <algorithm>

#include <queue>

#include <cstdio>

#include <cstdlib>

#include <cctype>

#include <cmath>

using namespace std;

int num[];

int x1[];

int x2[];

int s[][];

void Init(int n)

{

    memset(s, , sizeof(s));

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

    {

        int x=i;

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

        {

            if(x%j==)

            {

                s[i][j]++;

                x/=j;

                j--;

            }

        }

    }

}

long long c(int n, int k)

{

    memset(x1, , sizeof(x1));

    memset(x2, , sizeof(x2));

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

    {

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

        {

            x1[j] += s[i][j];

        }

    }

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

    {

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

        {

            x2[j] += s[i][j];

        }

    }

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

    {

        x2[i]-=x1[i];

    }

    long long ans=;

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

    {

        for(int j=; j<=x2[i];j++)

        {

            ans*=i;

        }

    }

    return ans;

}

double solve(int n, int k)

{

    double ans=;

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

    {

        ans += 0.5*c(n, i)*pow(0.5, n);

    }

    return ans;

}

int main()

{

    int t;

    int n, k;

    int x;

    scanf("%d", &t);

    Init();

    while(t--)

    {

        scanf("%d%d", &n, &k);

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

        {

            int sum1=;

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

            {

                scanf("%d", &x);

                if(x==)

                    sum1++;

            }

            num[i]=sum1;

        }

        double ans=;

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

        {

            if(num[i]>=k)

            {

                ans+=solve(num[i],k);

            }

        }

        printf("%.3lf\n", ans);

    }

    return ;

}