HackerRank Algebra – Girlfriend & Necklace

Challenge: Girlfriend & Necklace

Subdomeniu: Algebra (algebra)

Scor cont: 80.0 / 80

Submission status: Accepted

Submission score: 1.0

Submission ID: 464736356

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/gneck/problem

Cerinta

Mr. X wants to buy a necklace for his girlfriend.
The available necklaces are bi-colored (red and blue beads).

Mr. X desperately wants to impress his girlfriend and knows that she will like the necklace only if **every prime length continuous sub-sequence of beads in the necklace** has more or equal number of red beads than blue beads.

Given the number of beads in the necklace N, Mr. X wants to know the number of all possible such necklaces.

_Note: - It is given that the necklace is a single string and not a loop._


**Input Format**  
The first line of the input contains an integer *T*, the number of testcases.  
*T* lines follow, each line containing *N*, the number of beads in the necklace.  

**Constraints**  
1 ≤ T ≤ 10<sup>4</sup>  
2 ≤ N ≤ 10<sup>18</sup>  

**Output Format**  
For each testcase, print in a newline, the number of such necklaces that are possible.  If the answer is greater than or equal to 10<sup>9</sup>+7, print the answer modulo ( % ) 10<sup>9</sup>+7.

**Sample Input**

    2
    2
    3

**Sample Output**

    3
    4

**Explanation**

For the first testcase, valid arrangement of beads are 

    BR RB RR

For the second testcase, valid arrangement of beads are

    BRR RBR RRR RRB

Cod sursa

//gneck.cpp
//Girlfriend & Necklace
//Weekly Challenges - Week 8
//Author: derekhh

#include<iostream>
#include<cstring>
using namespace std;

const int MOD = 1000000007;

struct Matrix
{
	long long val[3][3];
	int row, col;
};

Matrix m, b;

Matrix mul(Matrix a, Matrix b)
{
	Matrix ret;
	ret.row = a.row;
	ret.col = b.col;
	for (int i = 0; i < a.row; i++)
	{
		for (int j = 0; j < b.col; j++)
		{
			ret.val[i][j] = 0;
			for (int k = 0; k < a.col; k++)
				ret.val[i][j] = (ret.val[i][j] + a.val[i][k] * b.val[k][j]) % MOD;
		}
	}
	return ret;
}

Matrix pow(long long n)
{
	Matrix ret;
	ret.row = ret.col = 3;
	memset(ret.val, 0, sizeof(ret.val));
	ret.val[0][0] = ret.val[1][1] = ret.val[2][2] = 1;
	Matrix cur = m;
	while (n)
	{
		if (n % 2) ret = mul(ret, cur);
		cur = mul(cur, cur);
		n /= 2;
	}
	return ret;
}

int main()
{
	int t;
	cin >> t;

	b.row = 3;
	b.col = 1;
	memset(b.val, 0, sizeof(b.val));
	b.val[0][0] = b.val[1][0] = b.val[2][0] = 1;

	while (t--)
	{
		long long n;
		cin >> n;

		m.row = 3; m.col = 3;
		memset(m.val, 0, sizeof(m.val));
		m.val[0][0] = 1; 
		m.val[0][1] = 1; 
		m.val[1][2] = 1; 
		m.val[2][0] = 1;

		Matrix ans_m = mul(pow(n - 2), b);
		long long ans = 0;
		for (int i = 0; i < 3; i++)
			ans = (ans + ans_m.val[i][0]) % MOD;
		cout << ans << endl;
	}
	return 0;
}