【题目链接】 点击打开链接
【题意】 其实题目是给了n条线段。问随机取三个，可以组成三角形的概率。
【解题思路】 下面解题方法摘抄自 kb大神blog
其实就是要求n条线段，选3条组成三角形的选法有多少种。
首先题目给了a数组，
如样例一：
4
1 3 3 4
把这个数组转化成num数组，num[i]表示长度为i的有num[i]条。
样例一就是
num = {0 1 0 2 1}
代表长度0的有0根，长度为1的有1根，长度为2的有0根，长度为3的有两根，长度为4的有1根。
使用FFT解决的问题就是num数组和num数组卷积。
num数组和num数组卷积的解决，其实就是从{1 3 3 4}取一个数，从{1 3 3 4}再取一个数，他们的和每个值各有多少个
例如{0 1 0 2 1}*{0 1 0 2 1} 卷积的结果应该是{0 0 1 0 4 2 4 4 1 }
长度为n的数组和长度为m的数组卷积，结果是长度为n+m-1的数组。
{0 1 0 2 1}*{0 1 0 2 1} 卷积的结果应该是{0 0 1 0 4 2 4 4 1 }。
这个结果的意义如下：
从{1 3 3 4}取一个数，从{1 3 3 4}再取一个数
取两个数和为 2 的取法是一种：1+1
和为 4 的取法有四种：1+3， 1+3 ，3+1 ，3+1
和为 5 的取法有两种：1+4 ，4+1；
和为 6的取法有四种：3+3,3+3,3+3,3+3,3+3
和为 7 的取法有四种： 3+4,3+4,4+3,4+3
和为 8 的取法有 一种：4+4
利用FFT可以快速求取循环卷积，具体求解过程不解释了，就是DFT和FFT的基本理论了。
总之FFT就是快速求到了num和num卷积的结果。只要长度满足>=n+m+1.那么就可以用循环卷积得到线性卷积了。
弄完FFT得到一个num数组，这个数组的含义在上面解释过了。
这里代码中的num数组就是卷积后的结果，表示两两组合。
但是题目中本身和本身组合是不行的，所有把取同一个的组合的情况删掉。
还有，这个问题求组合，所以第一个选t1,第二个选t2,和第一个选t2,第二个选t1,我们认为是一样的。
所有num数组整体除于2
然后对num数组求前缀和
之后就开始O(n)找可以形成三角形的组合了。
a数组从小到大排好序。
对于a[i]. 我们假设a[i]是形成的三角形中最长的。这样就是在其余中选择两个和>a[i],而且长度不能大于a[i]的。（注意这里所谓的大于小于，不是说长度的大于小于，其实是排好序以后的，位置关系，这样就可以不用管长度相等的情况，排在a[i]前的就是小于的，后面的就是大于的）。
根据前面求得的结果。
长度和大于a[i]的取两个的取法是sum[len]-sum[a[i]].
但是这里面有不符合的。
一个是包含了取一大一小的
cnt -= (long long)(n-1-i)*i;
一个是包含了取一个本身i,然后取其它的
cnt -= (n-1);
还有就是取两个都大于的了
cnt -= (long long)(n-1-i)*(n-i-2)/2;
【给出完整代码】
//
//Created by BLUEBUFF 2016/1/9
//Copyright (c) 2016 BLUEBUFF.All Rights Reserved
//
#pragma comment(linker,"/STACK:102400000,102400000")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <time.h>
#include <cstdlib>
#include <cstring>
#include <complex>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define REP3(i, a, b) for(int i = a; i >= b; i--)
#define CLR(a, b) memset(a, b, sizeof(a))
#define MP(x, y) make_pair(x,y)
template <class T1, class T2>inline void getmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void getmin(T1 &a, T2 b) { if (b<a)a = b; }
const int maxn = 400010;
const int maxm = 100010;
const int maxs = 10;
const int maxp = 1e3 + 10;
const int INF = 1e9;
const int UNF = -1e9;
const int mod = 1e9 + 7;
const double PI = acos(-1);
//head
struct FastIO
{
static const int S = 1310720;
int wpos;
char wbuf[S];
FastIO() : wpos(0) {}
inline int xchar()
{
static char buf[S];
static int len = 0, pos = 0;
if (pos == len)
pos = 0, len = fread(buf, 1, S, stdin);
if (pos == len) return -1;
return buf[pos ++];
}
inline int xuint()
{
int c = xchar(), x = 0;
while (c <= 32) c = xchar();
for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
return x;
}
inline int xint()
{
int s = 1, c = xchar(), x = 0;
while (c <= 32) c = xchar();
if (c == '-') s = -1, c = xchar();
for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
return x * s;
}
inline void xstring(char *s)
{
int c = xchar();
while (c <= 32) c = xchar();
for (; c > 32; c = xchar()) * s++ = c;
*s = 0;
}
inline void wchar(int x)
{
if (wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0;
wbuf[wpos ++] = x;
}
inline void wint(LL x)
{
if (x < 0) wchar('-'), x = -x;
char s[24];
int n = 0;
while (x || !n) s[n ++] = '0' + x % 10, x /= 10;
while (n--) wchar(s[n]);
}
inline void wstring(const char *s)
{
while (*s) wchar(*s++);
}
~FastIO()
{
if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
}
} io;
typedef complex <double> Complex;
void rader(Complex *y, int len) {
for(int i = 1, j = len / 2; i < len - 1; i++) {
if(i < j) swap(y[i], y[j]);
int k = len / 2;
while(j >= k) {j -= k; k /= 2;}
if(j < k) j += k;
}
}
void fft(Complex *y, int len, int op) {
rader(y, len);
for(int h = 2; h <= len; h <<= 1) {
double ang = op * 2 * PI / h;
Complex wn(cos(ang), sin(ang));
for(int j = 0; j < len; j += h) {
Complex w(1, 0);
for(int k = j; k < j + h / 2; k++) {
Complex u = y[k];
Complex t = w * y[k + h / 2];
y[k] = u + t;
y[k + h / 2] = u - t;
w = w * wn;
}
}
}
if(op == -1) for(int i = 0; i < len; i++) y[i] /= len;
}
int n, a[maxn / 4];
Complex x1[maxn];
LL num[maxn], sum[maxn];
int main()
{
int T;
//scanf("%d", &T);
T = io.xint();
while(T--)
{
memset(num, 0, sizeof(num));
memset(sum, 0, sizeof(sum));
//scanf("%d", &n);
n = io.xint();
for(int i = 0; i < n; i++){
//scanf("%d", &a[i]);
a[i] = io.xint();
num[a[i]]++;
}
sort(a, a + n);
int len = 1, len1 = a[n - 1] + 1;
while(len < 2 * len1) len <<= 1;
for(int i = 0; i < len1; i++) x1[i] = Complex(num[i], 0);
for(int i = len1; i < len; i++) x1[i] = Complex(0, 0);
fft(x1, len, 1);
for(int i = 0; i < len; i++) x1[i] = x1[i] * x1[i];
fft(x1, len, -1);
for(int i = 0; i < len; i++) num[i] = (LL) (x1[i].real() + 0.5);
len = 2 * a[n - 1];
//减去两个相同的组合
for(int i = 0; i < n; i++) num[a[i] + a[i]]--;
//选择无序，除以2
for(int i = 1; i <= len; i++) num[i] /= 2;
sum[0] = 0;
for(int i = 1; i <= len; i++) sum[i] = sum[i - 1] + num[i];
//O(n)计算答案
LL cnt = 0;
//枚举一条边作为三角形最大的边
for(int i = 0; i < n; i++){
//
cnt += sum[len] - sum[a[i]];
//减掉一个取大，一个取小
cnt -= (LL) (n - i - 1) * i;
//减掉一个取本身，一个取其他
cnt -= (LL) (n - 1);
//减掉一个取大，另一个也取大
cnt -= (LL) (n - i -1) * (n - i - 2) / 2;
}
LL ans = (LL) n * (n - 1) * (n - 2) / 6;
printf("%.7f\n", (double) cnt / ans);
}
return 0;
}
京公网安备 11010502036488号