fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. #define fast ios_base::sync_with_stdio(false); cin.tie(nullptr); cin.tie(nullptr);
  4. #define int long long
  5. #define ld long double
  6. #define pb emplace_back
  7. #define range(v) v.begin(),v.end()
  8. #define mod 1000000007
  9. #define inf (int)1e15
  10. #define pii pair<int,int>
  11. #define ff first
  12. #define ss second
  13. // #define N --
  14.  
  15. using namespace std;
  16.  
  17. vector<vector<int>> multiply(vector<vector<int>>& a, vector<vector<int>>& b) {
  18. 	vector<vector<int>> c(2, vector<int>(2));
  19. 	for (int i = 0; i < 2; i++) {
  20. 		for (int j = 0; j < 2; j++) {
  21. 			for (int x = 0; x < 2; x++) {
  22. 				c[i][j] += (a[i][x] % mod * b[x][j] % mod) % mod;
  23. 				c[i][j] %= mod;
  24. 			}
  25. 		}
  26. 	}
  27. 	return c;
  28. }
  29.  
  30. vector<vector<int>> power(vector<vector<int>> a, int p) {
  31. 	if (p == 1) return a;
  32. 	vector<vector<int>> ans = power(a, p / 2);
  33. 	ans = multiply(ans, ans);
  34. 	return (p & 1) ? multiply(a, ans) : ans;
  35. }
  36.  
  37. int fastFib(int n) {
  38. 	if (n == 0 or n == 1) return n;
  39. 	vector<vector<int>> t{{1, 1}, {1, 0}};
  40. 	vector<int> fb{1, 0};
  41. 	t = power(t, n - 1);
  42.  
  43. 	int ans = 0;
  44. 	for (int i = 0; i < 2; i++) {
  45. 		ans += (t[0][i] % mod * fb[i] % mod) % mod;
  46. 		ans %= mod;
  47. 	}
  48. 	return ans %= mod;
  49. }
  50.  
  51. int32_t main() {
  52. 	fast
  53. 	int t_c = 1;
  54. 	cin >> t_c;
  55. 	while (t_c--) {
  56. 		// cout << "#: ";
  57. 		int n;
  58. 		cin >> n;
  59. 		cout << fastFib(n) << endl;
  60. 	}
  61. }
Success #stdin #stdout 0s 4376KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
334481190
https://ideone.com/1aKYsl
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

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!