[原创]hdu 4609 3-idiots [FFT计数]【数学】

2017-01-14 18:08:40 Tabris_ 阅读数：431

博客爬取于2020-06-14 22:42:11
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54427994

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=4609
-----------------------------------------------------------.
3-idiots

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4437 Accepted Submission(s): 1561

Problem Description
King OMeGa catched three men who had been streaking in the street. Looking as idiots though, the three men insisted that it was a kind of performance art, and begged the king to free them. Out of hatred to the real idiots, the king wanted to check if they were lying. The three men were sent to the king’s forest, and each of them was asked to pick a branch one after another. If the three branches they bring back can form a triangle, their math ability would save them. Otherwise, they would be sent into jail.
However, the three men were exactly idiots, and what they would do is only to pick the branches randomly. Certainly, they couldn’t pick the same branch - but the one with the same length as another is available. Given the lengths of all branches in the forest, determine the probability that they would be saved.

Input
An integer T(T≤100) will exist in the first line of input, indicating the number of test cases.
Each test case begins with the number of branches N(3≤N≤105).
The following line contains N integers a_i (1≤a_i≤105), which denotes the length of each branch, respectively.

Output
Output the probability that their branches can form a triangle, in accuracy of 7 decimal places.

Sample Input
2
4
1 3 3 4
4
2 3 3 4

Sample Output
0.5000000
1.0000000

Source
2013 Multi-University Training Contest 1
-----------------------------------------------------------.
题目大意:
就是跟你N个数代表长度为aia_i的木棒,现在问你随便拿出来三个就能构成三角形的概率为多少

解题思路:
首先考虑暴力的
就是求ai−aj<k<ai+aja_i-a_j<k <a_i+a_j满足题意的这样的值有多少个,那么这样的话,我们就需要知道,这N个数两两加的和是什么样的,计算出这个之后,我们在预处理出前缀和之后就可以通过枚举最长边来O(n)O(n)计算三角形的情况数,再除以Cn3=n∗(n−1)∗(n−2)6C_{n}^{3}=\frac{n*(n-1)*(n-2)}{6}就是概率了,

所以最严重的问题就是如何求这N个数的两两相加.
这时候如果把加法换成乘法那么就可以转化为向量相乘，用FFT就可以o(nlog2n)o(nlog_2n)解决了

然后我们考虑将加法换成乘法，其实很简单，我们只要将加数代换成幂指数的指数就可以了，
an∗am=an+ma^n*a^m=a^{n+m}

我们可以用一个hash[a[i]]来记录每个大小的数都有几个
那么FFT之后的结果稍加一点简单处理就是两个不同的木棍长度加和wei[i][i]的情况数

而我们要的就是这个情况数,所以就不需要在继续处理了

附本题链接
-----------------------------------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
# include <bits/stdc++.h>

using namespace std;

# define INF        (~(1<<31))
# define INFLL      (~(1ll<<63))
# define pb         push_back
# define mp         make_pair
# define abs(a)     ((a)>0?(a):-(a))
# define lalal      puts("*******");
# define s1(x)      scanf("%d",&x)
# define Rep(a,b,c) for(int a=(b);a<=(c);a++)
# define Per(a,b,c) for(int a=(b);a>=(c);a--)
# define no         puts("NO")

typedef long long int LL ;
typedef unsigned long long int uLL ;

const int    MOD = 1e9+7;
const int    N   = 264000+5;
const double eps = 1e-6;
const double PI  = acos(-1.0);
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void fre(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
}

/***********************************************************************/
struct Complex{
    double real, image;
    Complex(double _real, double _image){
        real = _real;
        image = _image;
    }
    Complex(){}

    Complex operator + (const Complex &tmp){
        return Complex(real + tmp.real, image + tmp.image);
    }
    Complex operator - (const Complex &tmp){
        return Complex(real - tmp.real, image - tmp.image);
    }
    Complex operator * (const Complex &tmp){
        return Complex(real*tmp.real - image*tmp.image, real*tmp.image + image*tmp.real);
    }
};
int rev(int id, int len){
    int ret = 0;
    for(int i = 0; (1 << i) < len; i++){
        ret <<= 1;
        if(id & (1 << i)) ret |= 1;
    }
    return ret;
}
Complex A[264000];
void FFT(Complex *a, int len, int DFT){
    for(int i = 0; i < len; i++)
        A[rev(i, len)] = a[i];
    for(int s = 1; (1 << s) <= len; s++){
        int m = (1 << s);
        Complex wm = Complex(cos(DFT*2*PI/m), sin(DFT*2*PI/m));
        for(int k = 0; k < len; k += m){
            Complex w = Complex(1, 0);
            for(int j = 0; j < (m >> 1); j++){
                Complex t = w*A[k + j + (m >> 1)];
                Complex u = A[k + j];
                A[k + j] = u + t;
                A[k + j + (m >> 1)] = u - t;
                w = w*wm;
            }
        }
    }
    if(DFT == -1) for(int i = 0; i < len; i++) A[i].real /= len, A[i].image /= len;
    for(int i = 0; i < len; i++) a[i] = A[i];
    return;
}


int num[100010]，h[200010];
Complex a[264000];
LL tA[200010]，sum[200010];

int main()
{
    int _, n;
    while(~scanf("%d", &_))
    while(_--)
    {
        scanf("%d", &n);
        int mx = 0;
		memset(h, 0, sizeof(h));
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &num[i]);
			h[num[i]]++;
        }
        sort(num+1, num + n+1);
        mx = num[n];

		int len = 1;
        while(len <= mx) len <<= 1;  len <<= 1;
        for(int i = 0; i < len; i++)  a[i] = Complex((i<=mx)?h[i]:0, 0);

        FFT(a, len, 1);
        for(int i = 0; i < len; i++)   a[i] = a[i]*a[i];
        FFT(a, len, -1);
        for(int i = 0; i <= (mx<<1); i++)   tA[i] = (LL)(a[i].real + 0.5);

		for(int i=0;i<=n;i++) tA[num[i]<<1]--;
        for(int i = 0; i <= (mx<<1); i++)  tA[i] >>=1;
        //到现在为止A[i]表示的是去两根不同的branch的长度和为i的组合种数
        sum[0] = 0;
        for(int i = 1; i <= (mx<<1); i++)  sum[i] = sum[i - 1] + tA[i];
        LL ans = 0;

        for(int i = 1; i <= n; i++)//以第i根作为边最长的
        {
            LL tmp = sum[(mx<<1)] - sum[num[i]];//另外两条边长度和要大于branch[i]
            tmp -= (LL)(n - i)*(i - 1);//另外两条一条比branch[i]长, 一条不比它长
            tmp -= (LL)(n - i)*(n - i - 1) / 2;//两条都比他长
            tmp -= n - 1;//另外两条的组合中包括它自己的组合
            ans += tmp;
        }
        printf("%.7f\n",ans*6./n/(n - 1)/(n - 2));
    }
    return 0;
}