forked from Ouditchya/SPOJ
-
Notifications
You must be signed in to change notification settings - Fork 0
/
RABBIT1.cpp
75 lines (61 loc) · 2.17 KB
/
RABBIT1.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
// AC, ALGO : Matrix Exponentiation, Number Theory.
/* Some Helpful Links :
http://en.wikipedia.org/wiki/Exponentiation_by_squaring
http://comeoncodeon.wordpress.com/2011/05/08/recurrence-relation-and-matrix-exponentiation/
http://zobayer.blogspot.in/2010/11/matrix-exponentiation.html
http://en.wikipedia.org/wiki/Fibonacci_number
http://mathworld.wolfram.com/FibonacciNumber.html
*/
// For any clarifications, contact me at : [email protected]
#include <cstdio>
#include <cmath>
using namespace std ;
typedef unsigned long long i64 ;
i64 MOD ;
inline i64 matrix_exponentiation( i64 ex )
{
i64 a[2][2] = { { 1 , 1 } , { 1 , 0 } } , temp[2][2] , i[2][2] = { { 1 , 0 } , { 0 , 1 } } ;
if( ex == 0 )
return 0 ;
else if( ex == 1 )
return 1 ;
else
{
ex-- ;
while( ex )
{
if( ex & 1 )
{
temp[0][0] = i[0][0] ;
temp[0][1] = i[0][1] ;
temp[1][0] = i[1][0] ;
temp[1][1] = i[1][1] ;
i[0][0] = ( ( temp[0][0] * a[0][0] ) + ( temp[0][1] * a[1][0] ) ) % MOD ;
i[0][1] = ( ( temp[0][0] * a[0][1] ) + ( temp[0][1] * a[1][1] ) ) % MOD ;
i[1][0] = ( ( temp[1][0] * a[0][0] ) + ( temp[1][1] * a[1][0] ) ) % MOD ;
i[1][1] = ( ( temp[1][0] * a[0][1] ) + ( temp[1][1] * a[1][1] ) ) % MOD ;
}
temp[0][0] = a[0][0] ;
temp[0][1] = a[0][1] ;
temp[1][0] = a[1][0] ;
temp[1][1] = a[1][1] ;
a[0][0] = ( ( temp[0][0] * temp[0][0] ) + ( temp[0][1] * temp[1][0] ) ) % MOD ;
a[0][1] = ( ( temp[0][0] * temp[0][1] ) + ( temp[0][1] * temp[1][1] ) ) % MOD ;
a[1][0] = ( ( temp[1][0] * temp[0][0] ) + ( temp[1][1] * temp[1][0] ) ) % MOD ;
a[1][1] = ( ( temp[1][0] * temp[0][1] ) + ( temp[1][1] * temp[1][1] ) ) % MOD ;
ex >>= 1 ;
}
}
return i[0][0] % MOD ;
}
int main( )
{
i64 t , n , m ;
for( scanf("%llu",&t) ; t ; t-- )
{
scanf("%llu %llu",&n,&m) ;
MOD = 1 << m ;
printf("%llu\n",matrix_exponentiation( n + 1 )) ;
}
return 0 ;
}