Challenge: Extremely Dangerous Virus

Subdomeniu: Probability (probability)

Scor cont: 30.0 / 30

Submission status: Accepted

Submission score: 1.0

Submission ID: 464725331

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/extremely-dangerous-virus/problem

Cerinta

A recent lab accident resulted in the creation of an extremely dangerous virus that replicates so rapidly it's hard to predict exactly how many cells it will contain after a given period of time. However, a lab technician made the following observations about its growth per millisecond:

- The probability of the number of virus cells growing by a factor of $a$ is $0.5$.
- The probability of the number of virus cells growing by a factor of $b$ is $0.5$. 

Given $a$, $b$, and knowing that initially there is only a single cell of virus, calculate the *expected number* of virus cells after $t$ milliseconds. As this number can be very large, print your answer modulo $(10^9 + 7)$.

Input Format

A single line of three space-separated integers denoting the respective values of $a$ (the first growth factor), $b$ (the second growth factor), and $t$ (the time you want to know the expected number of cells for).

Output Format

Print the expected number of virus cells after $t$ milliseconds modulo $(10^9 + 7)$.

Constraints

- $1 \leq t \leq 10^{18}$  
- $1 \leq a, b \leq 100$  
- it is guaranteed that expected value is integer

Cod sursa

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


int main()
{
    int a,b;
    long t;
    cin >> a >> b >> t;
    long growth=(a+b)/2;
    long total=1;
    vector<int> binary;
    long twoth=2;
    while (t>0)
    {
        if (t%twoth==0)
            binary.push_back(0);
        else
        {
            binary.push_back(1);
            t-=twoth/2;
        }
        twoth= (2*twoth);
    }
    for (int i=0; i<binary.size(); i++)
    {
        if (binary[i]==1)
        {
            total*=growth;
            total%=1000000007;
        }
        growth*=growth;
        growth%=1000000007;
    }    
    cout << total;
    return 0;
}
HackerRank Probability – Extremely Dangerous Virus