Soluție HackerRank pentru Circle Summation, subdomeniul Algebra, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Circle Summation
- Domeniu: Algebra
- Limbaj: C++14
Challenge: Circle Summation
Subdomeniu: Algebra (algebra)
Scor cont: 80.0 / 80
Submission status: Accepted
Submission score: 1.0
Submission ID: 464735083
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/circle-summation/problem
Cerință
There are n children, numbered 1,2,…,n, sitting around a circle in a clockwise manner. The ith child has a piece of paper with the number a_i written on it. They play the following game:
- In the 1st round, the child numbered i increases his number by the sum of the numbers of his neighbors.
- In the 2nd round, the child next in clockwise order increases his number by the sum of the numbers of his neighbors.
- In the 3rd round, the child next in clockwise order increases his number by the sum of the numbers of his neighbors.
- And so on.
The game ends after m rounds have been played.
For every i, find the numbers that the children end up with if the game starts with child i playing the first round. Since the numbers can be large, output them [modulo](https://en.wikipedia.org/wiki/Modulo_operation) 10^9 + 7.
Input Format
The first line contains t, the number of test cases. t cases follow.
The first line of each test case contains two space-separated integers n and m. The next line contains n integers, the ith of which is a_i.
Output Format
For each test case, print n lines, each having n integers. The jth integer on the ith line contains the number that the jth child ends up with if the game starts with child i playing the first round.
Print a blank line after each test case *except the last one*.
Since the numbers can be large, output them [modulo](https://en.wikipedia.org/wiki/Modulo_operation) 10^9 + 7.
Constraints
- 1 ≤ t ≤ 15
- 3 ≤ n ≤ 50
- 1 ≤ m ≤ 10^9
- 1 ≤ a_i ≤ 10^9
Cod sursă
// https://www.hackerrank.com/challenges/circle-summation
#include <iostream>
#include <cstdio>
#include <vector>
#include <list>
#include <unordered_set>
using namespace std;
typedef unsigned long long ullong;
#define MOD_NUM 1000000007ull
class SquareMatrix {
public:
SquareMatrix(int _size, int _exp)
: size(_size), exp(_exp) {
//cout << _size << " " << _exp << endl;
M = vector< vector<ullong> > (size, vector<ullong>(size, 0));
orig = vector< vector<ullong> > (size, vector<ullong>(size, 0));
initCircleSummation();
}
void multiply(const vector<ullong> &v, vector<ullong> & output) {
output = vector<ullong>(v.size(), 0);
for(int row = 0; row < size; ++row)
for(int col = 0; col < size; ++col)
output[row] =
(output[row] + (M[row][col] * v[col])%MOD_NUM)
%MOD_NUM;
}
void print() {
for(int row = 0; row < size; ++row) {
for(int col = 0; col < size; ++col)
printf("%d ", M[row][col]);
printf("\n");
}
printf("\n");
}
private:
void initCircleSummation() {
for(int index = 1; index < size; index++)
orig[index-1][index] = M[index-1][index] = 1;
M[size-1][0] = M[size-1][1] = M[size-1][size-1] = 1;
orig[size-1][0] = orig[size-1][1] = orig[size-1][size-1] = 1;
findExponential(exp);
}
void findExponential(int _exp) {
if(_exp >= 2) {
findExponential(_exp/2);
multiplyWithItself();
if(_exp % 2 == 1)
multiplyWithOriginal();
}
}
void multiplyWithItself() {
vector<vector<ullong> > temp =
vector< vector<ullong> > (size, vector<ullong>(size, 0));
for(int row = 0; row < size; ++row)
for(int col = 0; col < size; ++col) {
for(int k = 0; k < size; ++k)
temp[row][col] =
(temp[row][col] + (M[row][k] *
M[k][col] ) %MOD_NUM )
% MOD_NUM;
}
for(int row = 0; row < size; ++row)
for(int col = 0; col < size; ++col)
M[row][col] = temp[row][col];
}
void multiplyWithOriginal() {
vector<vector<ullong> > temp =
vector< vector<ullong> > (size, vector<ullong>(size, 0));
for(int row = 0; row < size; ++row)
for(int col = 0; col < size; ++col) {
for(int row2 = 0; row2 < size; ++row2)
temp[row][col] =
(temp[row][col] + (M[row][row2] *
orig[row2][col] ) %MOD_NUM )
% MOD_NUM;
}
for(int row = 0; row < size; ++row)
for(int col = 0; col < size; ++col)
M[row][col] = temp[row][col];
}
vector<vector<ullong> > M, orig;
int size;
int exp;
};
void print(vector<ullong> &vec, int n) {
int index = 0;
for(auto it = vec.begin() + vec.size() - n;
it != vec.end(); ++it, ++index) {
printf("%d", *it);
if(index < vec.size()-1)
printf(" ");
}
for(auto it = vec.begin();
it != vec.begin() + vec.size() - n; ++it, ++index) {
printf("%d", *it);
if(index < vec.size()-1)
printf(" ");
}
}
void rotateBy1(vector<ullong> &vec) {
list<ullong> rotated(vec.begin()+1, vec.end());
rotated.push_back(vec[0]);
vec.clear();
vec = vector<ullong>(rotated.begin(), rotated.end());
}
void solveCircleSummation() {
int nTests;
scanf(" %d", &nTests);
for(int test = 0; test < nTests; ++test) {
int N;
int mSize;
scanf(" %d %d", &N, &mSize);
vector<ullong> vec;
for(int entry = 0; entry < N; ++entry) {
int inp;
scanf(" %d", &inp);
vec.push_back(inp);
}
SquareMatrix sqMat = SquareMatrix(N, mSize);
int N_1 = mSize%N;
vector<ullong> finalOut(N, 0);
for(int entry = 0; entry < N; ++entry) {
sqMat.multiply(vec, finalOut);
print(finalOut, N_1);
printf("\n");
N_1 = (N_1 + 1) % N;
rotateBy1(vec);
}
if(test < nTests -1)
printf("\n");
}
}
int main() {
solveCircleSummation();
return 0;
}