首页 > 代码库 > HDU 4609 3-idiots fft
HDU 4609 3-idiots fft
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4609
题目描述:给出n个数, 问其中选出三个能组成三角形的概率
解题思路:给出kuangbin巨巨的解题思路, 实在是没有比这儿更好的题解, 所以我就不误导别人和自己了
http://www.cnblogs.com/kuangbin/archive/2013/07/24/3210565.html
题目代码:
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <cstring> 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), 这个设计状态也很重要。
以后要多做题, 多动脑子。
HDU 4609 3-idiots fft
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。