hdu 4609 3-idiots(FFT+去重处理)
2024-10-07 16:58:14
3-idiots
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.
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.
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
题意给你n个木棍,问从中选出三根能组成一个三角形,那么有多少种选法?求出合法选法除以总选法的概率
FFT可以处理选择任意两个木棍,这两个木棍的和的情况数,我们这里是算了好多重复的比如选了a[i]又选了a[i],我需要减一下
再一想选x选y跟选y选x是一样的,我们再除以2,我们对两根木棍的和的情况求一个前缀和
然后我们枚举a[i]作为三个木棍中最长的一个,我们先对答案笼统的加上剩下两根木棍和大于a[i]的情况数
我们还要减去剩下两个木棍一根>=a[i]另一根<=a[i]的情况,再减去剩下两根木棍都>a[i]的情况,再减去剩下两根木棍中a[i]又被选了的情况
统计一下就是答案了
#include <bits/stdc++.h> using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int maxn = 4e5+;
struct Complex
{
double r,i;
Complex(double _r,double _i):r(_r),i(_i){}
Complex(){}
Complex operator +(const Complex &b)
{
return Complex(r+b.r,i+b.i);
}
Complex operator -(const Complex &b)
{
return Complex(r-b.r,i-b.i);
}
Complex operator *(const Complex &b)
{
return Complex(r*b.r-i*b.i,r*b.i+i*b.r);
}
};
void change(Complex y[],int len)
{
int i,j,k;
for(i = , j = len/;i < len-;i++)
{
if(i < j)swap(y[i],y[j]);
k = len/;
while( j >= k)
{
j -= k;
k /= ;
}
if(j < k)j += k;
}
}
void fft(Complex y[],int len,int on)
{
change(y,len);
for(int h = ;h <= len;h <<= )
{
Complex wn(cos(-on**pi/h),sin(-on**pi/h));
for(int j = ;j < len;j += h)
{
Complex w(,);
for(int k = j;k < j+h/;k++)
{
Complex u = y[k];
Complex t = w*y[k+h/];
y[k] = u+t;
y[k+h/] = u-t;
w = w*wn;
}
}
}
if(on == -)
for(int i = ;i < len;i++)
y[i].r /= len;
}
int n;
int a[maxn];
ll num[maxn],sum[maxn];
Complex A[maxn];
int main()
{
//freopen("de.txt","r",stdin);
int T;
scanf("%d",&T);
while (T--){
memset(num,,sizeof num);
scanf("%d",&n);
for (int i=;i<n;++i) scanf("%d",&a[i]),num[a[i]]++;
sort(a,a+n);
int len=;
int len1=a[n-]+;
while (len<*len1) len<<=;
for (int i=;i<len1;++i)
A[i]=Complex(num[i],);
for (int i=len1;i<len;++i)
A[i]=Complex(,);
fft(A,len,);
for (int i=;i<len;++i)
A[i]=A[i]*A[i];
fft(A,len,-);
for (int i=;i<len;++i) num[i]=(ll)(A[i].r+0.5);
len = *a[n-];
for (int i=;i<n;++i)
num[a[i]+a[i]]--;
for (int i=;i<=len;++i)
num[i]/=;
sum[]=;
for (int i=;i<=len;++i) sum[i]=sum[i-]+num[i];
ll ans = ;
for (int i=;i<n;++i){
ans+=sum[len]-sum[a[i]];
ans-=(ll)(n-i-)*i;
ans-=n-;
ans-=(long long)(n-i-)*(n-i-)/;
}
ll tot =(long long )(n-)*n*(n-)/;
printf("%.7f\n",(double)ans/tot);
}
return ;
}
最新文章
- linux内核调试技术之自构proc
- Centos 6.5 安装ELK
- [转]Java中Map的用法详解
- php工作笔记5-css定位
- ";微空间";免费空间很棒哦,很适合中小网站站长
- Java多线程系列--“基础篇”05之 线程等待与唤醒
- Android视频播放之VideoView
- 不重启程序使用最新版package
- centos vpn
- 问题与解答 [Questions &; Answers]
- P2P/WSN信任建模与仿真平台
- TravelCMS旅游网站系统诞生记-1(后台框架篇)
- Composer加速
- 我是如何理解ThreadLocal
- VMware Ubuntu16.04虚拟机安装MATLAB R2016b
- asp.net上传文件限制解决方案
- 《我们不一样》Alpha冲刺_1-5
- javascript事件流机制
- 题解 luogu P1144 【最短路计数】
- Paint House