题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4609
题目描述：给出n个数， 问其中选出三个能组成三角形的概率
解题思路：给出kuangbin巨巨的解题思路， 实在是没有比这儿更好的题解， 所以我就不误导别人和自己了
http://www.cnblogs.com/kuangbin/archive/2013/07/24/3210565.html
题目代码：
#include#include #include #include #include using namespace std;const double PI = acos(-1.0);struct Complex { double x, y; Complex(double _x = 0.0, double _y = 0.0) { x = _x; y = _y; } Complex operator -(const Complex &b)const { return Complex(x-b.x, y-b.y); } Complex operator +(const Complex &b)const { return Complex(x+b.x, y+b.y); } Complex operator *(const Complex &b)const { return Complex(x*b.x-y*b.y, x*b.y+y*b.x); }};void change(Complex y[], int len) { int i, j, k;// cout << len << endl;// cout << "-----" << endl; for(i = 1, j = len/2; i < len-1; i++) { if( i < j ) swap(y[i], y[j]); k = len / 2; while( j >= k ) { j -= k; k /= 2;// cout << "----" << endl;// cout << j << " " << k << endl; } if( j < k ) j += k;// cout << "==" << endl; }// cout << "-----" << endl;// cout << "-------------" << endl;}void fft(Complex y[], int len, int on) { change(y, len);// cout << "----" << endl; for(int h = 2; h <= len; h <<= 1) { Complex wn(cos(-on*2*PI/h), sin(-on*2*PI/h)); 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( on == -1 ) { for( int i = 0; i < len; i++ ) { y[i].x /= len; } }}const int MAXN = 400040;Complex x1[MAXN];int a[MAXN/4];long long num[MAXN];long long sum[MAXN];int main() { int t; int n; scanf( "%d", &t); while( t-- ) { scanf( "%d", &n ); memset( num, 0, sizeof( num ) ); for( int i = 0; i < n; i++ ) { scanf( "%d", &a[i] ); num[a[i]]++; // 记录a[i]出现的次数 }// cout << "=====" << endl; sort(a, a+n); int len1 = a[n-1] + 1; // len 为最长边的界 int len = 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); }// cout << "======" << endl; fft(x1, len, 1);// cout << "-----" << endl; for( int i = 0; i < len; i++ ) { x1[i] = x1[i] * x1[i]; } fft(x1, len, -1);// cout << "-----" << endl; for( int i = 0; i < len; i++ ) { num[i] = (long long)(x1[i].x + 0.5); } len = 2 * a[n-1]; // 教程中 界为 2n 必须由 2n 个点来确定 for(int i = 0; i < n; i++ ) { num[a[i]+a[i]]--; // 去重 } for(int i = 1; i <= len; i++ ) { num[i] /= 2; // 卷积后求得是排列数， 组合数除以2 } sum[0] = 0; for( int i = 1; i <= len; i++ ) { sum[i] = sum[i-1] + num[i]; } long long cnt = 0; for( int i = 0; i < n; i++ ) { cnt += sum[len] - sum[a[i]]; // 长度和 大于 a[i] 的个数 cnt -= (long long)(n-1-i)*i; // 减去一大一小 cnt -= (n-1); // 减去包括本身的 cnt -= (long long)(n-1-i)*(n-2-i)/2; // 减去两个大的组合数 } long long tot = (long long)n * (n-1) * (n-2) / 6;// cout << cnt << "===" << tot << endl; printf( "%.7lf\n", (double)cnt / tot ); } return 0;}
思考： 首先这道题要让我看到了fft 的一种应用， 那就是排列组合 ， 如果遇到加和的组合的可以往fft的方向想， 因为如果a[k]x^k中， k表示 加数时， a[k]代表数量的话， 那么卷积后的a[k']x^k' 中的 加和 k' 的所有排列数位 a[k'] ， 因为A^k1 * B^k2 = A^(k1+k2), 这个设计状态也很重要。
以后要多做题， 多动脑子。