0w1

CFR 696 C. PLEASE ( Math )

Problem - 696C - Codeforces

題意:
給你 K 個數 A[ i ],代表 N = PI{ A[ i ], for all i }。
有三個杯子,一開始中間的杯子裡面有寶物,每回合平等隨機地選左邊的或右邊的杯子,和中間的杯子交換。求 N 回合後,寶物在中間的機率。以分數形式表示,並分別取模。若答案的分數是可以化簡的,請先化簡後再取模。

資料規模:
The first line of input contains a single integer k (1 ≤ k ≤ 1e5) — the number of elements in array Barney gave you.
The second line contains k integers a1, a2, ..., ak (1 ≤ ai ≤ 1e18) — the elements of the array.
TL: 1000 ms
ML: 256 MB

解法:
dp[ i ]:i 回合後寶物在中間的機率
dp[ 0 ] = 1, dp[ 1 ] = 0, dp[ 2 ] = 0.5,
dp[ i ] = ( 1 - dp[ i - 1 ] ) * 0.5
dp[ i ] = -0.5 * dp[ i -1 ] + 0.5
ー> 解特徵方程式
x = -0.5 * x + 0.5, x = 1/3
dp[ i ] - 1/3 = -0.5 * ( dp[ i - 1 ] - 1/3 )
dp[ i ] = ( -0.5 )^i * ( dp[ 0 ] - 1/3 ) + 1/3
________= ( -1/2 )^i * ( 2/3 ) + 1/3
________= 1/3 * ( 1 + ( -1 )^i / 2^( i - 1 ) ) = p / q
ー> p = inverse( 3 ) * ( 2^( i - 1 ) + ( -1 )^i )
__ q = 2^( i - 1 )
又因為 p 是奇數,q 是偶數,gcd( p, q ) 必為 1,所以不必多做什麼處理。

時間 / 空間複雜度:
O( K * lg( A ) )

int K;
vl A;

void init(){
  cin >> K;
  A = vl( K );
  for( int i = 0; i < K; ++i ){
    cin >> A[ i ];
  }
}

int int_pow( int v, ll p ){
  int res = 1;
  while( p ){
    if( p & 1LL ){
      res = 1LL * res * v % MOD7;
    }
    p >>= 1;
    v = 1LL * v * v % MOD7;
  }
  return res;
}

int inv( int v ){
  return int_pow( v, MOD7 - 2 );
}

void solve(){
  int odd = 1;
  int q = 2;
  for( int i = 0; i < K; ++i ){
    if( ~A[ i ] & 1LL ){
      odd = 0;
    }
    q = int_pow( q, A[ i ] ) % MOD7;
  }
  q = 1LL * q * inv( 2 ) % MOD7;
  int p = ( ( odd ? -1LL : 1LL ) + q ) * inv( 3 ) % MOD7;
  if( p < 0 ) p += MOD7;
  cout << p << "/" << q << endl;
}