Specific birthday problem.

Question

Consider the the place where one year equal to $2^{n}$ days. Now, let's represent our birthday problem into this place. Consider the $k$ person among people from this planet.

Now, we have: $$p(n,k) = 1-\frac{\prod_{i = 1}^{k}(2^{n} - i)}{2^{nk}}$$, is probability that $2$ people from this group have the same birthday. I guess , that it's easy to get, so I would to know: does there some close form of this expression. Actually I want to represent this into irreducible fraction.

Answer 1

You probably want this to solve this problem in codeforces:

Here are the key ideas to solve it.

If $k>MOD$ then $A$ is $0$, if $k>2^n$ then $A=1,B=1$.

Otherwise you can use modular arithmetic to calculate $\prod_{k=0}^{-1}n-i\bmod MOD$.

You can also calculate $2^{2^{k\times n}}$ fast using modular exponentiation.

finally you have to calculate the GCD of the numerator and the denominator. To do this you can use polignac's formula, notice that the $2^n$ in the numerator clearly cancels out. And after that you can notice that the maximum of power of $2$ dividing $2^n-j$ is the same as the maximum power of $2$ dividing $j$, for $1\leq j\leq k-1$.

So the term that needs to be canceled is $2^{n+P((k-1)!)}$.

Where $P(k!)$ is the maximum power of $2$ dividing $n!$, this can be calculated using polignac's formula.

Here is my c++ code:

#include <bits/stdc++.h>
using namespace std;
typedef long long lli;

lli MOD=1000003;

lli power(lli b, lli e){
    lli res=1;
    while(e){
        if(e%2) res=(res*b)%MOD;
        e/=2;
        b=(b*b)%MOD;
    }
    return(res);
}

lli poder(lli b, lli e){
    lli res=1;
    while(e){
        if(e%2) res=(res*b);
        e/=2;
        b=(b*b);
    }
    return(res);
}

lli inv(lli b){
    return(power(b,MOD-2));
}

lli polig(lli k){
    lli res=0;
    while(k){
        res+=k/2;
        k/=2;
    }
    return(res);
}

int main(){
    lli n,k;
    scanf("%lld %lld",&n,&k);
    if(n<=62 && k>poder(2,n) ){
        printf("1 1\n");
        return(0);
    }
    lli B=power(2,n);
    lli A=1;
    if(k>=MOD) A=0;
    else{
        for(int i=0;i<k;i++){
            A= (A*(MOD+B- (i%MOD) )%MOD )%MOD;
        }
    }
    lli cancel=n;
    cancel+=polig(k-1);
    B=power(B,k);
    A=(MOD+B-A)%MOD;
    A=( A*inv(power(2,cancel) ) ) %MOD;
    B=( B*inv(power(2,cancel) ) ) %MOD;
    printf("%lld %lld\n",A,B);
}