fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long int lld;
  5.  
  6. lld t[3][3]={{1,0,1},{0,2,3},{0,3,5}};
  7. lld a[3][3]={{1,0,1},{0,2,3},{0,3,5}};
  8. lld mod = 1000000007;
  9.  
  10. void mul(lld a[][3],lld b[][3])
  11. {
  12. 	lld i,j,k;
  13. 	lld temp[3][3]={0};
  14. 	for(i=0;i<3;i++)
  15. 	for(j=0;j<3;j++)
  16. 	for(k=0;k<3;k++)
  17. 	{
  18. 		lld x = a[i][k]*b[k][j];
  19. 		while(x>=mod)
  20. 		x=x-mod;
  21. 		lld y = x+temp[i][j];
  22.  
  23. 		while(y>=mod)
  24. 		y=y-mod;
  25. 		temp[i][j] = y;
  26. 	}
  27.  
  28. 	for(i=0;i<3;i++)
  29. 	for(j=0;j<3;j++)
  30. 	a[i][j]=temp[i][j];
  31. }
  32.  
  33. void fib(lld n)
  34. {
  35. 	if(n==2)
  36.     {
  37.     	a[0][0]=1;
  38.     	a[0][1]=3;
  39.     	a[0][2]=6;
  40.     	a[1][0]=a[2][0]=0;
  41.     	a[1][1]=13;
  42.     	a[1][2]=a[2][1]=21;
  43.     	a[2][2]=34;
  44.     	return;
  45.     }
  46. 	if(n==1)
  47. 	return;
  48. 	fib(n/2);
  49. 	mul(a,a);
  50. 	if(n&1)
  51. 	mul(a,t);
  52. }
  53.  
  54. void fastscan(lld &number) 
  55. { 
  56.     //variable to indicate sign of input number 
  57.     bool negative = false; 
  58.     register int c; 
  59.  
  60.     number = 0; 
  61.  
  62.     // extract current character from buffer 
  63.     c = getchar(); 
  64.     if (c=='-') 
  65.     { 
  66.         // number is negative 
  67.         negative = true; 
  68.  
  69.         // extract the next character from the buffer 
  70.         c = getchar(); 
  71.     } 
  72.  
  73.     // Keep on extracting characters if they are integers 
  74.     // i.e ASCII Value lies from '0'(48) to '9' (57) 
  75.     for (; (c>47 && c<58); c=getchar()) 
  76.         number = number *10 + c - 48; 
  77.  
  78.     // if scanned input has a negative sign, negate the 
  79.     // value of the input number 
  80.     if (negative) 
  81.         number *= -1; 
  82. } 
  83.  
  84. int main()
  85. {
  86. 	lld t;
  87. 	ios_base::sync_with_stdio(false);
  88. 	cin.tie(NULL);
  89. 	fastscan(t);
  90. //	scanf("%lld",&t);
  91. 	while(t--)
  92. 	{
  93. 		lld n;
  94. 		fastscan(n);
  95. 	//	scanf("%lld",&n);
  96. 		a[0][0]=a[0][2]=1;
  97. 		a[0][1]=a[1][0]=a[2][0]=0;
  98. 		a[1][2]=a[2][1]=3;
  99. 		a[2][2]=5;
  100. 		a[1][1]=2;
  101.  
  102. 		if(n==0)
  103. 	    cout << "0\n";
  104. 		else
  105. 		{
  106. 			fib(n);
  107. 			lld q=2*a[0][2];
  108. 			while(q>=mod)
  109. 			q=q-mod;
  110. 			lld r = q+a[0][1];
  111. 			while(r>=mod)
  112. 			r=r-mod;
  113. 			cout << r << "\n";
  114. 		}
  115. 	}
  116. 	return 0;
  117. }
Success #stdin #stdout 0s 4512KB
comments (?)
stdin
copy 
2
2
4
stdout
copy 
15
714
https://ideone.com/xICiTo
problem FLIB, based on SPOJ submission 25121847 (CPP14), 2019-12-23 20:34:25
language:
C++14 (gcc 8.3)
created:
4 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!