fork(1) download
copy 
  1. /*
  2. 	Solution By - Amrutansu Garanaik
  3. 	Codechef ID - dragonemperor
  4. */
  5.  
  6. #include<stdio.h>
  7. #define MOD 1000000007
  8. typedef long long ll;
  9. void multiply(ll a[4][4],ll b[4][4],ll c[4][4])
  10. {
  11. 	ll d[4][4];
  12. 	for(int i=0;i<4;i++)
  13. 	for(int j=0;j<4;j++)
  14. 	{
  15. 		d[i][j]=0;
  16. 		for(int k=0;k<4;k++)
  17. 		{
  18. 			d[i][j]=d[i][j]+a[i][k]*b[k][j];
  19. 			d[i][j]%=MOD;
  20. 			d[i][j]+=MOD;
  21. 			d[i][j]%=MOD;
  22. 		}
  23. 	}
  24. 	for(int i=0;i<4;i++)
  25. 	for(int j=0;j<4;j++)
  26. 		c[i][j]=d[i][j];
  27. }
  28. void exponent(ll result[4][4],ll trans[4][4],ll power)
  29. {
  30. 	while(power)
  31. 	{
  32. 		if(power&1)
  33. 		{
  34. 			multiply(result,trans,result);		
  35. 		}
  36. 		multiply(trans,trans,trans);		
  37. 		power/=2;
  38. 	}
  39. }
  40. int main()
  41. {
  42. 	ll test,a,b,c,e,t0,t1,t2,n,ans;
  43. 	scanf("%lld",&test);
  44. 	while(test--)
  45. 	{
  46. 		ans=0;
  47. 		scanf("%lld%lld%lld%lld%lld%lld%lld",&a,&b,&c,&e,&t0,&t1,&t2);
  48. 		scanf("%lld",&n);
  49. 		a=(a+MOD)%MOD;
  50. 		b=(b+MOD)%MOD;
  51. 		c=(c+MOD)%MOD;
  52. 		e=(e+MOD)%MOD;
  53. 		t0=(t0+MOD)%MOD;
  54. 		t1=(t1+MOD)%MOD;
  55. 		t2=(t2+MOD)%MOD;
  56. 		if(n<=3)
  57. 		{
  58. 			if(n==1)
  59. 				printf("%lld\n",t0);
  60. 			else if(n==2)
  61. 				printf("%lld\n",t1);
  62. 			else if(n==3)
  63. 				printf("%lld\n",t2);
  64. 			continue;
  65. 		}
  66. 		ll trans[4][4]= {
  67. 					{a,b,c,1},
  68. 					{1,0,0,0},
  69. 					{0,1,0,0},
  70. 					{0,0,0,1},
  71. 				};
  72. 		ll result[4][4]={
  73. 					{1,0,0,0},
  74. 					{0,1,0,0},
  75. 					{0,0,1,0},
  76. 					{0,0,0,1},
  77.  
  78. 				};
  79. 		ll initial[4]={t2,t1,t0,e};
  80. 		exponent(result,trans,n-3);		
  81. 		for(int i=0;i<4;i++)
  82. 		{
  83. 			ans=ans+(result[0][i]*initial[i])%MOD;
  84. 			ans%=MOD;
  85. 		}
  86. 		if(ans<0)
  87. 			ans+=MOD;
  88. 		printf("%lld\n",ans);
  89. 	}
  90. }
Success #stdin #stdout 0s 2732KB
comments (?)
stdin
copy 
1
5 4 5 2 1 4 5 2 6
stdout
copy 
4
https://ideone.com/DCmm1i
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 years 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!