【HDU】4609 3-idiots 【FFT】

本文主要是介绍【HDU】4609 3-idiots 【FFT】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门：【HDU】4609 3-idiots

题目分析：

我们考虑两边长度之和为$n$的方案数，设$num[x]$为长度为$x$的个数，那么$\sum_{x=1}^{n}{num[n-x]*num[x]}$即两边长度之和为$n$的方案数。容易发现这这正是卷积！

然后我们就可以愉快的用$FFT$预处理出所有的两边长度之和为i的方案数。$FFT$求出来的第$i$项的系数就是方案数。由于$FFT$处理出来的是重复的，以及部分非法的（自己和自己构成两边之和），这些我们可以很容易的去除：设长度为$x$的方案数为$ans$，如果长度$x$为偶数，首先$ans = ans - num[\frac{x}{2}]$，之后$ans=\frac{ans}{2}$。

接下来，我们枚举两边长度之和$i$，易知第三边长度$x\geq{i}$的都是不合法的，这样我们减去就好了。这时候我很自然的想到了一种情况：如果$i=5$，其中包含情况$x=1,y=4,x+y=i$，此时如果第三条边长度为2，那不是不合法么？然而我们不需要担心。因为在$x=1,y=2,x+y=3,z=4$的时候我们就已经排除了，所以这样所有不合法的情况我们都恰好排除了。
上面的过程我们用到了容斥的思想。

my code：

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std ;typedef long long LL ;#define clr( a , x ) memset ( a , x , sizeof a )
#define cpy( a , x ) memcpy ( a , x , sizeof a )const int MAXN = 100005 ;
const double pi = acos ( -1.0 ) ;struct Complex {double r , i ;Complex () {}Complex ( double r , double i ) : r ( r ) , i ( i ) {}Complex operator + ( const Complex& t ) const {return Complex ( r + t.r , i + t.i ) ;}Complex operator - ( const Complex& t ) const {return Complex ( r - t.r , i - t.i ) ;}Complex operator * ( const Complex& t ) const {return Complex ( r * t.r - i * t.i , r * t.i + i * t.r ) ;}
} ;void FFT ( Complex y[] , int n , int rev ) {for ( int i = 1 , j , t , k ; i < n ; ++ i ) {for ( j = 0 , t = i , k = n >> 1 ; k ; k >>= 1 , t >>= 1 ) j = j << 1 | t & 1 ;if ( i < j ) swap ( y[i] , y[j] ) ;}for ( int s = 2 , ds = 1 ; s <= n ; ds = s , s <<= 1 ) {Complex wn ( cos ( rev * 2 * pi / s ) , sin ( rev * 2 * pi / s ) ) , w ( 1 , 0 ) , t ;for ( int k = 0 ; k < ds ; ++ k , w = w * wn ) {for ( int i = k ; i < n ; i += s ) {y[i + ds] = y[i] - ( t = w * y[i + ds] ) ;y[i] = y[i] + t ;}}}if ( rev == -1 ) for ( int i = 0 ; i < n ; ++ i ) y[i].r /= n ;
}int num[MAXN] , sum[MAXN] ;
int n ;
Complex y[MAXN << 2] ;void solve () {int x , n1 = 1 , maxv = 0 ;clr ( num , 0 ) ;scanf ( "%d" , &n ) ;for ( int i = 0 ; i < n ; ++ i ) {scanf ( "%d" , &x ) ;num[x] ++ ;maxv = max ( maxv , x ) ;}while ( n1 <= 2 * maxv ) n1 <<= 1 ;for ( int i = 0 ; i <= maxv ; ++ i ) y[i] = Complex ( num[i] , 0 ) ;for ( int i = maxv + 1 ; i < n1 ; ++ i ) y[i] = Complex ( 0 , 0 ) ;FFT ( y , n1 , 1 ) ;for ( int i = 0 ; i < n1 ; ++ i ) y[i] = y[i] * y[i] ;FFT ( y , n1 , -1 ) ;for ( int i = 1 ; i <= maxv ; ++ i ) sum[i] = sum[i - 1] + num[i] ;LL tot = ( LL ) n * ( n - 1 ) * ( n - 2 ) / 6 , ans = tot ;for ( int i = 2 ; i <= maxv ; ++ i ) {LL x = ( LL ) ( y[i].r + 0.5 ) ;if ( i % 2 == 0 ) x -= num[i / 2] ;x /= 2 ;ans -= x * ( n - sum[i - 1] ) ;}printf ( "%.7f\n" , ( double ) ans / tot ) ;
}int main () {int T ;scanf ( "%d" , &T ) ;for ( int i = 1 ; i <= T ; ++ i ) solve () ;return 0 ;
}

这篇关于【HDU】4609 3-idiots 【FFT】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---