Suhendry’s Blog

B - Liar Game

Problem: B - Liar Game
Author: Felix Halim

Pertama kita harus terlebih dahulu mengetahui bagaimana cara menghitung P seperti yang diminta oleh soal.

Setiap kartu memiliki dua buah sisi, dengan demikian probabilitas untuk mendapatkan poin dalam satu round adalah 1/2N. Misalnya N = 2, maka kemungkinan kartu yang keluar adalah:

• Keluar Back, dibalik Joker: win
• Keluar Joker, dibalik Back: lose (aturan 2)
• Keluar Back₁, dibalik Back₂: lose (aturan 3)
• Keluar Back₂, dibalik Back₁: lose (aturan 3)

Pada contoh di atas, probabilitas mendapatkan 1 poin dalam 1 round adalah 1/4.

Dengan demikian probabilitas untuk tidak mendapatkan poin dalam 1 round adalah (2N-1)/2N. Untuk menghitung probabilitas mendapatkan tepat K poin dalam R round, kita bisa menggunakan rumus kombinasi: P = (1/2N)^K * ((2N-1)/2N)^R-K * NCK(R,K), atau bisa disederhanakan menjadi: P = 1^K * (2N-1)^R-K * (1/2N)^R * NCK(R,K). Karena yang diminta soal adalah P * (2N)^R, maka solusi yang kita cari menjadi (2N-1)^R-K * NCK(R,K).

Menghitung (2N-1)^R-K mod M tidaklah masalah karena bisa dilakukan dalam O(R-K). Namun bagaimana dengan NCK(R,K) mod M? Seperti yang kita ketahui NCK(R,K) bisa dihitung dengan rumus R!/K!(R-K)!, namun bagaimana mengatasi pembagian modular?

Ada beberapa cara yang bisa digunakan untuk menghitung NCK(R,K) mod M dengan cepat:

• Precalculate semua faktor prima dari 1..100000 menggunakan teknik sieve eratosthenes. Jumlah faktor prima berbeda dari masing masing bilangan tidak lebih dari 7. Dengan demikian untuk menghitung R!/K!(R-K)! cukup dengan mencari selisih faktor prima dari R! dengan K!(R-K)!.
• Banyaknya faktor prima dari R! bisa dihitung lebih cepat dengan menggunakan Legendre (banyaknya faktor x dari n! adalah n/x¹ + n/x² + n/x³ + …)
• Pembagian dengan modulo bilangan prima bisa diatasi dengan Fermat Little Theorm.

Solusi C/C++
oleh Suhendry Effendy

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn = 100005;
const int mod  = 1000003;

bool isp[maxn];
vector <pair<int,int> > v[maxn];

int power(int a, int b) {
   if ( b == 0 ) return 1;
   int x = power(a,b/2);
   int ret = ((long long)x * x) % mod;
   if ( b % 2 == 1 ) ret = ((long long)ret * a) % mod;
   return ret % mod;
}

int main()
{
   memset(isp,true,sizeof(isp));
   for ( int i = 2; i < maxn; i++ ) if ( isp[i] ) {
      v[i].push_back(make_pair(i,1));
      for ( int j = i + i; j < maxn; j += i ) {
         int x = 0, n = j;
         while ( n % i == 0 ) n /= i, x++;
         v[j].push_back(make_pair(i,x));
         isp[j] = false;
      }
   }

   int n, r, k;
   while ( scanf( "%d %d %d", &n, &r, &k ) == 3 ) {
      int arr[maxn] = {0};
      for ( int i = 1; i <= k; i++ ) {
         for ( int j = 0; j < v[r-i+1].size(); j++ )
            arr[v[r-i+1][j].first] += v[r-i+1][j].second;
         for ( int j = 0; j < v[i].size(); j++ )
            arr[v[i][j].first] -= v[i][j].second;
      }
      int ans = 1;
      for ( int i = 1; i <= r-k; i++ )
         ans = ((long long)ans * (2*n-1)) % mod;
      for ( int i = 1; i <= r; i++ )
         ans = ((long long)ans * power(i,arr[i])) % mod;
      printf( "%d\n", ans % mod );
   }
   return 0;
}

• Problem A - General Election
• Problem B - Liar Game
• Problem C - Why is Math Book So Sad?
• Problem D - Noodle Team Contest
• Problem E - Palapa Number
• Problem F - New House

Pages: 1 2 3 4 5 6 7