Soluție HackerRank pentru Computer Virus, subdomeniul Number Theory, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Computer Virus
- Domeniu: Number Theory
- Limbaj: C++14
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
Cerință
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 ≤ Q ≤ 10^5
1≤ n≤ 5 × 10^6
0≤ t≤ 10^18
The sum of all n's in one file does not exceed 5 × 10^6
Cod sursă
#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;
}