当前位置: 华文星空 > 心灵

acm哪些脑洞令人叹为观止?

2016-05-09心灵

昨天学习杜教代码的时候看到了一个黑科技(先上代码让大家感受一下)

VI gao ( int n ) { VI ret ( p + 1 , 0 ); if ( n == 0 ) { ret [ 0 ] = 1 ; } else if ( n % 2 == 0 ) { VI c = gao ( n / 2 ); rep ( i , 0 , p + 1 ) rep ( j , 0 , p + 1 ) if ( i + j <= p ) ret [ i + j ] += c [ i ] * c [ j ]; } else { VI c = gao ( n - 1 ); rep ( i , 0 , p + 1 ) rep ( j , 0 , 2 ) if ( i + j <= p ) ret [ i + j ] += c [ i ]; } return ret ; }

这段代码返回一个vector,其第i项是C_n^i


我们知道求C_n^i 有一个经典的递推的方法:C_n^i = C_n^{i - 1} * \frac{n - i + 1} {i}

这种方法因为有除法,在要模的数是一个合数的时候就不适用了

此时,通常的做法就是根据上述公式每次暴力求i和前面那些项的gcd,然后除掉,我也一直是这样写的,

直到昨天看到杜教的代码……