HR Colliding Circles ( Math, Expectation )

Programming Problems and Competitions :: HackerRank

題意：
有 N 個線段，用長度描述。每一秒以均等機率有兩個線段合併 ( 長度變為總和 )。問期望上 K 秒後，每個線斷所成的圓面積總和為何。

制約：
1 ≤ N ≤ 1e5
0 ≤ K ≤ N - 1
0 ≤ R[ i ] ≤ 1e4

解法：
首先要想辦法獨立。
每項自身的貢獻 R[ i ] * R[ i ] 除去後，考慮合併的貢獻。
對於任意的 i ≠ j，若 i, j 屬於同一集合，會有額外的貢獻 R[ i ] * R[ j ]。
由於機率均等，問題的核心在於求得任意 i, j 於 K 秒後在同一個集合的機率。
這個機率和 i, j 無關，可以遞推出來：
f( n, k )：n 個點，在 k 秒後對於任意特定的兩個點在同一個集合的機率。
由於若當前有 n 個點，任意兩個特定的點在這一刻合併的機率為 2 / n / ( n - 1 )：
f( n, k ) = 2 / n / ( n - 1 ) + ( 1 - 2 / n / ( n - 1 ) ) * f( n - 1, k - 1 )
答案便是 PI * ( f( n, k ) * sum( R[ i ] * R[ j ] for all i ≠ j ) + sum( R[ i ] * R[ i ] ) )

時間 / 空間複雜度：
O( N )

from math import acos

N, K = map( int, input().split() )
R = list( map( int, input().split() ) )

prob, fail = 0.0, 1.0
for i in range( K ):
  prob += fail * 2 / ( N - i ) / ( N - i - 1 )
  fail *= 1 - 2 / ( N - i ) / ( N - i - 1 )

t = sum( R[ i ] * R[ i ] for i in range( N ) )
s = sum( R )
print( "%.10f" % ( acos( -1 ) * ( ( s * s - t ) * prob + t ) ) )