就是求第$n$个图形的上三角的个数
设$f_n$为第$n$个图形的上三角的个数 $g_n$为第$n$个图形的下三角的个数
那么$f_n = 3f_{n-1}+g_{n-1}$ 并且$g_n = 3g_{n-1}+f_{n-1}$
则可以构造矩阵 用矩阵快速幂解决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
using namespace std;
struct prog {
__int64 a[2][2] ;
void init(){
a[0][0]=a[1][1]=3;
a[1][0]=a[0][1]=1;
}
};
prog matrixmul ( prog a ,prog b )
{
int i , j , k ;
prog c ;
for ( i = 0 ; i < 2; i ++ )
{
for ( j = 0 ; j < 2 ; j ++ )
{
c.a[i][j]=0;
for ( k =0 ; k < 2; k ++ )
c.a[i][j]+=__int64(a.a[i][k]*b.a[k][j]) ;
c.a[i][j] %= 1000000007 ;
}
}
return c ;
}
prog mul (prog s , __int64 k )
{
prog ans ;
ans.init();
while ( k >= 1 )
{
if ( k & 1 )
ans = matrixmul ( ans , s ) ;
k = k >> 1 ;
s = matrixmul ( s , s ) ;
}
return ans ;
}
int main()
{
__int64 n ;
while ( cin >> n )
{
if(n==0)
{
cout<<1<<endl;
continue;
}
prog s ;
s.init ( ) ;
s = mul ( s , n - 1 ) ;
cout<<s.a[0][0]%1000000007<<endl;
}
return 0;
}