fork download 
  1. #include <bits/stdc++.h>
  2. #ifndef ONLINE_JUDGE
  3. #include "debug.cpp"
  4. #else
  5. #define debug(...)
  6. #define debugArr(...)
  7. #endif // Debugging locally
  8. using namespace std;
  9. #define ll long long int
  10. #define endl "\n"
  11.  
  12. inline ll add64(const ll &a, const ll &b, const ll &mod)
  13. {
  14. 	__int128_t res = __int128_t(a) + b;
  15. 	if (res >= mod)
  16. 		res -= mod;
  17. 	return res;
  18. }
  19.  
  20. inline ll sub64(const ll &a, const ll &b, const ll &mod)
  21. {
  22. 	__int128_t res = __int128_t(a) - b;
  23. 	if (res < 0)
  24. 		res += mod;
  25. 	if (res >= mod)
  26. 		res -= mod;
  27. 	return res;
  28. }
  29.  
  30. inline ll mult64(const ll &a, const ll &b, const ll &mod)
  31. {
  32. 	return __int128_t(a) * b % mod;
  33. }
  34.  
  35. ll modPow(ll N, ll power, const ll &mod)
  36. {
  37. 	if (N % mod == 0 || N == 0)
  38. 		return 0;
  39. 	if (N == 1 || power == 0)
  40. 		return 1;
  41.  
  42. 	ll res{1};
  43. 	while (power)
  44. 	{
  45. 		if (power & 1)
  46. 			res = mult64(res, N, mod);
  47. 		N = mult64(N, N, mod);
  48. 		power >>= 1;
  49. 	}
  50. 	return res;
  51. }
  52.  
  53. class Matrix
  54. {
  55. private:
  56. 	int numRows;
  57. 	int numCols;
  58. 	ll modulus;
  59. 	vector<vector<ll>> data;
  60.  
  61. public:
  62. 	// Constructor: zero matrix
  63. 	Matrix(int rows, int cols, ll mod = 1e9 + 7)
  64. 		: numRows(rows), numCols(cols), modulus(mod), data(rows, vector<ll>(cols, 0)) {}
  65.  
  66. 	// Constructor: with initial value (mod parameter comes first to avoid ambiguity)
  67. 	Matrix(int rows, int cols, ll mod, ll initialValue)
  68. 		: numRows(rows), numCols(cols), modulus(mod), data(rows, vector<ll>(cols, initialValue)) {}
  69.  
  70. 	// Constructor: from 2D vector
  71. 	Matrix(const vector<vector<ll>> &matrix, ll mod = 1e9 + 7)
  72. 		: numRows(matrix.size()), numCols(matrix[0].size()), modulus(mod), data(matrix) {}
  73.  
  74. 	// Copy constructor
  75. 	Matrix(const Matrix &other) = default;
  76.  
  77. 	// Assignment operator
  78. 	Matrix &operator=(const Matrix &other) = default;
  79.  
  80. 	// Element access using operator[]
  81. 	vector<ll> &operator[](int row)
  82. 	{
  83. 		assert(row >= 0 && row < numRows);
  84. 		return data[row];
  85. 	}
  86.  
  87. 	const vector<ll> &operator[](int row) const
  88. 	{
  89. 		assert(row >= 0 && row < numRows);
  90. 		return data[row];
  91. 	}
  92.  
  93. 	// Matrix multiplication
  94. 	Matrix operator*(const Matrix &other) const
  95. 	{
  96. 		assert(numCols == other.numRows);
  97. 		assert(modulus == other.modulus);
  98.  
  99. 		Matrix result(numRows, other.numCols, modulus);
  100. 		for (int i = 0; i < numRows; i++)
  101. 		{
  102. 			for (int j = 0; j < other.numCols; j++)
  103. 			{
  104. 				for (int k = 0; k < numCols; k++)
  105. 					result.data[i][j] = add64(result.data[i][j], mult64(data[i][k], other.data[k][j], modulus), modulus);
  106. 			}
  107. 		}
  108. 		return result;
  109. 	}
  110.  
  111. 	// Matrix addition
  112. 	Matrix operator+(const Matrix &other) const
  113. 	{
  114. 		assert(numRows == other.numRows && numCols == other.numCols);
  115. 		assert(modulus == other.modulus);
  116.  
  117. 		Matrix result(numRows, numCols, modulus);
  118. 		for (int i = 0; i < numRows; i++)
  119. 		{
  120. 			for (int j = 0; j < numCols; j++)
  121. 				result.data[i][j] = add64(data[i][j], other.data[i][j], modulus);
  122. 		}
  123. 		return result;
  124. 	}
  125.  
  126. 	// Matrix subtraction
  127. 	Matrix operator-(const Matrix &other) const
  128. 	{
  129. 		assert(numRows == other.numRows && numCols == other.numCols);
  130. 		assert(modulus == other.modulus);
  131.  
  132. 		Matrix result(numRows, numCols, modulus);
  133. 		for (int i = 0; i < numRows; i++)
  134. 		{
  135. 			for (int j = 0; j < numCols; j++)
  136. 				result.data[i][j] = sub64(data[i][j], other.data[i][j], modulus);
  137. 		}
  138. 		return result;
  139. 	}
  140.  
  141. 	// Static method: create identity matrix
  142. 	static Matrix createIdentity(int size, ll mod = 1e9 + 7)
  143. 	{
  144. 		Matrix identity(size, size, mod);
  145. 		for (int i = 0; i < size; i++)
  146. 			identity.data[i][i] = 1;
  147. 		return identity;
  148. 	}
  149.  
  150. 	// Matrix exponentiation (only for square matrices)
  151. 	Matrix matrixPower(ll exponent) const
  152. 	{
  153. 		assert(numRows == numCols);
  154. 		assert(exponent >= 0);
  155.  
  156. 		Matrix result = createIdentity(numRows, modulus);
  157. 		Matrix base = *this;
  158.  
  159. 		while (exponent > 0)
  160. 		{
  161. 			if (exponent & 1)
  162. 				result = result * base;
  163. 			base = base * base;
  164. 			exponent >>= 1;
  165. 		}
  166. 		return result;
  167. 	}
  168.  
  169. 	// Sum of powers: A^0 + A^1 + A^2 + ... + A^N
  170. 	static Matrix sumOfPowers(const Matrix &matrix, ll exponent)
  171. 	{
  172. 		assert(matrix.numRows == matrix.numCols);
  173.  
  174. 		int dimension = matrix.numRows;
  175. 		ll mod = matrix.modulus;
  176. 		Matrix identity = createIdentity(dimension, mod);
  177.  
  178. 		// Build augmented 2d x 2d matrix M
  179. 		// M = [A  I]
  180. 		//     [0  I]
  181. 		Matrix augmented(2 * dimension, 2 * dimension, mod);
  182.  
  183. 		for (int i = 0; i < dimension; i++)
  184. 		{
  185. 			for (int j = 0; j < dimension; j++)
  186. 			{
  187. 				augmented.data[i][j] = matrix.data[i][j];						 // Top-left: A
  188. 				augmented.data[i][j + dimension] = (i == j) ? 1 : 0;			 // Top-right: I
  189. 				augmented.data[i + dimension][j] = 0;							 // Bottom-left: 0
  190. 				augmented.data[i + dimension][j + dimension] = (i == j) ? 1 : 0; // Bottom-right: I
  191. 			}
  192. 		}
  193.  
  194. 		// Compute M^{N+1}
  195. 		Matrix matrixExponent = augmented.matrixPower(exponent + 1);
  196.  
  197. 		// Extract top-right block: sum A^0 + A^1 + ... + A^N
  198. 		Matrix result(dimension, dimension, mod);
  199. 		for (int i = 0; i < dimension; i++)
  200. 		{
  201. 			for (int j = 0; j < dimension; j++)
  202. 				result.data[i][j] = matrixExponent.data[i][j + dimension];
  203. 		}
  204.  
  205. 		return result;
  206. 	}
  207.  
  208. 	// Print matrix (for debugging)
  209. 	friend ostream &operator<<(ostream &Cout, const Matrix &obj)
  210. 	{
  211. 		for (int i = 0; i < obj.numRows; i++)
  212. 		{
  213. 			for (int j = 0; j < obj.numCols; j++)
  214. 				Cout << obj.data[i][j] << " ";
  215. 			Cout << "\n";
  216. 		}
  217. 		return Cout;
  218. 	}
  219.  
  220. 	// Check if matrix is square
  221. 	bool isSquare() const
  222. 	{
  223. 		return numRows == numCols;
  224. 	}
  225. };
  226.  
  227. int main()
  228. {
  229. 	ios_base::sync_with_stdio(false);
  230. 	cin.tie(nullptr);
  231. #ifndef ONLINE_JUDGE
  232. 	freopen("input.txt", "r", stdin);
  233. 	freopen("Output.txt", "w", stdout);
  234. #endif //! ONLINE_JUDGE
  235. 	int t = 1;
  236. 	ll N;
  237. 	// cin >> t;
  238. 	while (t--)
  239. 	{
  240. 		ll A, X, M;
  241. 		cin >> A >> X >> M;
  242. 		Matrix matrix({{A, 1}, {0, 1}}, M);
  243. 		matrix = matrix.matrixPower(X);
  244. 		cout << matrix[0][1];
  245. 	}
  246. 	return 0;
  247. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin 
Standard input is empty
stdout 
4042884702585
https://ideone.com/6ub4Cs
language:
C++ (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!