HackerRank Number Theory – Computer Virus

Challenge: Computer Virus

Subdomeniu: Number Theory (number-theory)

Scor cont: 100.0 / 100

Submission status: Accepted

Submission score: 1.0

Submission ID: 464810824

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/demidenko-computer-virus/problem

Cerinta

Suppose we have an *n-dimensional* supercomputer with an infinite number of processors. Every processor has a vector of $n$ integers as its (*n-dimensional*) coordinates and can be thought of as a point in the $n$-dimensional space. Furthermore, at every $n$-dimensional lattice point, there is a processor. Two processors are called _neighbors_ if their coordinate vectors are different in only one position, and the absolute difference of the numbers in that position is equal to $1$. For example $(0,0,0)$ and $(1,0,0)$ are neighbors, and so are $(-1,2,3,4)$ and $(-1,2,3,3)$. But $(0,0,0)$ and $(1,0,1)$, and $(1,2,3,4)$ and $(1,2,3,2)$, are not neighbors.

Some processors of this computer are infected by a virus. At time $0$, only one processor is infected. After every second, all uninfected processors that are neighbors with infected ones become infected too. Given $n$ and $t$, calculate the number of processors that are infected after $t$ seconds, modulo $(10^9+7)$.

Input Format

The first line contains an integer $Q$, the number of test cases.  
Each of the next $Q$ lines contains two integers $n$ and $t$, separated by a space.

Output Format

For every test case, write the answer in a single line.  

**Constraints**  

$1 \leq Q \leq 10^{5}$  
$1\leq n\leq 5 \times 10^{6}$  
$0\leq t\leq 10^{18}$  
The sum of all $n$'s in one file does not exceed $5 \times 10^{6}$

Cod sursa

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

static const long long MOD = 1000000007LL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int Q;
    if (!(cin >> Q)) return 0;

    vector<pair<long long,long long>> qs(Q);
    long long maxK = 0;
    for (int i = 0; i < Q; ++i) {
        long long n, t;
        cin >> n >> t;
        qs[i] = {n, t};
        maxK = max(maxK, min(n, t));
    }

    vector<long long> inv(maxK + 2, 1);
    for (long long i = 2; i <= maxK + 1; ++i) {
        inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD;
    }

    for (auto [n, t] : qs) {
        long long K = min(n, t);

        long long cn = 1;  // C(n,0)
        long long ct = 1;  // C(t,0)
        long long pow2 = 1;
        long long ans = 1; // k=0

        for (long long k = 0; k < K; ++k) {
            // move to k+1
            cn = cn * ((n - k) % MOD) % MOD;
            cn = cn * inv[k + 1] % MOD;

            ct = ct * ((t - k) % MOD) % MOD;
            ct = ct * inv[k + 1] % MOD;

            pow2 = (pow2 << 1) % MOD;

            long long term = cn * ct % MOD;
            term = term * pow2 % MOD;
            ans += term;
            if (ans >= MOD) ans -= MOD;
        }

        cout << ans << '\n';
    }

    return 0;
}