PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Author: Utkarsh Gupta
Tester: Tejas Pandey
Editorialist: Daanish Mahajan
DIFFICULTY:
Medium
PREREQUISITES:
Expectation, Probability, Binomial Theorem, Geometric Series Sum
PROBLEM:
Chef is playing a game, which he starts with a score of S = 0. He also has an integer N.
In one move, Chef does the following:
- Uniformly randomly pick an integer X between 0 and 2^N - 1 (inclusive of both ends)
- Update his score as S \rightarrow S \mid X, where \mid denotes the bitwise OR operation
Chef stops when his score S becomes equal to 2^N-1. What is the expected number of moves Chef performs? Output the answer modulo 10^9 + 7.
EXPLANATION:
Subtask 1 Solution
Define S_i the state in which S has exactly i bits set.
Let E[X_i] denote the expected number of moves to get N bits set if at present exactly i bits are set and P_{i, j} denote the probability of moving from state S_i \rightarrow S_j (where j \ge i since the number of set bits won’t reduce with OR operation).
So we can write:
E[X_i] = 1 + \sum_{j = i}^{N} E[X_j] \cdot P_{i, j}
where E[X_N] = 0 and P_{i, j} = \frac{\binom{N - i}{j - i}}{2 ^ {N - i}}
P_{i, j} explanation
If we have i bits set currently, then N - i bits are unset. Out of these N - i bits we want exactly j - i more bits to set, so we choose the same in \binom{N - i}{j - i} and divide the expression with total possibilities for the N - i unset bits to get the required probability.
Finally, our answer is E[0].
The complexity for the same is \mathcal{O}(N ^ 2) but requires you to precompute factorials, the inverse of factorials, and the inverse of powers of 2.
If you try optimizing the \mathcal{O}(N^2) solution, you will find that there’s no way to do so if we follow the previous approach. Here’s when basics come into the picture.
Main Solution
Answer = \sum_{i = 1}^{\infty} i \cdot P_i where P_i denotes probability that the process ends in exactly i steps.
The equation can be rewritten as: Answer
= (P_1 + P_2 + P_3 + \ldots + P_{\infty}) + (P_2 + P_3 + \ldots + P_{\infty}) + (P_3 + \ldots + P_{\infty}) + \ldots
= \sum_{i = 1}^{\infty} Q_i (where Q_i denotes the probability that the process needs at least i steps before finish)
Q_i explanation
Q_i = 1 - R_{i - 1} (where R_{i - 1} denotes the probability that the process needs atmost i - 1 steps before finish)
Now important observation here to calculate R_{i - 1} is to consider each bit independently. Therefore:
R_{i - 1} = B^{N} where B denotes the probability that the process needs atmost i - 1 steps to set one bit.
So, B = 1 - probability that the bit remains unset after i - 1 steps = 1 - \frac{1}{2^{i - 1}}.
= \sum_{i = 1}^{\infty} 1 - (1 - \frac{1}{2^{i - 1}})^N
= \sum_{i = 1}^{\infty} 1 - (\sum_{j = 0}^{N} \binom{N}{j} (- \frac{1}{2^{i - 1}})^j)
= \sum_{i = 1}^{\infty} \sum_{j = 1}^{N} (-1)^{j + 1} \binom{N}{j} (\frac{1}{2^{i - 1}})^j
= \sum_{j = 1}^{N} (-1)^{j + 1} \binom{N}{j} \sum_{i = 1}^{\infty} (\frac{1}{2^j})^{i - 1}
= \sum_{j = 1}^{N} (-1)^{j + 1} \binom{N}{j} \frac{1}{(1 - \frac{1}{2^j})} (Sum of infinite geometric sequence with first term as a and common difference as r (\lt 1) is \frac{a}{1 - r})
= \sum_{j = 1}^{N} (-1)^{j + 1} \binom{N}{j} \frac{2^j}{(2^j - 1)}
The above summation can be calculated in \mathcal{O}(N) or \mathcal{O}(N \log_2 N).
SOLUTIONS:
Setter's Solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
#define mod 1000000007
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=1000023;
ll fact[N];
ll invfact[N];
ll inv[N];
void factorialsComputation()
{
inv[0]=inv[1]=1;
fact[0]=fact[1]=1;
invfact[0]=invfact[1]=1;
for(int i=2;i<N;i++)
{
inv[i]=(inv[mod%i]*(mod-mod/i))%mod;
fact[i]=(fact[i-1]*i)%mod;
invfact[i]=(invfact[i-1]*inv[i])%mod;
}
}
ll ncr(ll n,ll r)
{
ll ans=fact[n]*invfact[r];
ans%=mod;
ans*=invfact[n-r];
ans%=mod;
return ans;
}
void solve()
{
ll n;
cin>>n;
ll ans=1;
for(int i=1;i<=n;i++)
{
ll temp = ncr(n,i)*modInverse(power(2,i)-1);
temp%=mod;
if(i%2==0)
temp=mod-temp;
ans+=temp;
ans%=mod;
}
cout<<ans<<'\n';
}
int main()
{
factorialsComputation();
int t;
cin>>t;
while(t--)
solve();
}
Tester's Solution
#include <bits/stdc++.h>
#define ll long long int
#define mod 1000000007
#define maxn 300007
using namespace std;
ll fact[maxn],ifact[maxn];
ll mpow(ll a, ll b){
ll res = 1;
while(b){
if(b&1) res *= a,res %= mod;
a *= a;
a %= mod;
b >>= 1;
}
return res;
}
void pre(){
fact[0] = fact[1] = ifact[0] = ifact[1] = 1;
for(int i = 2;i < maxn;i++){
fact[i] = (fact[i - 1]*i)%mod;
ifact[i] = mpow(fact[i],mod - 2);
}
}
ll comb(ll a,ll b){
ll ans = (fact[a]*ifact[b])%mod;
ans *= ifact[a - b];
ans %= mod;
return ans;
}
int main() {
int t;
cin >> t;
pre();
while(t--) {
int n;
cin >> n;
ll ans = 1, sign = 1;
for(int i = 1; i <= n; i++) {
ans += (comb(n, i)*mpow((mpow(2, i) - 1 + mod)%mod, mod - 2))%mod*sign;
ans += mod;
ans %= mod;
sign *= -1;
}
cout << ans << "\n";
}
return 0;
}
