這次比賽的時間是23:30開始...囧...寫了一道A題就回去睡覺了..這場比賽有三道題A的人很多..本題就是一個很典型的找遞推式..用矩陣乘法求解...
另 N [ k ] [ 0 ] 表示第 k 時間向上三角形個數... N [ k ] [ 1 ] 表示 k 時間向下三角形個數...那麼易得:
N [ k ] [ 0 ] = N [ k-1 ] [ 0 ] * 3 + N [ k - 1 ] [ 1 ]
N [ k ] [ 1 ] = N [ k-1 ] [ 1 ] * 3 + N [ k - 1 ] [ 0 ]
由於k很大..只能用矩陣乘法求解..構造矩陣:
h= [ 3 1
1 3 ]
初始值為 A={ 1 , 0 }
那麼要求第k天的情況: A*h^k 即可....
Program:
[cpp]
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
#define oo 2000000000
#define ll long long
using namespace std;
struct node
{
ll s[2][2];
}_2jie[70],temp;
ll n;
node matrix_mul(node a,node b)
{
int k,i,j;
memset(temp.s,0,sizeof(temp.s));
for (k=0;k<2;k++)
for (i=0;i<2;i++)
for (j=0;j<2;j++)
temp.s[i][j]=(temp.s[i][j]+a.s[i][k]*b.s[k][j])%1000000007;
return temp;
}
node getanswer(node h,ll l)
{
ll k,i;
node ans;
_2jie[1]=h;
k=2;
for (i=2;i<63;i++)
{
_2jie[i]=matrix_mul(_2jie[i-1],_2jie[i-1]);
k*=2;
}
ans.s[0][0]=1; ans.s[0][1]=0;
ans.s[1][0]=0; ans.s[1][1]=1;
while (l)
{
while (k>l)
{
i--;
k/=2;
}
ans=matrix_mul(ans,_2jie[i]);
l-=k;
}
return ans;
}
int main()
{
scanf("%I64d",&n);
node h;
h.s[0][0]=3; h.s[0][1]=1;
h.s[1][0]=1; h.s[1][1]=3;
h=getanswer(h,n);
printf("%I64d\n",h.s[0][0]);
return 0;
}
